The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Similarity relations and cover automata”

Minimal NFA and biRFSA Languages

Michel Latteux, Yves Roos, Alain Terlutte (2008)

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

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

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