go-v.orgcodex
Menu
Page tools

codex · Philosophy

Star height

In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexity of regular expressions and regular languages. The star height of a regular expression equals the maximum nesting depth of stars appearing in that expression. The star height of a regular language is the least star height of any regular expression for that language. The concept of star height was first defined and studied by Eggan (1963).

Wikipedia contributors, "Star height", Wikipedia, revision 1188056294, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex