Detail publikace

On the Descriptional Complexity of Scattered Context Grammars

MASOPUST, T.

Originální název

On the Descriptional Complexity of Scattered Context Grammars

Typ

článek v časopise ve Web of Science, Jimp

Jazyk

angličtina

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.

Klíčová slova

scattered context grammar; descriptional complexity.

Autoři

MASOPUST, T.

Rok RIV

2009

Vydáno

1. 1. 2009

ISSN

0304-3975

Periodikum

Theoretical Computer Science

Ročník

410

Číslo

1

Stát

Nizozemsko

Strany od

108

Strany do

112

Strany počet

5

URL

http://dx.doi.org/10.1016/j.tcs.2008.10.017

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