Publication result detail

A Note on the Cooperation in Rewriting Systems with Context-Dependency Checking

KŘIVKA, Z.; MASOPUST, T.

Original Title

A Note on the Cooperation in Rewriting Systems with Context-Dependency Checking

English Title

A Note on the Cooperation in Rewriting Systems with Context-Dependency Checking

Type

Paper in proceedings outside WoS and Scopus

Original Abstract

This paper discusses the cooperation and its effect on the generative power of rewriting systems with some kind of simple context-dependency checking represented by the mechanism of random context grammars. Specifically, it discusses the cooperation in terms of cooperating distributed grammar systems with respect to all basic types of cooperation protocols, and proves that although the cooperation is powerful enough to increase the generative power of both permitting and forbidding random context grammars, it has no effect on the generative power of random context grammars. It also discusses two possible definitions of the relation of the direct derivation step used in the literature.

English abstract

This paper discusses the cooperation and its effect on the generative power of rewriting systems with some kind of simple context-dependency checking represented by the mechanism of random context grammars. Specifically, it discusses the cooperation in terms of cooperating distributed grammar systems with respect to all basic types of cooperation protocols, and proves that although the cooperation is powerful enough to increase the generative power of both permitting and forbidding random context grammars, it has no effect on the generative power of random context grammars. It also discusses two possible definitions of the relation of the direct derivation step used in the literature.

Keywords

context-dependency checking, cooperating distributed grammar systems, generative power

Key words in English

context-dependency checking, cooperating distributed grammar systems, generative power

Authors

KŘIVKA, Z.; MASOPUST, T.

Released

28.09.2009

Location

Cremona

Book

11th Italian Conference on Theoretical Computer Science

Pages from

129

Pages to

135

Pages count

7

URL

http://www.cremona.polimi.it/ictcs09/show_paper.php?id=1CT9r42bmF&progr=1

BibTex

@inproceedings{BUT91224,
  author="Zbyněk {Křivka} and Tomáš {Masopust}",
  title="A Note on the Cooperation in Rewriting Systems with Context-Dependency Checking",
  booktitle="11th Italian Conference on Theoretical Computer Science",
  year="2009",
  pages="129--135",
  address="Cremona",
  url="http://www.cremona.polimi.it/ictcs09/show_paper.php?id=1CT9r42bmF&progr=1"
}