Detail publikace
On the Descriptional Complexity of Scattered Context Grammars
MASOPUST, T.
Originální název
On the Descriptional Complexity of Scattered Context Grammars
Anglický název
On the Descriptional Complexity of Scattered Context Grammars
Jazyk
en
Originální abstrakt
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.
Anglický abstrakt
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.
Dokumenty
BibTex
@article{BUT49470,
author="Tomáš {Masopust}",
title="On the Descriptional Complexity of Scattered Context Grammars",
annote="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.",
address="NEUVEDEN",
chapter="49470",
edition="NEUVEDEN",
howpublished="print",
institution="NEUVEDEN",
journal="Theoretical Computer Science",
number="1",
volume="410",
year="2009",
month="january",
pages="108--112",
publisher="NEUVEDEN",
type="journal article in Web of Science"
}