On the Prefix–Suffix Duplication Reduction

Autor:	Robert Mercaş, Daniel Reidenbach, Szilárd Zsolt Fazekas
Rok vydání:	2020
Předmět:	Combinatorics Reduction (complexity) Prefix Square root Iterated function Bounded function Computer Science (miscellaneous) Data_CODINGANDINFORMATIONTHEORY Suffix Word (computer architecture) Square (algebra) Mathematics
Zdroj:	International Journal of Foundations of Computer Science. 31:91-102
ISSN:	1793-6373 0129-0541
DOI:	10.1142/s0129054120400067
Popis:	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 [Formula: see text] time all of its primitive prefix–suffix square roots.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b68f55bc5b42746e2227db585753f02d https://doi.org/10.1142/s0129054120400067 Zobrazit plný text záznamu