Displaying similar documents to “Loops in automata and HDTOL relations”

Two-way automaton computations

Jean-Camille Birget (1990)

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

Similarity:

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.