Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0764.68087
Coupet-Grimal, Solange
Prolog infinite trees and automata. (English)
[J] RAIRO, Inform. Théor. Appl. 25, No.5, 397-418 (1991). ISSN 0988-3754

Summary: This paper deals with an algorithm constructing the minimal deterministic finite state automaton recognizing a language defined by a rational expression. It relies on a representation in a normalized form of languages over finite alphabets by infinite trees and uses the powerful implementation of these trees in Prolog. It accomodates extended rational expressions with new operators including intersection and difference. It is also possible to get complete or non complete automata, according to what is needed. The result is a program which is neat, close to the mathematic formulation and very concise (2 pages).

MSC 2000:: *68Q45 Formal languages

Keywords: regular expression; minimal deterministic finite state automaton; language defined by a rational expression; infinite trees; Prolog

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article 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]