Representations of a free group of rank two by time-varying Mealy automata

Adam Woryna

Displaying similar documents to “Representations of a free group of rank two by time-varying Mealy automata”

CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store

Benedek Nagy, Friedrich Otto (2011)

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

Similarity:

We study cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are equipped with an external pushdown store. In this way we obtain an automata-theoretical characterization for the class of word languages that are linearizations of context-free trace languages.

On the equivalence of linear conjunctive grammars and trellis automata

Alexander Okhotin (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence...

An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid

Laura Giambruno, Antonio Restivo (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

We investigate the intersection of two finitely generated submonoids of the free monoid on a finite alphabet. To this purpose, we consider automata that recognize such submonoids and we study the product automata recognizing their intersection. By using automata methods we obtain a new proof of a result of Karhumäki on the characterization of the intersection of two submonoids of rank two, in the case of prefix (or suffix) generators. In a more general setting, for an arbitrary number...

On an algorithm to decide whether a free group is a free factor of another

Pedro V. Silva, Pascal Weil (2008)

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

Similarity:

We revisit the problem of deciding whether a finitely generated subgroup $H$ is a free factor of a given free group $F$ . Known algorithms solve this problem in time polynomial in the sum of the lengths of the generators of $H$ and exponential in the rank of $F$ . We show that the latter dependency can be made exponential in the rank difference rank $(F)$ - rank $(H)$ , which often makes a significant change.