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

DOI10.1016/J.IPL.2012.06.017MaRDI QIDQ456098zbMATH OpenOpenAlexFDO

Authors Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Gad M. Landau, Moshe Lewenstein, 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

string algorithmsstraight-line programstext 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)

Recommendations

• An efficient algorithm to test square-freeness of strings compressed by balanced straight line programs
• scientific article; zbMATH DE number 3913712
• Efficient parallel algorithms to test square-freeness and factorize strings
• Algorithmics on SLP-compressed strings: a survey
• ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS

Cites work

• scientific article; zbMATH DE number 3913712 (Why is no real title available?)
• An O(n log n) algorithm for finding all repetitions in a string
• An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String
• An efficient algorithm to test square-freeness of strings compressed by balanced straight line programs
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Efficient algorithms for Lempel-Ziv encoding
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS
• Processing Compressed Texts: A Tractability Border
• Transducers and repetitions

Cited in

(3)

• Access, rank, and select in grammar-compressed strings
• Detecting regularities on grammar-compressed strings
• An efficient algorithm to test square-freeness of strings compressed by balanced straight line programs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456098)