Algorithms for determining relative star height and star height (Q1118420)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Algorithms for determining relative star height and star height
scientific article

    Statements

    Algorithms for determining relative star height and star height (English)
    0 references
    1988
    0 references
    Let R be a regular language and \({\mathcal C}=(R_ 1,R_ 2,...,R_ m)\) be a finite set of regular languages. The relative star height of R with respect to \({\mathcal C}\) is the minimum star height of regular languages which can be transformed into R by substituting alphabetic symbols on languages from \({\mathcal C}\). This paper proves the existence of algorithm for determining the relative star height. This evidently implies the solvability of determining the star height for any regular language. The suggested algorithm is quite complex.
    0 references
    regular language
    0 references
    relative star height
    0 references

    Identifiers