Detailed Information on Publication Record
2006
Computing by commuting
KARHUMÄKI, Juhani, Michal KUNC and Alexander OKHOTINBasic information
Original name
Computing by commuting
Name in Czech
Počítání komutováním
Authors
KARHUMÄKI, Juhani (246 Finland), Michal KUNC (203 Czech Republic, guarantor) and Alexander OKHOTIN (643 Russian Federation)
Edition
Theoretical Computer Science, Amsterdam, Elsevier, 2006, 0304-3975
Other information
Language
English
Type of outcome
Článek v odborném periodiku
Field of Study
10101 Pure mathematics
Country of publisher
Netherlands
Confidentiality degree
není předmětem státního či obchodního tajemství
References:
Impact factor
Impact factor: 0.843
RIV identification code
RIV/00216224:14330/06:00016786
Organization unit
Faculty of Informatics
UT WoS
000237197900017
Keywords in English
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.
In Czech
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.
Links
| 1M0545, research and development project |
|