6533b85dfe1ef96bd12bf05f

RESEARCH PRODUCT

ON THE STAR HEIGHT OF RATIONAL LANGUAGES

Antonio RestivoRosa Montalbano

subject

Discrete mathematicsFactorialTransitive relationStar heightGeneral Mathematicsmedia_common.quotation_subjectComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)AmbiguityRegular languageIf and only ifComputer Science::Programming LanguagesEntropy (information theory)Algebraic numberMathematicsmedia_common

description

Two problems concerning the star height of a rational language are investigated: the star height one problem and the relationships between the unambiguity of an expression and its star height. For this purpose we consider the class of factorial, transitive and rational (FTR) languages. From the algebraic point of view a FTR language is the set of factors of a rational submonoid M. Two subclasses of FTR languages are introduced: renewal languages, corresponding to the case of M finitely generated, and unambiguous renewal languages, corresponding to the case of M finitely generated and free. We prove that a FTR language has star height one if and only if it is renewal. This gives a simple decision procedure for the star height one problem for this class of languages. As concerns the relationships with the ambiguity, we introduce the notion of unambiguous star height of a rational language and prove that it can be strictly greater than the star height. This is a consequence of the following results: i) a FTR language of unambiguous star height one is unambiguous renewal; ii) there exist renewal languages which are not unambiguous renewal. This last result is obtained by using arguments involving the entropy of a language.

yearjournalcountryeditionlanguage
1994-09-01International Journal of Algebra and Computation
https://doi.org/10.1142/s0218196794000075