اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCompletely reducible sets
181
0
0.0
(
0
)
تأليف
Dominique Perrin
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We study the family of rational sets of words, called completely reducible and which are such that the syntactic representation of their characteristic series is completely reducible. This family contains, by a result of Reutenauer, the submonoids generated by bifix codes and, by a result of Berstel and Reutenauer, the cyclic sets. We study the closure properties of this family. We prove a result on linear representations of monoids which gives a generalization of the result concerning the complete reducibility of the submonoid generated by a bifix code to sets called birecurrent. We also give a new proof of the result concerning cyclic sets.
قيم البحث
اقرأ أيضاً
A completely reducible subcomplex of a spherical building is a spherical building.
A set is called recurrent if its minimal automaton is strongly connected and birecurrent if it is recurrent as well as its reversal. We prove a series of results concerning birecurrent sets. It is already known that any birecurrent set is completely
reducible (that is, such that the minimal representation of its characteristic series is completely reducible). The main result of this paper characterizes completely reducible sets as linear combinations of birecurrent sets
Given a (finite or infinite) subset $X$ of the free monoid $A^*$ over a finite alphabet $A$, the rank of $X$ is the minimal cardinality of a set $F$ such that $X subseteq F^*$. We say that a submonoid $M$ generated by $k$ elements of $A^*$ is {em $k$
-maximal} if there does not exist another submonoid generated by at most $k$ words containing $M$. We call a set $X subseteq A^*$ {em primitive} if it is the basis of a $|X|$-maximal submonoid. This definition encompasses the notion of primitive word -- in fact, ${w}$ is a primitive set if and only if $w$ is a primitive word. By definition, for any set $X$, there exists a primitive set $Y$ such that $X subseteq Y^*$. We therefore call $Y$ a {em primitive root} of $X$. As a main result, we prove that if a set has rank $2$, then it has a unique primitive root. To obtain this result, we prove that the intersection of two $2$-maximal submonoids is either the empty word or a submonoid generated by one single primitive word. For a single word $w$, we say that the set ${x,y}$ is a {em bi-root} of $w$ if $w$ can be written as a concatenation of copies of $x$ and $y$ and ${x,y}$ is a primitive set. We prove that every primitive word $w$ has at most one bi-root ${x,y}$ such that $|x|+|y|<sqrt{|w|}$. That is, the bi-root of a word is unique provided the word is sufficiently long with respect to the size (sum of lengths) of the root. Our results are also compared to previous approaches that investigate pseudo-repetitions, where a morphic involutive function $theta$ is defined on $A^*$. In this setting, the notions of $theta$-power, $theta$-primitive and $theta$-root are defined, and it is shown that any word has a unique $theta$-primitive root. This result can be obtained with our approach by showing that a word $w$ is $theta$-primitive if and only if ${w, theta(w)}$ is a primitive set.
In this note we study automata recognizing birecurrent sets. A set of words is birecurrent if the minimal partial DFA recognizing this set and the minimal partial DFA recognizing the reversal of this set are both strongly connected. This notion was i
ntroduced by Perrin, and Dolce et al. provided a characterization of such sets. We prove that deciding whether a partial DFA recognizes a birecurrent set is a PSPACE-complete problem. We show that this problem is PSPACE-complete even in the case of binary partial DFAs with all states accepting and in the case of binary complete DFAs. We also consider a related problem of computing the rank of a partial DFA.
Given a (finite or infinite) subset $X$ of the free monoid $A^*$ over a finite alphabet $A$, the rank of $X$ is the minimal cardinality of a set $F$ such that $X subseteq F^*$. A submonoid $M$ generated by $k$ elements of $A^*$ is $k$-maximal if ther
e does not exist another submonoid generated by at most $k$ words containing $M$. We call a set $X subseteq A^*$ primitive if it is the basis of a $|X|$-maximal submonoid. This extends the notion of primitive word: indeed, ${w}$ is a primitive set if and only if $w$ is a primitive word. By definition, for any set $X$, there exists a primitive set $Y$ such that $X subseteq Y^*$. The set $Y$ is therefore called a primitive root of $X$. As a main result, we prove that if a set has rank $2$, then it has a unique primitive root. This result cannot be extended to sets of rank larger than 2. For a single word $w$, we say that the set ${x,y}$ is a {em binary root} of $w$ if $w$ can be written as a concatenation of copies of $x$ and $y$ and ${x,y}$ is a primitive set. We prove that every primitive word $w$ has at most one binary root ${x,y}$ such that $|x|+|y|<sqrt{|w|}$. That is, the binary root of a word is unique provided the length of the word is sufficiently large with respect to the size of the root. Our results are also compared to previous approaches that investigate pseudo-repetitions, where a morphic involutive function $theta$ is defined on $A^*$. In this setting, the notions of $theta$-power, $theta$-primitive and $theta$-root are defined, and it is shown that any word has a unique $theta$-primitive root. This result can be obtained with our approach by showing that a word $w$ is $theta$-primitive if and only if ${w, theta(w)}$ is a primitive set.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
