Detail výsledku

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.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D., UIFS (FIT)
Meduna Alexandr, prof. RNDr., CSc., UIFS (FIT)
Abstrakt

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.

Klíčová slova

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

URL
Rok
2008
Strany
407–415
Časopis
FUNDAMENTA INFORMATICAE, roč. 87, č. 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"
}
Projekty
Multiinformační technologie, GAČR, Standardní projekty, GA201/07/0005, zahájení: 2007-01-01, ukončení: 2009-12-31, ukončen
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