Další formáty:
BibTeX
LaTeX
RIS
@article{800005, author = {Masopust, Tomáš and Meduna, Alexander}, article_location = {Polsko}, article_number = {3}, keywords = {formal languages, scattered context grammars, multisequential grammars, multicontinuous grammars, descriptional complexity}, issn = {0169-2968}, journal = {Fundamenta Informaticae}, title = {On Descriptional Complexity of Partially Parallel Grammars}, url = {http://fi.mimuw.edu.pl/vol87.html}, volume = {87}, year = {2008} }
TY - JOUR ID - 800005 AU - Masopust, Tomáš - Meduna, Alexander PY - 2008 TI - On Descriptional Complexity of Partially Parallel Grammars JF - Fundamenta Informaticae VL - 87 IS - 3 SP - 407-415 EP - 407-415 PB - IOS Press, Nizozemí SN - 01692968 KW - formal languages, scattered context grammars, multisequential grammars, multicontinuous grammars, descriptional complexity UR - http://fi.mimuw.edu.pl/vol87.html N2 - In this paper, we improve some well-known results concerning descriptional complexity of partially parallel grammars. Specifically, we prove that every recursively enumerable language is generated by a four-nonterminal scattered context grammar with no more than four non-context-free productions, by a two-nonterminal multisequential grammar with no more than two selectors, or by a three-nonterminal multicontinuous grammar with no more than two selectors. ER -
MASOPUST, Tomáš a Alexander MEDUNA. On Descriptional Complexity of Partially Parallel Grammars. \textit{Fundamenta Informaticae}. Polsko: IOS Press, Nizozemí, 2008, roč.~87, č.~3, s.~407-415. ISSN~0169-2968.
|