Back to Search
Start Over
Generative power of three-nonterminal scattered context grammars
- Source :
- Theoretical Computer Science. 246:279-284
- Publication Year :
- 2000
- Publisher :
- Elsevier BV, 2000.
-
Abstract
- This paper discusses the descriptional complexity of scattered context grammars with respect to the number of nonterminals. It proves that the three-nonterminal scattered context grammars characterize the family of recursively enumerable languages.
- Subjects :
- Theoretical computer science
General Computer Science
Computer science
business.industry
Context-sensitive grammar
Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)
Context (language use)
Context-free grammar
computer.software_genre
Theoretical Computer Science
Tree-adjoining grammar
Recursively enumerable language
Indexed grammar
Artificial intelligence
L-attributed grammar
business
Phrase structure grammar
computer
Computer Science::Formal Languages and Automata Theory
Natural language processing
Generative grammar
Computer Science(all)
Subjects
Details
- ISSN :
- 03043975
- Volume :
- 246
- Database :
- OpenAIRE
- Journal :
- Theoretical Computer Science
- Accession number :
- edsair.doi.dedup.....32889e073b4939c4fbcf499e74419969
- Full Text :
- https://doi.org/10.1016/s0304-3975(00)00153-5