Result Details

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.
Type
journal article
Language
English
Authors
Masopust Tomáš, doc. RNDr., Ph.D., DIFS (FIT)
Abstract

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.

Keywords

scattered context grammar; descriptional complexity.

URL
Published
2009
Pages
108–112
Journal
Theoretical Computer Science, vol. 410, no. 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"
}
Projects
Security-Oriented Research in Information Technology, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, start: 2007-01-01, end: 2013-12-31, running
Research groups
Formal Model Research Group (RG FM)
Departments
Department of Information Systems (DIFS)
Back to top