Publication Details

n-Right-Linear #-Rewriting Systems

KŘIVKA, Z.; MEDUNA, A.; SMRČEK, J. n-Right-Linear #-Rewriting Systems. In Third Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2007). Znojmo: Ing. Zdeněk Novotný, CSc., 2007. p. 105-112. ISBN: 978-80-7355-077-6.
Czech title
n-pravě-lineární #-přepisovací systémy
Type
conference paper
Language
English
Authors
Křivka Zbyněk, Ing., Ph.D. (DIFS)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Smrček Jaromír, Ing.
URL
Keywords

#-rewriting systems of finite index, right-linear #-rewriting systems, m-parallel n-right-linear simple matrix languages, infinite hierarchies of language families

Abstract

The present paper  discusses #-rewriting systems, which represent simple language-defining devices that combine both automata and grammars.  Indeed, like automata, they use finitely many states without any nonterminals; on the other hand, like grammars, they generate languages.  The paper introduces n-right-linear #-rewriting systems and characterize the infinite hierarchy of language families defined by m-parallel n-right-linear simple matrix grammars.  However, it also places some trivial restrictions on rewriting in these systems and demonstrates that under these restrictions, they generate only the family of right-linear languages. In its conclusion, this paper suggests some variants of #-rewriting systems.

Published
2007
Pages
105–112
Proceedings
Third Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2007)
ISBN
978-80-7355-077-6
Publisher
Ing. Zdeněk Novotný, CSc.
Place
Znojmo
BibTeX 
@inproceedings{BUT25352,
  author="Zbyněk {Křivka} and Alexandr {Meduna} and Jaromír {Smrček}",
  title="n-Right-Linear #-Rewriting Systems",
  booktitle="Third Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2007)",
  year="2007",
  pages="105--112",
  publisher="Ing. Zdeněk Novotný, CSc.",
  address="Znojmo",
  isbn="978-80-7355-077-6"
}
Back to top