An efficient algorithm to test square-freeness of strings compressed by straight-line programs
DOI10.1016/J.IPL.2012.06.017zbMATH Open1248.68575OpenAlexW1981704228MaRDI QIDQ456098FDOQ456098
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
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
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)
Cites Work
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String
- Title not available (Why is that?)
- An O(n log n) algorithm for finding all repetitions in a string
- Transducers and repetitions
- Processing Compressed Texts: A Tractability Border
- Efficient algorithms to compute compressed longest common substrings and compressed palindromes
- Efficient algorithms for Lempel-Ziv encoding
- ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS
- An efficient algorithm to test square-freeness of strings compressed by balanced straight line programs
Cited In (3)
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)
