Generalized star height problem
1 reference results for: Generalized star height problem
Wikipedia
The generalized star-height problem in formal language theory is the open question whether all regular languages can be expressed using regular expressions with a built-in complement operator of limited star height, i. e. with a limited nesting depth of Kleene stars. Specifically, it is an open question whether a nesting depth of more than 1 is required, and if so, whether there is an algorithm to determine the minimum required star height.
Regular languages of star-height 0 are also known as star-free languages. The theorem of Schützenberger provides an algebraic characterization of star-free languages by means of aperiodic syntactic monoids. In particular star-free languages are a proper decidable subclass of regular languages.
See also
References
- M.P. Schützenberger, "On finite monoids having only trivial subgroups", Information and Control, 8, 190–194 (1965).
- Jean-Eric Pin, Howard Straubing and Denis Thérien, Some results on the generalized star-height problem, Information and Computation, 101(2):219–250, December 1992. Available from http://www.liafa.jussieu.fr/~jep/Resumes/StarHeight.html
Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)
This article is licensed under the GNU Free Documentation License.
Last updated on Tuesday June 24, 2008 at 16:05:05 PDT (GMT -0700)
View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation
This article is licensed under the GNU Free Documentation License.
Last updated on Tuesday June 24, 2008 at 16:05:05 PDT (GMT -0700)
View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation
Share This:
Copyright © 2008, Dictionary.com, LLC. All rights reserved.
