Syntactic complexity of scattered context grammars (Q1892719)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Syntactic complexity of scattered context grammars |
scientific article; zbMATH DE number 766463
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Syntactic complexity of scattered context grammars |
scientific article; zbMATH DE number 766463 |
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
