Publication detail

n-Right-Linear #-Rewriting Systems

KŘIVKA, Z. MEDUNA, A. SMRČEK, J.

Original Title

n-Right-Linear #-Rewriting Systems

English Title

n-Right-Linear #-Rewriting Systems

Type

conference paper

Language

en

Original 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.

English 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.

Keywords

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

RIV year

2007

Released

26.10.2007

Publisher

Ing. Zdeněk Novotný, CSc.

Location

Znojmo

ISBN

978-80-7355-077-6

Book

Third Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2007)

Pages from

105

Pages to

112

Pages count

8

Documents

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"
}