2006
Computing by commuting
KARHUMÄKI, Juhani; Michal KUNC a Alexander OKHOTINZákladní údaje
Originální název
Computing by commuting
Název česky
Počítání komutováním
Autoři
KARHUMÄKI, Juhani; Michal KUNC a Alexander OKHOTIN
Vydání
Theoretical Computer Science, Amsterdam, Elsevier, 2006, 0304-3975
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.843
Kód RIV
RIV/00216224:14330/06:00016786
Organizační jednotka
Fakulta informatiky
UT WoS
000237197900017
Klíčová slova anglicky
Rewriting systems; Regular languages; Commutation of languages; Rational relations
Změněno: 16. 11. 2006 14:48, doc. Mgr. Michal Kunc, Ph.D.
V originále
We consider the power of the following rewriting: given a finite or regular set X of words and an initial word w, apply iteratively the operation which deletes a word from X from one of the ends of w and simultaneously catenates another word from X to the opposite end of w. We show that if the deletion is always done at the beginning and the catenation at the end, and the choice of a word to be catenated does not depend on the word erased, then the generated language is always regular, though the derivability relation is not, in general, rational. If the deletion and the catenation are done arbitrarily at the opposite ends, the language need not be regular. If the catenation is done at the same end as the deletion, the relation of derivability is rational even if the catenated word can depend on the word erased.
Česky
Zabýváme se silou následujícího přepisování: pro danou konečnou či regulární množinu slov X a počáteční slovo w aplikujeme iterativně operaci, která smaže slovo z X z jednoho konce w a současně připojí jiné slovo z X k opačnému konci w. Ukazujeme, že pokud je mazání vždy prováděno na začátku a připojování na konci a volba připojovaného slova nezávisí na volbě slova smazaného, potom je generovaný jazyk vždy regulární, přestože relace odvoditelnosti není obecně racionální. Jsou-li mazání a připojování prováděny libovolně na protilehlých koncích, generovaný jazyk nemusí být regulární. Je-li připojování prováděno na stejné straně jako mazání, relace odvoditelnosti je racionální dokonce pokud připojované slovo může záviset na slově mazaném.
Návaznosti
| 1M0545, projekt VaV |
|