mastodon — frederic — 7 Oct 2026
Oh, cool, OpenAI's AI proved that every regular language has generalized star height (gsh) <= 3. I remember this prob…

#computational-complexity #ai-assisted-proof #formal-languages
Oh, cool, OpenAI's AI proved that every regular language has generalized star height (gsh) <= 3. I remember this problem from my time as a computer science student. The bigger open question was, whether there is even any regular language L with gsh(L) > 1 or if all regular languages have gsh(L)<=1. Any CS student can understand this problem, if you know what regular languages and regular…