Hide and seek with repetitions
| Autor: | Florin Manea, Paweł Gawrychowski, Dirk Nowotka, Robert Mercaş |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
General Computer Science
Repetition (rhetorical device) Computer Networks and Communications Computer science Generalization Applied Mathematics Existential quantification Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 02 engineering and technology Concatenation (mathematics) 01 natural sciences Theoretical Computer Science Combinatorics on words Morphism Computational Theory and Mathematics 010201 computation theory & mathematics 020204 information systems 0202 electrical engineering electronic engineering information engineering Pattern matching Arithmetic Computer Science::Formal Languages and Automata Theory Word (computer architecture) |
| Zdroj: | Journal of Computer and System Sciences. 101:42-67 |
| ISSN: | 0022-0000 |
| DOI: | 10.1016/j.jcss.2018.10.004 |
| Popis: | Pseudo-repetitions are a natural generalization of the classical notion of repetitions in sequences: they are the repeated concatenation of a word and its encoding under a certain morphism or antimorphism. Thus, such occurrences can be regarded as hidden repetitive structures of, or within, a word. We solve fundamental algorithmic questions on pseudo-repetitions by application of insightful combinatorial results on words. More precisely, we efficiently decide whether a word is a pseudo-repetition and find all the pseudo-repetitive factors of a word. We also approach the problem of deciding whether there exists an anti-/morphism for which a word is a pseudo-repetition. We show that some variants of this latter problem are efficiently solvable, while some others are NP-complete. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect