Algorithms for determining relative star height and star height. (English) Zbl 0668.68081

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.
Reviewer: A.V.Anisimov


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Braquelaire, J.P.; Courcelle, B., The solutions of two star-height problems for regular trees, Theoret. comput. sci., 30, 205-239, (1984) · Zbl 0554.68037
[2] Brzozowski, J.A., Roots of star events, J. assoc. comput. Mach., 14, 466-477, (1967) · Zbl 0162.02601
[3] Cohen, R.S., Star height of certain families of regular events, J. comput. system sci., 4, 281-297, (1970) · Zbl 0245.94039
[4] Cohen, R.S., Techniques for establishing star height of regular sets, Math. systems theory, 5, 97-114, (1971) · Zbl 0218.94028
[5] Cohen, R.S.; Brzozowski, J.A., General properties of star height of regular events, J. comput. system sci., 4, 260-280, (1970) · Zbl 0245.94038
[6] Dejean, F.; Schutzenberger, M.P., On a question of eggan, Inform. contr., 9, 23-25, (1966) · Zbl 0209.02903
[7] Eggan, L.C., Transition graphs and the star height of regular events, Michigan math. J., 10, 385-397, (1963) · Zbl 0173.01504
[8] Hashiguchi, K., A decision procedure for the order of regular events, Theoret. comput. sci., 8, 69-72, (1979) · Zbl 0419.68088
[9] Hashiguchi, K., Limitedness theorem on finite automata with distance functions, J. comput. system sci., 24, 233-244, (1982) · Zbl 0513.68051
[10] Hashiguchi, K., Regular languages of star height one, Inform. control, 53, 199-210, (1982) · Zbl 0547.68072
[11] Hashiguchi, K., Representation theorems on regular languages, J. comput. system sci., 27, 101-115, (1983) · Zbl 0516.68063
[12] Hashiguchi, K., Improved limitedness theorems on finite automata with distance functions, 86, (1986), Rapport LITP Université Paris
[13] Hashiguchi, K.; Honda, N., Homomorphisms that preserve star height, Inform. contr., 30, 247-266, (1976) · Zbl 0325.94039
[14] Hashiguchi, K.; Honda, N., The star height of rest-free events and strictly locally testable events, Inform. contr., 40, 267-284, (1979) · Zbl 0406.68051
[15] Linna, M., Finite power property of regular languages, (), 87-98
[16] McNaughton, R., The loop complexity of pure-group events, Inform. contr., 11, 167-176, (1967) · Zbl 0166.26905
[17] {\scSimon, I.} (1978), Locally finite semigroups and limited subsets of a free monoid, a manuscript.
[18] Validow, F., On the on the stard star height of regular sets I, Electron. informationsverarb. kybernet., 22, 463-473, (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.