Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q5532516> ?p ?o }
Showing triples 1 to 23 of
23
with 100 triples per page.
- Q5532516 subject Q7036095.
- Q5532516 subject Q7142640.
- Q5532516 subject Q9149857.
- Q5532516 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.".
- Q5532516 wikiPageExternalLink starheight.html.
- Q5532516 wikiPageExternalLink StarHeight.html.
- Q5532516 wikiPageWikiLink Q1384896.
- Q5532516 wikiPageWikiLink Q185612.
- Q5532516 wikiPageWikiLink Q192161.
- Q5532516 wikiPageWikiLink Q3217203.
- Q5532516 wikiPageWikiLink Q3321297.
- Q5532516 wikiPageWikiLink Q6030974.
- Q5532516 wikiPageWikiLink Q638934.
- Q5532516 wikiPageWikiLink Q7036095.
- Q5532516 wikiPageWikiLink Q7142640.
- Q5532516 wikiPageWikiLink Q752532.
- Q5532516 wikiPageWikiLink Q7601219.
- Q5532516 wikiPageWikiLink Q8366.
- Q5532516 wikiPageWikiLink Q849775.
- Q5532516 wikiPageWikiLink Q912887.
- Q5532516 wikiPageWikiLink Q9149857.
- Q5532516 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.".
- Q5532516 label "Generalized star height problem".