Computing The Star Height of Regular Languages
In contrast, the second question turned out to be much more difficult, and the question became a famous open problem in formal language theory for over two decades (Brzozowski 1980). For years, there was only little progress. The pure-group languages were the first interesting family of regular languages for which the star height problem was proved to be decidable (McNaughton 1967). But the general problem remained open for more than 25 years until it was settled by Hashiguchi, who in 1988 published an algorithm to determine the star height of any regular language. The algorithm wasn't at all practical, being of non-elementary complexity. To illustrate the immense resource consumptions of that algorithm, Lombardy and Sakarovitch (2002) give some actual numbers:
| “ |
leads to computations that are by far impossible, even for very small examples. For instance, if L is accepted by a 4 state automaton of loop complexity 3 (and with a small 10 element transition monoid), then a very low minorant of the number of languages to be tested with L for equality is: |
” |
|
—S. Lombardy and J. Sakarovitch, Star Height of Reversible Languages and Universal Automata, LATIN 2002 |
||
Notice that alone the number has 10 billion zeros when written down in decimal notation, and is already by far larger than the number of atoms in the observable universe.
A much more efficient algorithm than Hashiguchi's procedure was devised by Kirsten in 2005. This algorithm runs, for a given nondeterministic finite automaton as input, within double-exponential space. Yet the resource requirements of this algorithm still greatly exceed the margins of what is considered practically feasible.
Read more about this topic: Star Height Problem
Famous quotes containing the words star, height, regular and/or languages:
“The sun descending in the west,
The evening star does shine;
The birds are silent in their nest,
And I must seek for mine.”
—William Blake (1757–1827)
“The enemy are no match for us in a fair fight.... The young men ... of the upper class are kind-hearted, good-natured fellows, who are unfit as possible for the business they are in. They have courage but no endurance, enterprise, or energy. The lower class are cowardly, cunning, and lazy. The height of their ambition is to shoot a Yankee from some place of safety.”
—Rutherford Birchard Hayes (1822–1893)
““I couldn’t afford to learn it,” said the Mock Turtle with a sigh. “I only took the regular course.”
“What was that?” inquired Alice.
“Reeling and Writhing, of course, to begin with,” the Mock Turtle replied; “and then the different branches of Arithmetic—Ambition, Distraction, Uglification, and Derision.”
“I never heard of ‘Uglification,’” Alice ventured to say.”
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“No doubt, to a man of sense, travel offers advantages. As many languages as he has, as many friends, as many arts and trades, so many times is he a man. A foreign country is a point of comparison, wherefrom to judge his own.”
—Ralph Waldo Emerson (1803–1882)