Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Generalized_star_height_problem> ?p ?o. }
Showing items 1 to 28 of
28
with 100 items per page.
- Generalized_star_height_problem abstract "The generalized star-height problem in formal language theory is the open question whether all regular languages can be expressed using generalized regular expressions with a limited nesting depth of Kleene stars. Here, generalized regular expressions are defined like regular expressions, but they have a built-in complement operator. For a regular language, its generalized star height is defined as the minimum nesting depth of Kleene stars needed in order to describe the language by means of a generalized regular expression, hence the name of the problem. More 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.".
- Generalized_star_height_problem wikiPageExternalLink starheight.html.
- Generalized_star_height_problem wikiPageExternalLink StarHeight.html.
- Generalized_star_height_problem wikiPageID "669942".
- Generalized_star_height_problem wikiPageRevisionID "543790130".
- Generalized_star_height_problem hasPhotoCollection Generalized_star_height_problem.
- Generalized_star_height_problem subject Category:Automata_theory.
- Generalized_star_height_problem subject Category:Formal_languages.
- Generalized_star_height_problem subject Category:Unsolved_problems_in_computer_science.
- Generalized_star_height_problem type Abstraction100002137.
- Generalized_star_height_problem type Attribute100024264.
- Generalized_star_height_problem type Communication100033020.
- Generalized_star_height_problem type Condition113920835.
- Generalized_star_height_problem type Difficulty114408086.
- Generalized_star_height_problem type FormalLanguages.
- Generalized_star_height_problem type Language106282651.
- Generalized_star_height_problem type Problem114410605.
- Generalized_star_height_problem type State100024720.
- Generalized_star_height_problem type UnsolvedProblemsInComputerScience.
- Generalized_star_height_problem type UnsolvedProblemsInMathematics.
- Generalized_star_height_problem comment "The generalized star-height problem in formal language theory is the open question whether all regular languages can be expressed using generalized regular expressions with a limited nesting depth of Kleene stars. Here, generalized regular expressions are defined like regular expressions, but they have a built-in complement operator.".
- Generalized_star_height_problem label "Generalized star height problem".
- Generalized_star_height_problem sameAs m.031fv0.
- Generalized_star_height_problem sameAs Q5532516.
- Generalized_star_height_problem sameAs Q5532516.
- Generalized_star_height_problem sameAs Generalized_star_height_problem.
- Generalized_star_height_problem wasDerivedFrom Generalized_star_height_problem?oldid=543790130.
- Generalized_star_height_problem isPrimaryTopicOf Generalized_star_height_problem.