Syntactic complexity of scattered context grammars (Q1892719): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1007/bf01178263 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W4253932464 / rank | |||
Normal rank | |||
Latest revision as of 10:38, 30 July 2024
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
