a 2009

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

KŘIVKA, Zbyněk a Tomáš MASOPUST

Základní údaje

Originální název

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

Autoři

KŘIVKA, Zbyněk a Tomáš MASOPUST

Vydání

11th Italian Conference on Theoretical Computer Science, 2009

Další údaje

Jazyk

angličtina

Typ výsledku

Konferenční abstrakt

Obor

10201 Computer sciences, information science, bioinformatics

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

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

Příznaky

Mezinárodní význam
Změněno: 15. 10. 2009 16:41, doc. RNDr. Tomáš Masopust, Ph.D., DSc.

Anotace

ORIG CZ

V originále

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.

Česky

Článek diskutuje vliv kooperace na generativní sílu přepisovacích systémů s jistým mechanismem zajištujícím ověřování kontextových závislostí reprezentovaným pomocí random kontext gramatik. Zejména diskutuje kooperaci v souvislosti s kooperujícími a distributivními gramatickými systémy s ohledem na známé derivační protokoly a ukazuje, že ačkoliv je kooperace dostatečně silná na to, aby zvýšila generativní sílu jak povolujících, tak i zakazujících gramatik, nemá žádný vliv na generativní sílu random kontext gramatik. Zároveň jsou diskutovýny dvě možné definice relace přímé derivace užívané v literatuře.