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)

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"
}