Informace o publikaci
Computing by commuting
| Název česky | Počítání komutováním |
|---|---|
| Autoři | |
| Rok publikování | 2006 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Theoretical Computer Science |
| Fakulta / Pracoviště MU | |
| 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: |