File(s) under embargo
Reason: Publisher requirement
until file(s) become available
On the prefix-suffix duplication reduction
journal contributionposted on 08.05.2018 by Szilard Z. Fazekas, Robert Mercas, Daniel Reidenbach
Any type of content formally published in an academic journal, usually following a peer-review process.
This work answers some questions proposed by Bottoni, Labella, and Mitrana (Theoretical Computer Science 682, 2017) regarding the prefix–suffix reduction on words. The operation is defined as a reduction by one half of every square that is present as either a prefix or a suffix of a word, leading thus to a finite set of words associated to the starting one. The iterated case considers consecutive applications of the operations, on all the resulting words. We show that the classes of linear and context-free language are closed under iterated bounded prefix–suffix square reduction, and that for a given word we can determine in O(n2logn) time all of its primitive prefix–suffix square roots.
- Computer Science