Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPattern Avoidability with Involution
130
0
0.0
(
0
)
Added by
EPTCS
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
An infinte word w avoids a pattern p with the involution t if there is no substitution for the variables in p and no involution t such that the resulting word is a factor of w. We investigate the avoidance of patterns with respect to the size of the alphabet. For example, it is shown that the pattern a t(a) a can be avoided over three letters but not two letters, whereas it is well known that a a a is avoidable over two letters.
rate research
Read More
In this paper we study the enumeration and the construction, according to the number of ones, of particular binary words avoiding a fixed pattern. The growth of such words can be described by particular jumping and marked succession rules. This approach enables us to obtain an algorithm which constructs all binary words having a fixed number of ones and then kills those containing the forbidden pattern.
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.
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 there 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.
This chapter presents some of the links between automata theory and symbolic dynamics. The emphasis is on two particular points. The first one is the interplay between some particular classes of automata, such as local automata and results on embeddings of shifts of finite type. The second one is the connection between syntactic semigroups and the classification of sofic shifts up to conjugacy.
The finiteness problem for automaton groups and semigroups has been widely studied, several partial positive results are known. However we prove that, in the most general case, the problem is undecidable. We study the case of automaton semigroups. Given a NW-deterministic Wang tile set, we construct an Mealy automaton, such that the plane admit a valid Wang tiling if and only if the Mealy automaton generates a finite semigroup. The construction is similar to a construction by Kari for proving that the nilpotency problem for cellular automata is unsolvable. Moreover Kari proves that the tiling of the plane is undecidable for NW-deterministic Wang tile set. It follows that the finiteness problem for automaton semigroup is undecidable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
