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, boolean operators 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 . Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids .
| Property | Value |
|---|
| dbpedia-owl: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, boolean operators 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 . 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 monadic first-order logic over the natural numbers with the less-than relation, as the languages acceptable by counter-free automata and as languages definable in linear temporal logic .
|
| dcterms:subject
| |
| 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, boolean operators 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 . Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids .
|
| rdfs:label
| |
| owl:sameAs
| |
| foaf:page
| |
| is dbpedia-owl:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
