Přístupnostní navigace
E-application
Search Search Close
Publication result detail
MASOPUST, T.
Original Title
On the Descriptional Complexity of Scattered Context Grammars
English Title
Type
WoS Article
Original Abstract
This paper proves that every recursively enumerable language is generated by a scattered context grammar with no more than four nonterminals and three non-context-free productions. In its conclusion, it gives an overview of the results and open problems concerning scattered context grammars and languages.
English abstract
Keywords
scattered context grammar; descriptional complexity.
Key words in English
Authors
RIV year
2010
Released
01.01.2009
ISBN
0304-3975
Periodical
Theoretical Computer Science
Volume
410
Number
1
State
Kingdom of the Netherlands
Pages from
108
Pages to
112
Pages count
5
URL
http://dx.doi.org/10.1016/j.tcs.2008.10.017
Full text in the Digital Library
http://hdl.handle.net/
BibTex
@article{BUT49470, author="Tomáš {Masopust}", title="On the Descriptional Complexity of Scattered Context Grammars", journal="Theoretical Computer Science", year="2009", volume="410", number="1", pages="108--112", issn="0304-3975", url="http://dx.doi.org/10.1016/j.tcs.2008.10.017" }