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
Masopust Tomáš, RNDr., Ph.D. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
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