Puissance extérieure d'un automate déterministe, application au calcul de la fonction zêta d'un système sofique
Computing the prefix of an automaton
Tree algebra of sofic tree languages
We consider the languages of finite trees called tree-shift languages which are factorial extensible tree languages. These languages are sets of factors of subshifts of infinite trees. We give effective syntactic characterizations of two classes of regular tree-shift languages: the finite type tree languages and the tree languages which are almost of finite type. Each class corresponds to a class of subshifts of trees which is invariant by conjugacy. For this goal, we define a tree algebra which...
Asynchronous sliding block maps
Computing the prefix of an automaton
We present an algorithm for computing the prefix of an automaton. Automata considered are non-deterministic, labelled on words, and can have -transitions. The prefix automaton of an automaton has the following characteristic properties. It has the same graph as . Each accepting path has the same label as in . For each state , the longest common prefix of the labels of all paths going from to an initial or final state is empty. The interest of the computation of the prefix of an automaton...
Asynchronous sliding block maps
We define a notion of asynchronous sliding block map that can be realized by transducers labeled in * × *. We show that, under some conditions, it is possible to synchronize this transducer by state splitting, in order to get a transducer which defines the same sliding block map and which is labeled in × , where is a constant integer. In the case of a transducer with a strongly connected graph, the synchronization process can be considered as an implementation of an algorithm of Frougny...
Page 1