Displaying similar documents to “Translation from classical two-way automata to pebble two-way 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.

Hyper-minimizing minimized deterministic finite state automata

Andrew Badr, Viliam Geffert, Ian Shipman (2009)

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

Similarity:

We present the first (polynomial-time) algorithm for reducing a given deterministic finite state automaton (DFA) into a hyper-minimized DFA, which may have fewer states than the classically minimized DFA. The price we pay is that the language recognized by the new machine can differ from the original on a finite number of inputs. These hyper-minimized automata are optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs. With small modifications,...

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

Efficient simulation of synchronous systems by multi-speed systems

Tomasz Jurdziński, Mirosław Kutyłowski, Jan Zatopiański (2005)

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

Similarity:

We consider systems consisting of finite automata communicating by exchanging messages and working on the same read-only data. We investigate the situation in which the automata work with constant but different speeds. We assume furthermore that the automata are not aware of the speeds and they cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata. Complexity measure that we consider here is...