Detail publikačního výsledku

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

Druh

Článek WoS

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.

Klíčová slova

scattered context grammar; descriptional complexity.

Klíčová slova v angličtině

scattered context grammar; descriptional complexity.

Autoři

MASOPUST, T.

Rok RIV

2010

Vydáno

01.01.2009

ISSN

0304-3975

Periodikum

Theoretical Computer Science

Svazek

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