Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0878.68077
Breveglieri, L.
Fair expressions and regular languages over lists. (English)
[J] RAIRO, Inform. Théor. Appl. 31, No.1, 15-66 (1997). ISSN 0988-3754

Summary: A formalism is proposed, named fair expressions, partly introduced in {\it L. Breveglieri}, {\it A. Cherubini} and {\it S. Crespi Reghizzi} [Fair list languages and parallel programme schemes, in developments in formal language theory, G. Rozenberg and A. Salomaa eds., World Scientific Publishing, 389-418 (1994)] that extends regular expressions to lists, having strings as components. This formalism uses classical regular operators, i.e. catenation and its closure, and novel ones, namely the operator of merge and its closure, which are natural for lists. Fair expressions allow to define languages of lists, named fair languages, which can be compared to word languages by flattening the lists into strings. In this paper, the basic properties of fair languages are briefly summarized and also extended with respect to previous works: hierarchy, semilinearity, closure, decidability and comparison with the Chomsky hierarchy are dealt with. The family of fair languages is however far larger than the regular one; as a novel contribution this paper investigates its subfamilies that are comparable with regular languages. The main result is that the regular subfamilies of fair languages constitute a proper hierarchy. These subfamilies are then characterized and their properties are explored, showing that they are, in general, more mathematically tractable than fair languages. The conclusion lists comparisons with related works, open problems and research directions.

MSC 2000:: *68Q45 Formal languages

Keywords: Chomsky hierarchy

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]