Detail publikace

On Descriptional Complexity of Partially Parallel Grammars

MASOPUST Tomáš a MEDUNA Alexander. On Descriptional Complexity of Partially Parallel Grammars. Fundamenta Informaticae, roč. 87, č. 3, 2008, s. 407-415. ISSN 0169-2968.
Název česky
O popisné složitosti částečně paralelních gramatik
Typ
článek v časopise
Jazyk
angličtina
Autoři
URL
Abstrakt

Článek upravuje některé výsledky týkající se popisné složitosti částečně paralelních gramatik. Ukazuje, že každý rekurzívně spočetný jazyk je generovaný gramatikou s rozptýleným kontextem se čtyřmi neterminály a ne více jak čtyřmi pravidly, která nejsou bezkontextová, multisekvenční gramatikou mající dva neterminály a dva selektory a multicontinuous gramatikou mající tři neterminály a dva selektory.

Rok
2008
Strany
407-415
Časopis
Fundamenta Informaticae, roč. 87, č. 3, ISSN 0169-2968
Vydavatel
IOS Press
UT WoS
000262368900006
BibTeX
@ARTICLE{FITPUB8605,
   author = "Tom\'{a}\v{s} Masopust and Alexander Meduna",
   title = "On Descriptional Complexity of Partially Parallel Grammars",
   pages = "407--415",
   journal = "Fundamenta Informaticae",
   volume = 87,
   number = 3,
   year = 2008,
   ISSN = "0169-2968",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8605"
}
Nahoru