Currently displaying 1 – 6 of 6

Showing per page

Order by Relevance | Title | Year of publication

Asynchronous sliding block maps

Marie-Pierre BéalOlivier Carton — 2010

RAIRO - Theoretical Informatics and Applications

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...

Tree algebra of sofic tree languages

Nathalie AubrunMarie-Pierre Béal — 2014

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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...

Computing the prefix of an automaton

Marie-Pierre BéalOlivier Carton — 2010

RAIRO - Theoretical Informatics and Applications

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...

Page 1

Download Results (CSV)