Publication Details

n-Right-Linear #-Rewriting Systems

KŘIVKA Zbyněk, MEDUNA Alexander and SMRČEK Jaromír. 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, pp. 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 FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Smrček Jaromír, Ing. (FIT BUT)
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)
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{FITPUB8498,
   author = "Zbyn\v{e}k K\v{r}ivka and Alexander Meduna and Jarom\'{i}r Smr\v{c}ek",
   title = "n-Right-Linear \#-Rewriting Systems",
   pages = "105--112",
   booktitle = "Third Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2007)",
   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/8498"
}
Files
Back to top