Displaying similar documents to “Returning and non-returning parallel communicating finite automata are equivalent”

Systems of parallel communicating restarting automata

Marcel Vollweiler, Friedrich Otto (2014)

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

Similarity:

Several types of systems of parallel communicating restarting automata are introduced and studied. The main result shows that, for all types of restarting automata X, centralized systems of restarting automata of type X have the same computational power as non-centralized systems of restarting automata of the same type and the same number of components. This result is proved by a direct simulation. In addition, it is shown that for one-way restarting automata without auxiliary symbols,...

The factor automaton

Milan Šimánek (2002)

Kybernetika

Similarity:

This paper concerns searching substrings in a string using the factor automaton. The factor automaton is a deterministic finite automaton constructed to accept every substring of the given string. Nondeterministic factor automaton is used to achieve new operations on factor automata for searching in non-constant texts.

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