Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Generalized_star_height_problem> ?p ?o }
Showing triples 1 to 44 of
44
with 100 triples 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 wikiPageLength "2838".
- Generalized_star_height_problem wikiPageOutDegree "19".
- Generalized_star_height_problem wikiPageRevisionID "691329587".
- Generalized_star_height_problem wikiPageWikiLink Algorithm.
- Generalized_star_height_problem wikiPageWikiLink Cambridge_University_Press.
- Generalized_star_height_problem wikiPageWikiLink Category:Automata_(computation).
- Generalized_star_height_problem wikiPageWikiLink Category:Formal_languages.
- Generalized_star_height_problem wikiPageWikiLink Category:Unsolved_problems_in_computer_science.
- Generalized_star_height_problem wikiPageWikiLink Formal_language.
- Generalized_star_height_problem wikiPageWikiLink Information_and_Computation.
- Generalized_star_height_problem wikiPageWikiLink Kleene_star.
- Generalized_star_height_problem wikiPageWikiLink Marcel-Paul_Schützenberger.
- Generalized_star_height_problem wikiPageWikiLink Regular_expression.
- Generalized_star_height_problem wikiPageWikiLink Regular_language.
- Generalized_star_height_problem wikiPageWikiLink Star-free_language.
- Generalized_star_height_problem wikiPageWikiLink Star_height.
- Generalized_star_height_problem wikiPageWikiLink Star_height_problem.
- Generalized_star_height_problem wikiPageWikiLink Syntactic_monoid.
- Generalized_star_height_problem wikiPageWikiLinkText "Generalized star height problem".
- Generalized_star_height_problem wikiPageUsesTemplate Template:Cite_book.
- Generalized_star_height_problem wikiPageUsesTemplate Template:Cite_journal.
- Generalized_star_height_problem wikiPageUsesTemplate Template:Comp-sci-theory-stub.
- Generalized_star_height_problem wikiPageUsesTemplate Template:Mathscinet.
- Generalized_star_height_problem wikiPageUsesTemplate Template:Reflist.
- Generalized_star_height_problem subject Category:Automata_(computation).
- Generalized_star_height_problem subject Category:Formal_languages.
- Generalized_star_height_problem subject Category:Unsolved_problems_in_computer_science.
- Generalized_star_height_problem hypernym Question.
- Generalized_star_height_problem type Language.
- Generalized_star_height_problem type Work.
- Generalized_star_height_problem type Combinatoric.
- Generalized_star_height_problem type Language.
- 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 Q5532516.
- Generalized_star_height_problem sameAs সাধারণীকৃত_তারকা-উচ্চতা_সমস্যা.
- Generalized_star_height_problem sameAs m.031fv0.
- Generalized_star_height_problem sameAs Q5532516.
- Generalized_star_height_problem wasDerivedFrom Generalized_star_height_problem?oldid=691329587.
- Generalized_star_height_problem isPrimaryTopicOf Generalized_star_height_problem.