J 2010

Computational power of two stacks with restricted communication

KARHUMÄKI, Juhani; Michal KUNC a Alexander OKHOTIN

Základní údaje

Originální název

Computational power of two stacks with restricted communication

Název česky

Výpočetní síla dvou zásobníků s omezenou komunikací

Autoři

KARHUMÄKI, Juhani; Michal KUNC a Alexander OKHOTIN

Vydání

Information and Computation, Amsterdam, Elsevier, 2010, 0890-5401

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Nizozemské království

Utajení

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

Odkazy

Impakt faktor

Impact factor: 0.825

Kód RIV

RIV/00216224:14310/10:00042811

Organizační jednotka

Přírodovědecká fakulta

UT WoS

000281456800005

Klíčová slova anglicky

Word rewriting; String rewriting; Post systems; Multi-pushdown machines; Communication; Universality

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 25. 8. 2010 14:13, doc. Mgr. Michal Kunc, Ph.D.

Anotace

ORIG CZ

V originále

Rewriting systems working on words with a center marker are considered. The derivation is done by erasing a prefix or a suffix and then adding a prefix or a suffix. This models a communication of two stacks according to a fixed protocol defined by the choice of rewriting rules. The paper systematically considers different cases of these systems and determines their expressive power. Several cases are identified where very restricted communication surprisingly yields computational universality.

Česky

V práci jsou studovány přepisovací systémy pracující na slovech se středovou značkou. Odvozování se provádí umazáním prefixu nebo sufixu a následným přidáním prefixu nebo sufixu. Toto odvozování modeluje komunikaci dvou zásobníků podle daného protokolu určeného volbou přepisovacích pravidel. V práci jsou systematicky uvažovány různé varianty těchto systémů a je určena jejich vyjadřovací síla. Je identifikováno několik případů, kde velmi omezená komunikace překvapivě poskytuje výpočetní univerzalitu.

Návaznosti

GA201/09/1313, projekt VaV
Název: Algebraické metody v teorii automatů a formálních jazyků II
Investor: Grantová agentura ČR, Algebraické metody v teorii automatů a formálních jazyků II
MSM0021622409, záměr
Název: Matematické struktury a jejich fyzikální aplikace
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury a jejich fyzikální aplikace