Displaying similar documents to “Minimal NFA and biRFSA Languages”

Minimal NFA and biRFSA languages

Michel Latteux, Yves Roos, Alain Terlutte (2009)

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

Similarity:

In this paper, we define the notion of biRFSA which is a residual finate state automaton (RFSA) whose the reverse is also an RFSA. The languages recognized by such automata are called biRFSA languages. We prove that the canonical RFSA of a biRFSA language is a minimal NFA for this language and that each minimal NFA for this language is a sub-automaton of the canonical RFSA. This leads to a characterization of the family of biRFSA languages. In the second part of this paper, we define...

Deterministic blow-ups of minimal NFA's

Galina Jirásková (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

The paper treats the question whether there always exists a minimal nondeterministic finite automaton of states whose equivalent minimal deterministic finite automaton has states for any integers and with . Partial answers to this question were given by Iwama, Kambayashi, and Takaki (2000) and by Iwama, Matsuura, and Paterson (2003). In the present paper, the question is completely solved by presenting appropriate automata for all values of and . However, in order to give an...

Strategies to scan pictures with automata based on Wang tiles

Violetta Lonati, Matteo Pradella (2011)

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

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

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