Duplication-reduction.pdf (306.88 kB)
On the prefix-suffix duplication reduction
journal contribution
posted on 2018-05-08, 14:17 authored by Szilard Z. Fazekas, Robert MercasRobert Mercas, Daniel ReidenbachThis 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.
History
School
- Science
Department
- Computer Science
Published in
International Journal of Foundations of Computer ScienceVolume
31Issue
1Pages
91 - 102Citation
FAZEKAS, S.Z., MERCAS, R. and REIDENBACH, D., 2020. On the prefix-suffix duplication reduction. International Journal of Foundations of Computer Science, 31 (1), pp.91-102.Publisher
© World Scientific PublishingVersion
- AM (Accepted Manuscript)
Publisher statement
Electronic version of an article published as International Journal of Foundations of Computer Science, 31, 1, 2020, pp.91-102, https://doi.org/10.1142/S0129054120400067, © copyright World Scientific Publishing Company, https://www.worldscientific.com/worldscinet/ijfcs.Acceptance date
2019-05-05Publication date
2020-01-31Copyright date
2020ISSN
0129-0541eISSN
1793-6373Publisher version
Language
- en