Algorithms for determining relative star height and star height

Kosaburo Hashiguchi
Additional contact information
Kosaburo Hashiguchi: Toyohashi University of technology

A chapter in Sequences, 1990, pp 228-243 from Springer

Abstract: Abstract Eggan(l963) introduced the notion of the star height to each regular expression which is a nonnegative integer denoting the nestedness of star operators in this expression. The star height of a regular language is the minimum of the star height of regular expressions denoting this language. We remark here that to each regular language, there exist generally infinitely many regular expressions denoting this language. Eggan(l963) showed that for each nonnegative integer k, there exists a regular language of star height k, and posed the problem of determining the star height of any regular language. Dejean and Schutzenberger (1966) showed that for each nonnegative integer k, there exists a regular language of star height k over the two-letter alphabet. McNaughton (1967) presented an algorithm for determining the loop complexity (i.e., the star height) of any regular language whose syntactic monoid is a group. Cohen (1970, 1971) and Cohen and Brzozowski (1970) investigated many properties of star height, some of which provide algorithms for determining the star height of any regular language of certain reset-free type. Hashiguchi and Honda (1979) presented an algorithm for determining the star height of any reset-free language and any reset language. Hashiguchi (1982B) presented an algorithm for deciding whether or not an arbitrary language is of star height one. To obtain this result, it uses the limitedness theorem on finite automata with distance functions (in short, D-automata) in Hashiguci (1982A, 1983).

Keywords: Limitedness Theorem; Nonnegative Integer; Regular Expression; Regular Language; Finite Automaton (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-3352-7_17

Ordering information: This item can be ordered from
http://www.springer.com/9781461233527

DOI: 10.1007/978-1-4612-3352-7_17

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().