File(s) under embargo

Reason: Publisher requirement

97

days

2

hours

until file(s) become available

On the prefix-suffix duplication reduction

journal contribution
posted on 08.05.2018 by Szilard Z. Fazekas, Robert Mercas, Daniel Reidenbach
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.

History

School

  • Science

Department

  • Computer Science

Published in

International Journal of Foundations of Computer Science

Volume

31

Issue

1

Pages

91 - 102

Citation

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 Publishing

Version

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

05/05/2019

Publication date

2020-01-31

Copyright date

2020

ISSN

0129-0541

eISSN

1793-6373

Language

en

Exports

Logo branding

Keyword(s)

Exports