Factorizing strings into repetitions

DOI10.1007/S00224-022-10070-3MaRDI QIDQ2135631zbMATH OpenOpenAlexFDO

Authors Hiroe Inoue, Yoshiaki Matsuoka, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Publication date 9 May 2022

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-022-10070-3

zbMATH Keywords

dynamic programmingFibonacci stringsrepetition factorizationssquares

Mathematics Subject Classification ID

Theory of data (68Pxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Recommendations

• Largest repetition factorization of Fibonacci words
• Fast and Practical Algorithms for Computing All the Runs in a String
• Repetitions in Sturmian strings
• An O(n log n) algorithm for finding all repetitions in a string
• Repetitions and factor automata

Cites work

• A faster algorithm for computing maximal -gapped repeats in a string
• A subquadratic algorithm for minimum palindromic factorization
• A universal algorithm for sequential data compression
• Closed factorization
• Compression of individual sequences via variable-rate coding
• Computing longest previous factor in linear time and applications
• Computing palindromic factorizations and palindromic covers on-line
• Constructing LZ78 tries and position heaps in linear time for large alphabets
• Data compression via textual substitution
• Diverse Palindromic Factorization is NP-Complete
• Factorizing a String into Squares in Linear Time
• Factorizing words over an ordered alphabet
• Free differential calculus. IV: The quotient groups of the lower central series
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 871172 (Why is no real title available?)
• On prefix/suffix-square free words
• Palindromic length in linear time
• Searching of gapped repeats and subrepetitions in a word
• Squares, cubes, and time-space efficient string searching
• The ``runs theorem
• The exact number of squares in Fibonacci words
• Uniqueness Theorems for Periodic Functions

Cited in

(10)

• Computing equality-free and repetitive string factorisations
• scientific article; zbMATH DE number 6819809 (Why is no real title available?)
• Generic Algorithms for Factoring Strings
• Repetition Detection in a Dynamic String
• On string replacement exponentiation
• Largest repetition factorization of Fibonacci words
• Exploiting new properties of string net frequency for efficient computation
• Repetition factorization of automatic sequences
• Edit and alphabet-ordering sensitivity of lex-parse
• Net occurrences in Fibonacci and Thue-Morse words

This page was built for publication: Factorizing strings into repetitions

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