Detail publikace
n-Right-Linear #-Rewriting Systems
KŘIVKA, Z. MEDUNA, A. SMRČEK, J.
Originální název
n-Right-Linear #-Rewriting Systems
Anglický název
n-Right-Linear #-Rewriting Systems
Jazyk
en
Originální abstrakt
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.
Anglický abstrakt
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.
Dokumenty
BibTex
@inproceedings{BUT25352,
author="Zbyněk {Křivka} and Alexandr {Meduna} and Jaromír {Smrček}",
title="n-Right-Linear #-Rewriting Systems",
annote="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.",
address="Ing. Zdeněk Novotný, CSc.",
booktitle="Third Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2007)",
chapter="25352",
howpublished="print",
institution="Ing. Zdeněk Novotný, CSc.",
year="2007",
month="october",
pages="105--112",
publisher="Ing. Zdeněk Novotný, CSc.",
type="conference paper"
}