Other formats:
BibTeX
LaTeX
RIS
@article{634090,
author = {Karhumäki, Juhani and Kunc, Michal and Okhotin, Alexander},
article_location = {Amsterdam},
article_number = {1-2},
keywords = {Rewriting systems; Regular languages; Commutation of languages; Rational relations},
language = {eng},
issn = {0304-3975},
journal = {Theoretical Computer Science},
title = {Computing by commuting},
url = {http://dx.doi.org/10.1016/j.tcs.2006.01.051},
volume = {356},
year = {2006}
}
TY - JOUR
ID - 634090
AU - Karhumäki, Juhani - Kunc, Michal - Okhotin, Alexander
PY - 2006
TI - Computing by commuting
JF - Theoretical Computer Science
VL - 356
IS - 1-2
SP - 200
EP - 200
PB - Elsevier
SN - 03043975
KW - Rewriting systems
KW - Regular languages
KW - Commutation of languages
KW - Rational relations
UR - http://dx.doi.org/10.1016/j.tcs.2006.01.051
N2 - 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.
ER -
KARHUMÄKI, Juhani, Michal KUNC and Alexander OKHOTIN. Computing by commuting. \textit{Theoretical Computer Science}. Amsterdam: Elsevier, 2006, vol.~356, 1-2, p.~200-211. ISSN~0304-3975.
|
