Article ID Journal Published Year Pages File Type
438114 Theoretical Computer Science 2009 8 Pages PDF
Abstract

In this paper we generalize the notion of an ι-symmetric word, from an antimorphic involution, to an arbitrary involution ι as follows: a nonempty word w is said to be ι-symmetric if w=αβ=ι(βα) for some words α,β. We propose the notion of ι-twin-roots (x,y) of an ι-symmetric word w. We prove the existence and uniqueness of the ι-twin-roots of an ι-symmetric word, and show that the left factor α and right factor β of any factorization of w as w=αβ=ι(βα), can be expressed in terms of the ι-twin-roots of w. In addition, we show that for any involution ι, the catenation of the ι-twin-roots of w equals the primitive root of w. We also provide several characterizations of the ι-twin-rots of a word, for ι being a morphic or antimorphic involution.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics