Result Details

On Descriptional Complexity of Partially Parallel Grammars

MASOPUST, T.; MEDUNA, A. On Descriptional Complexity of Partially Parallel Grammars. FUNDAMENTA INFORMATICAE, 2008, vol. 87, no. 3, p. 407-415. ISSN: 0169-2968.
Type
journal article
Language
English
Authors
Masopust Tomáš, doc. RNDr., Ph.D., DIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Abstract

In this paper, we improve some well-known results concerningdescriptional complexity of partially parallel grammars. Specifically,we prove that every recursively enumerable language is generated by afour-nonterminal scattered context grammar with no more than fournon-context-free productions, by a two-nonterminal multisequentialgrammar with no more than two selectors, or by a three-nonterminalmulticontinuous grammar with no more than two selectors.

Keywords

formal languages, scattered context grammars, multisequential grammars, multicontinuous grammars, descriptional complexity

URL
Published
2008
Pages
407–415
Journal
FUNDAMENTA INFORMATICAE, vol. 87, no. 3, ISSN 0169-2968
UT WoS
000262368900006
BibTeX 
@article{BUT49466,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="On Descriptional Complexity of Partially Parallel Grammars",
  journal="FUNDAMENTA INFORMATICAE",
  year="2008",
  volume="87",
  number="3",
  pages="407--415",
  issn="0169-2968",
  url="http://fi.mimuw.edu.pl/vol87.html"
}
Projects
Multi-Information Technologies, GACR, Standardní projekty, GA201/07/0005, start: 2007-01-01, end: 2009-12-31, completed
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