'star-height' can also refer to...


More Like This

Show all results sharing this subject:

  • Computing


Show Summary Details

Quick Reference

The maximum depth to which the Kleene-star operator is nested in a given regular expression. The star-height of a regular language L is the smallest star-height of any regular expression for L. There is no known algorithm for determining the star-height of a regular language. It is however known that there are regular languages of arbitrary star-height.

If complement and intersection are allowed, the class of generalized regular expressions is obtained. For these it is not known if there are languages of star-height greater than one.

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.