Hide and seek with repetitions

DOI10.1016/J.JCSS.2018.10.004zbMath1410.68309OpenAlexW2602778071MaRDI QIDQ1713479

Florin Manea, Paweł Gawrychowski, Dirk Nowotka, Robert Mercaş

Publication date: 25 January 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2018.10.004

zbMATH Keywords

pattern matchingrepetitioncombinatorics on wordsstringologypseudo-repetition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items (2)

Primitive sets of words ⋮ Equations enforcing repetitions under permutations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding a homomorphism between two words is NP-complete
• An extension of the Lyndon-Schützenberger result to pseudoperiodic words
• The extended equation of Lyndon and Schützenberger
• On a special class of primitive words
• Cubic patterns with permutations
• Fine and Wilf’s Theorem and Pseudo-repetitions
• Generalised Lyndon-Schützenberger Equations
• Finding Pseudo-Repetitions
• Testing Generalised Freeness of Words
• PROPERTIES OF PSEUDO-PRIMITIVE WORDS AND THEIR APPLICATIONS
• The Avoidability of Cubes under Permutations
• Unary Patterns with Permutations
• Linear work suffix array construction
• A Minimal Periods Algorithm with Applications
• Algorithms on Strings, Trees and Sequences
• Discovering Hidden Repetitions in Words
• Uniqueness Theorems for Periodic Functions
• Algorithms on Strings

This page was built for publication: Hide and seek with repetitions