An efficient algorithm to test square-freeness of strings compressed by straight-line programs

DOI10.1016/J.IPL.2012.06.017zbMath1248.68575OpenAlexW1981704228MaRDI QIDQ456098

Hideo Bannai, Shunsuke Inenaga, Moshe Lewenstein, Travis Gagie, Gad M. Landau, Tomohiro I.

Publication date: 23 October 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2012.06.017

zbMATH Keywords

straight-line programsstring algorithmstext compressionrepetitions in stringsstring processing

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Related Items (2)

Access, Rank, and Select in Grammar-compressed Strings ⋮ Detecting regularities on grammar-compressed strings

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Transducers and repetitions
• An O(n log n) algorithm for finding all repetitions in a string
• ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS
• Processing Compressed Texts: A Tractability Border
• Efficient algorithms for Lempel-Ziv encoding
• An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String

This page was built for publication: An efficient algorithm to test square-freeness of strings compressed by straight-line programs