Displaying similar documents to “On the k-reversibility of finite automata.”

Returning and non-returning parallel communicating finite automata are equivalent

Ashish Choudhary, Kamala Krithivasan, Victor Mitrana (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

A parallel communicating automata system consists of several automata working independently in parallel and communicating with each other by request with the aim of recognizing a word. Rather surprisingly, returning parallel communicating finite automata systems are equivalent to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata. Some open problems are finally formulated.

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.

How expressions can code for automata

Sylvain Lombardy, Jacques Sakarovitch (2005)

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

Similarity:

In this paper we investigate how it is possible to recover an automaton from a rational expression that has been computed from that automaton. The notion of derived term of an expression, introduced by Antimirov, appears to be instrumental in this problem. The second important ingredient is the co-minimization of an automaton, a dual and generalized Moore algorithm on non-deterministic automata. We show here that if an automaton is then sufficiently “decorated”, the combination of these...

Strategies to scan pictures with automata based on Wang tiles

Violetta Lonati, Matteo Pradella (2011)

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

Similarity:

Wang automata are devices for picture language recognition recently introduced by us, which characterize the class REC of recognizable picture languages. Thus, Wang automata are equivalent to tiling systems or online tessellation acceptors, and are based like Wang systems on labeled Wang tiles. The present work focus on scanning strategies, to prove that the ones Wang automata are based on are those following four kinds of movements: boustrophedonic, “L-like”, “U-like”, and spirals. ...

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

Note on the complexity of Las Vegas automata problems

Galina Jirásková (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

We investigate the complexity of several problems concerning Las Vegas finite automata. Our results are as follows. (1) The membership problem for Las Vegas finite automata is in NL. (2) The nonemptiness and inequivalence problems for Las Vegas finite automata are NL-complete. (3) Constructing for a given Las Vegas finite automaton a minimum state deterministic finite automaton is in NP. These results provide partial answers to some open problems posed by Hromkovič and Schnitger...