Publication Details
Homogeneous Multicontinuous Grammars and Their Reduction
MEDUNA Alexander, LUKÁŠ Roman and FIALA Jiří. Homogeneous Multicontinuous Grammars and Their Reduction. In: MEMICS 2007 Proceedings. Znojmo: Ing. Zdeněk Novotný, CSc., 2007, pp. 90-96. ISBN 978-80-7355-077-6.
Czech title
Homogenní rozšířené multigramatiky a jejich redukce
Type
conference paper
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Lukáš Roman, Ing., Ph.D. (DIFS FIT BUT)
Fiala Jiří, Ing. (DIFS FIT BUT)
Lukáš Roman, Ing., Ph.D. (DIFS FIT BUT)
Fiala Jiří, Ing. (DIFS FIT BUT)
Keywords
multicontinuous grammars, homogeneous grammars, descriptional complexity
Abstract
This paper discusses homogeneous multicontinuous grammars in which each selector has all its activated parts identical. It is demonstrated that every recursive enumerable language is generated by a homogeneous five-nonterminal
multicontinuous grammar that has no more than five selectors and each of these selectors contains no more than two activated parts.
Published
2007
Pages
90-96
Proceedings
MEMICS 2007 Proceedings
Conference
MEMICS'07 -- 3rd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Znojmo, CZ
ISBN
978-80-7355-077-6
Publisher
Ing. Zdeněk Novotný, CSc.
Place
Znojmo, CZ
BibTeX
@INPROCEEDINGS{FITPUB8532, author = "Alexander Meduna and Roman Luk\'{a}\v{s} and Ji\v{r}\'{i} Fiala", title = "Homogeneous Multicontinuous Grammars and Their Reduction", pages = "90--96", booktitle = "MEMICS 2007 Proceedings", year = 2007, location = "Znojmo, CZ", publisher = "Ing. Zden\v{e}k Novotn\'{y}, CSc.", ISBN = "978-80-7355-077-6", language = "english", url = "https://www.fit.vut.cz/research/publication/8532" }