Detail výsledku

On the Descriptional Complexity of Scattered Context Grammars

MASOPUST, T. On the Descriptional Complexity of Scattered Context Grammars. Theoretical Computer Science, 2009, vol. 410, no. 1, p. 108-112. ISSN: 0304-3975.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D., UIFS (FIT)
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.

URL
Rok
2009
Strany
108–112
Časopis
Theoretical Computer Science, roč. 410, č. 1, ISSN 0304-3975
UT WoS
000262997100011
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"
}
Projekty
Výzkum informačních technologií z hlediska bezpečnosti, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, zahájení: 2007-01-01, ukončení: 2013-12-31, řešení
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru