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

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.