Prefix-suffix square reduction (Q2358680): Difference between revisions

The paper introduces an operation on words called the ``prefix-suffix square reduction''. This operation could be seen as the inverse of another operation on words, already studied in the literature, known as ``prefix-suffix duplication''. A ``square'' is a word of the form \(uu\) with \(u\) a nonempty word. A ``prefix'' (resp. ``suffix'') of a word \(w\) is a word \(u\) such that \(w = uv\) (resp. \(w = vu\)) for a certain word \(v\). The ``prefix square reduction'' of a word \(w\) is defined as the set of all possible words obtained by replacing a prefix of \(w\) that is a square by one of its halves, that is, \[ \{ uv \; | \; w = uuv \text{ with } u \text{ nonempty} \}. \] The ``suffix square reduction'' is defined symmetrically. The ``prefix-suffix square reduction'' of a word \(w\) is just the union of the two previous sets. The authors define also the ``prefix-suffix square reduction'' of a language as the union of the prefix-square reductions of all words in the language. Bounded versions of these operations are also defined. Namely, given a positive integer \(p\), the ``\(p\)-prefix square reduction'' of a word \(w\) is the set \[ \{ uv \; | \; w = uuv \text{ with } u \text{ nonempty and such that } |u| \leq p \}. \] In a similar way the authors define the ``\(p\)-suffix square reduction'' and the ``\(p\)-prefix-suffix square reduction'' of a word as well as the ``\(p\)-prefix-suffix square reduction'' of a language. The authors prove several results concerning the complexity (in time and space) of the membership problem of a given language and the closure properties of some special classes of languages (regular, linear, context-free), both for the bounded and the unbounded case. Finally, the unbounded (resp. bounded) ``primitive prefix-suffix square root'' of a word \(w\) is defined as the word that can be obtained from \(w\) by iterated unbounded (resp. bounded) prefix-suffix square reductions and is irreducible, i.e., no further prefix or suffix square reduction can be applied. It is shown that, while the language of bounded primitive prefix-suffix square roots of all words over an alphabet is always regular, for the unbounded case, this language is regular only when the alphabet contains a single letter.