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