Publication Details
n-Right-Linear #-Rewriting Systems
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Smrček Jaromír, Ing. (FIT BUT)
#-rewriting systems of finite index, right-linear #-rewriting systems, m-parallel n-right-linear simple matrix languages, infinite hierarchies of language families
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.
@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"
}