Computing by commuting

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

KARHUMÄKI Juhani KUNC Michal OKHOTIN Alexander

Year of publication 2006
Type Article in Periodical
Magazine / Source Theoretical Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Web http://dx.doi.org/10.1016/j.tcs.2006.01.051
Field General mathematics
Keywords Rewriting systems; Regular languages; Commutation of languages; Rational relations
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.