6533b870fe1ef96bd12cfa94

RESEARCH PRODUCT

The Star Height One Problem for Irreducible Automata

R. MontalbanoA. Restivo

subject

Discrete mathematicsStar heightAstrophysics::Cosmology and Extragalactic AstrophysicsExpression (computer science)Measure (mathematics)AutomatonLoop (topology)StarsRegular languageAstrophysics::Solar and Stellar AstrophysicsAstrophysics::Earth and Planetary AstrophysicsRegular expressionArithmeticAstrophysics::Galaxy AstrophysicsMathematics

description

The star height of a regular expression is, informally, the maximum number of nested stars in the expression. The star height of a regular language is the minimal star height of a regular expression denoting this language. The notion of star height indicates in a certain sense the “loop complexity” of a regular expression and thus it gives a measure of the complexity of a regular language.

yearjournalcountryeditionlanguage
1993-01-01
https://doi.org/10.1007/978-1-4613-9323-8_35