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:
“I must down to the seas again, to the lonely sea and the sky,
And all I ask is a tall ship and a star to steer her by,”
—John Masefield (1878–1967)
“I pray that, according to the riches of his glory, he may grant that you may be strengthened in your inner being with power through his Spirit, and that Christ may dwell in your hearts through faith, as you are being rooted and grounded in love. I pray that you may have the power to comprehend, with all the saints, what is the breadth and length and height and depth, and to know the love of Christ that surpasses knowledge, so that you may be filled with all the fullness of God.”
—Bible: New Testament, Ephesians 3:16-19.
“They were regular in being gay, they learned little things that are things in being gay, they learned many little things that are things in being gay, they were gay every day, they were regular, they were gay, they were gay the same length of time every day, they were gay, they were quite regularly gay.”
—Gertrude Stein (1874–1946)
“The very natural tendency to use terms derived from traditional grammar like verb, noun, adjective, passive voice, in describing languages outside of Indo-European is fraught with grave possibilities of misunderstanding.”
—Benjamin Lee Whorf (1897–1934)