Result Details

Homogeneous Multicontinuous Grammars and Their Reduction

MEDUNA, A.; LUKÁŠ, R.; FIALA, J. Homogeneous Multicontinuous Grammars and Their Reduction. MEMICS 2007 Proceedings. Znojmo: Ing. Zdeněk Novotný, CSc., 2007. p. 90-96. ISBN: 978-80-7355-077-6.
Type
conference paper
Language
English
Authors
Meduna Alexandr, prof. RNDr., CSc., DIFS (FIT)
Lukáš Roman, Ing., Ph.D., DIFS (FIT)
Fiala Jiří, Ing., DIFS (FIT)
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.

Keywords

multicontinuous grammars, homogeneous grammars, descriptional complexity

Published
2007
Pages
90–96
Proceedings
MEMICS 2007 Proceedings
Conference
MEMICS'07 -- 3rd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
ISBN
978-80-7355-077-6
Publisher
Ing. Zdeněk Novotný, CSc.
Place
Znojmo
BibTeX 
@inproceedings{BUT26073,
  author="Alexandr {Meduna} and Roman {Lukáš} and Jiří {Fiala}",
  title="Homogeneous Multicontinuous Grammars and Their Reduction",
  booktitle="MEMICS 2007 Proceedings",
  year="2007",
  pages="90--96",
  publisher="Ing. Zdeněk Novotný, CSc.",
  address="Znojmo",
  isbn="978-80-7355-077-6"
}
Projects
Multi-Information Technologies, GACR, Standardní projekty, GA201/07/0005, start: 2007-01-01, end: 2009-12-31, completed
Security-Oriented Research in Information Technology, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, start: 2007-01-01, end: 2013-12-31, running
Research groups
Formal Model Research Group (RG FM)
Departments
Department of Information Systems (DIFS)
Back to top