This HTML5 document contains 38 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n17https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
n13http://www.liafa.jussieu.fr/~jep/Problemes/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n16http://bn.dbpedia.org/resource/
n15https://www.irif.fr/~jep/PDF/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Generalized_star-height_problem
rdfs:label
Generalized star-height problem
rdfs: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. 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.
dcterms:subject
dbc:Automata_(computation) dbc:Formal_languages dbc:Unsolved_problems_in_computer_science
dbo:wikiPageID
669942
dbo:wikiPageRevisionID
1032220457
dbo:wikiPageWikiLink
dbc:Unsolved_problems_in_computer_science dbc:Automata_(computation) dbr:Algorithm dbr:Regular_expression dbr:Theoretical_Computer_Science_(journal) dbr:Star_height dbr:Regular_language dbc:Formal_languages dbr:Marcel-Paul_Schützenberger dbr:Formal_language_theory dbr:Information_and_Control dbr:Cambridge_University_Press dbr:Information_and_Computation dbr:Syntactic_monoid dbr:Star-free_language dbr:Kleene_star dbr:Star_height_problem
dbo:wikiPageExternalLink
n13:starheight.html n15:StarHeight.pdf
owl:sameAs
wikidata:Q5532516 n16:সাধারণীকৃত_তারকা-উচ্চতা_সমস্যা n17:4kGJA
dbp:wikiPageUsesTemplate
dbt:Cite_book dbt:Comp-sci-theory-stub dbt:Reflist dbt:Unsolved dbt:Cite_journal
dbo: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.
prov:wasDerivedFrom
wikipedia-en:Generalized_star-height_problem?oldid=1032220457&ns=0
dbo:wikiPageLength
3243
foaf:isPrimaryTopicOf
wikipedia-en:Generalized_star-height_problem