Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Computing by commuting. / Karhumäki, Juhani; Kunc, Michal; Okhotin, Alexander.
в: Theoretical Computer Science, Том 356, № 1-2, 05.05.2006, стр. 200-211.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Computing by commuting
AU - Karhumäki, Juhani
AU - Kunc, Michal
AU - Okhotin, Alexander
PY - 2006/5/5
Y1 - 2006/5/5
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.
AB - 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.
KW - Commutation of languages
KW - Rational relations
KW - Regular languages
KW - Rewriting systems
UR - http://www.scopus.com/inward/record.url?scp=33645979324&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2006.01.051
DO - 10.1016/j.tcs.2006.01.051
M3 - Article
AN - SCOPUS:33645979324
VL - 356
SP - 200
EP - 211
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
IS - 1-2
ER -
ID: 41141201