Result Details

Descriptional Complexity of Multi-Parallel Grammars

MASOPUST, T. Descriptional Complexity of Multi-Parallel Grammars. INFORMATION PROCESSING LETTERS, 2008, vol. 108, no. 2, p. 68-70. ISSN: 0020-0190.
Type
journal article
Language
English
Authors
Masopust Tomáš, doc. RNDr., Ph.D., DIFS (FIT)
Abstract

This paper studies the descriptional complexity of multi-parallel grammars with respect to the number of nonterminals and selectors, and the length of these selectors. As a result, it proves that every recursively enumerable language is generated by a multi-parallel grammar with no more than seven nonterminals and four selectors of length five.

Keywords

formal languages, multi-parallel grammars, descriptional complexity

URL
Published
2008
Pages
68–70
Journal
INFORMATION PROCESSING LETTERS, vol. 108, no. 2, ISSN 0020-0190
UT WoS
000259435800005
BibTeX 
@article{BUT48168,
  author="Tomáš {Masopust}",
  title="Descriptional Complexity of Multi-Parallel Grammars",
  journal="INFORMATION PROCESSING LETTERS",
  year="2008",
  volume="108",
  number="2",
  pages="68--70",
  issn="0020-0190",
  url="http://dx.doi.org/10.1016/j.ipl.2008.04.002"
}
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