Displaying similar documents to “Systems of parallel communicating restarting 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.

Similarity relations and cover automata

Jean-Marc Champarnaud, Franck Guingne, Georges Hansel (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Cover automata for finite languages have been much studied a few years ago. It turns out that a simple mathematical structure, namely similarity relations over a finite set of words, is underlying these studies. In the present work, we investigate in detail for themselves the properties of these relations beyond the scope of finite languages. New results with straightforward proofs are obtained in this generalized framework, and previous results concerning cover automata are obtained...

How expressions can code for automata

Sylvain Lombardy, Jacques Sakarovitch (2010)

RAIRO - Theoretical Informatics and 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...

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