Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSymbolic dynamics
151
0
0.0
(
0
)
Added by
Jean Berstel
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We revisit the complexity of procedures on SFAs (such as intersection, emptiness, etc.) and analyze them according to the measures we find suitable for symbolic automata: the number of states, the maximal number of transitions exiting a state, and the size of the most complex transition predicate. We pay attention to the special forms of SFAs: {normalized SFAs} and {neat SFAs}, as well as to SFAs over a {monotonic} effective Boolean algebra.
This paper presents a general and systematic discussion of various symbolic representations of iterated maps through subshifts. We give a unified model for all continuous maps on a metric space, by representing a map through a general subshift over usually an uncountable alphabet. It is shown that at most the second order representation is enough for a continuous map. In particular, it is shown that the dynamics of one-dimensional continuous maps to a great extent can be transformed to the study of subshift structure of a general symbolic dynamics system. By introducing distillations, partial representations of some general continuous maps are obtained. Finally, partitions and representations of a class of discontinuous maps, piecewise continuous maps are discussed, and as examples, a representation of the Gauss map via a full shift over a countable alphabet and representations of interval exchange transformations as subshifts of infinite type are given.
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.
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 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
