Syntactic complexity of scattered context grammars (Q1892719)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Syntactic complexity of scattered context grammars |
scientific article |
Statements
Syntactic complexity of scattered context grammars (English)
0 references
21 June 1995
0 references
The syntactic complexity of context-free grammars defined over word monoids is investigated. It is demonstrated that every recursively enumerable language can be defined by a ten-nonterminal context-free grammar over a word monoid generated by an alphabet and six words of length two. Open problems are formulated.
0 references
syntactic complexity
0 references
context-free grammars
0 references
