Computing by commuting

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Název česky Počítání komutováním
Autoři

KARHUMÄKI Juhani KUNC Michal OKHOTIN Alexander

Rok publikování 2006
Druh Článek v odborném periodiku
Časopis / Zdroj Theoretical Computer Science
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://dx.doi.org/10.1016/j.tcs.2006.01.051
Obor Obecná matematika
Klíčová slova Rewriting systems; Regular languages; Commutation of languages; Rational relations
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.