This HTML5 document contains 54 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/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-cahttp://ca.dbpedia.org/resource/
n13https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
n15http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-frhttp://fr.dbpedia.org/resource/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
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:Star-free_language
rdf:type
yago:Language106282651 yago:Abstraction100002137 yago:Communication100033020 yago:WikicatFormalLanguages
rdfs:label
Langage sans étoile Llenguatge lliure d'estrella Star-free language
rdfs:comment
A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star. For instance, the language of words over the alphabet that do not have consecutive a's can be defined by , where denotes the complement of a subset of . The condition is equivalent to having generalized star height zero. An example of a regular language which is not star-free is , i.e. the language of strings consisting of an even number of "a". En informatique théorique, et notamment en théorie des langages formels, un langage rationnel est sans étoile (star-free language en anglais) s'il peut être obtenu à partir des lettres d'un alphabet et de l'ensemble vide par un ensemble fini d'opérations ensemblistes d'union, intersection, de complémentaire et de concaténations, mais sans utiliser l'opération étoile. Un llenguatge regular es diu que és un llenguatge lliure d'estrella si es pot descriure amb una expressió regular construïda amb les lletres d'un alfabet, el símbol buit, tots els operadors booleans (incloent-hi complement i concatenació) però no la clausura de Kleen. Per exemple, el llenguatge de paraules de l'alfabet que no té as consecutives es pot definir com , on denota el complement del subconjunt de . Un exemple d'un llenguatge que no es lliure d'estrella és . Tots els llenguatges lliure d'estrella pertanyen a la classe de complexitat AC0.
dcterms:subject
dbc:Automata_(computation) dbc:Logic_in_computer_science dbc:Formal_languages
dbo:wikiPageID
4922792
dbo:wikiPageRevisionID
1054696254
dbo:wikiPageWikiLink
dbr:Counter-free_language dbr:Concatenation dbr:Syntactic_monoid dbr:Aperiodic_monoid dbr:Generalized_star_height dbr:AC0 dbr:First-order_logic dbr:Set_operations_(Boolean) dbc:Automata_(computation) dbr:Generalized_star_height_problem dbr:Star_height dbc:Logic_in_computer_science dbr:Complement_(set_theory) dbr:Star_height_problem dbr:Alphabet_(computer_science) dbr:Regular_expression dbc:Formal_languages dbr:Regular_language dbr:Marcel-Paul_Schützenberger dbr:Kleene_star dbr:Empty_set dbr:Linear_temporal_logic
dbo:wikiPageExternalLink
n15:DG-WT08.pdf
owl:sameAs
dbpedia-fr:Langage_sans_étoile yago-res:Star-free_language n13:2yUaG freebase:m.0cvcd_ dbpedia-ca:Llenguatge_lliure_d'estrella wikidata:Q3217203
dbp:wikiPageUsesTemplate
dbt:Comp-sci-theory-stub dbt:Formal_languages_and_grammars dbt:Cite_book dbt:Reflist
dbo:abstract
A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star. For instance, the language of words over the alphabet that do not have consecutive a's can be defined by , where denotes the complement of a subset of . The condition is equivalent to having generalized star height zero. An example of a regular language which is not star-free is , i.e. the language of strings consisting of an even number of "a". Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids. They can also be characterized logically as languages definable in FO[<], the first-order logic over the natural numbers with the less-than relation, as the counter-free languages and as languages definable in linear temporal logic. All star-free languages are in uniform AC0. En informatique théorique, et notamment en théorie des langages formels, un langage rationnel est sans étoile (star-free language en anglais) s'il peut être obtenu à partir des lettres d'un alphabet et de l'ensemble vide par un ensemble fini d'opérations ensemblistes d'union, intersection, de complémentaire et de concaténations, mais sans utiliser l'opération étoile. Par exemple, l'ensemble de tous les mots est le complémentaire de l'ensemble vide : c'est donc un langage sans étoile. Le langage des mots sur l'alphabet qui ne contiennent pas deux lettres consécutives est aussi un langage sans étoile. En effet, c'est l'ensemble défini par , où dénote le complément d'une partie de . Un llenguatge regular es diu que és un llenguatge lliure d'estrella si es pot descriure amb una expressió regular construïda amb les lletres d'un alfabet, el símbol buit, tots els operadors booleans (incloent-hi complement i concatenació) però no la clausura de Kleen. Per exemple, el llenguatge de paraules de l'alfabet que no té as consecutives es pot definir com , on denota el complement del subconjunt de . Un exemple d'un llenguatge que no es lliure d'estrella és . Es va caracteritzar els llenguatges lliures d'estrella com aquells monoides sintàctics aperiòdics. També es poden caracteritzar lògicament com llenguatges que es poden definir per FO[<], la lògica de primer ordre sobre els nombres naturals amb la relació "més petit que", també es poden caracteritzar com llenguatges sense comptadors i com a llenguatges definits per una lògica temporal lineal. Tots els llenguatges lliure d'estrella pertanyen a la classe de complexitat AC0.
prov:wasDerivedFrom
wikipedia-en:Star-free_language?oldid=1054696254&ns=0
dbo:wikiPageLength
3862
foaf:isPrimaryTopicOf
wikipedia-en:Star-free_language