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"
}