Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1166.68025
Latteux, Michel; Roos, Yves; Terlutte, Alain
Minimal NFA and biRFSA languages. (English)
[J] Theor. Inform. Appl. 43, No. 2, 221-237 (2009). ISSN 0988-3754; ISSN 1290-385X/e

Summary: We define the notion of biRFSA which is a Residual Finite State Automaton (RFSA) whose 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 the family of biseparable automata. We prove that every biseparable NFA is uniquely minimal among all NFAs recognizing a same language, improving the result of H. Tamm and E. Ukkonen for bideterministic automata.

MSC 2000:: *68Q45 Formal languages

Keywords: residual finite state automata; minimal NFA

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]