Transducers and repetitions
From MaRDI portal
Publication:1820587
DOI10.1016/0304-3975(86)90041-1zbMath0615.68053OpenAlexW2154104338WikidataQ61677987 ScholiaQ61677987MaRDI QIDQ1820587
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(86)90041-1
Related Items
A metric index for approximate string matching, Speeding up two string-matching algorithms, A Heuristic For Computing Repeats With A Factor Oracle: Application To Biological Sequences, A fast algorithm for finding the positions of all squares in a run-length encoded string, From Nerode's congruence to suffix automata with mismatches, General suffix automaton construction algorithm and space bounds, Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations, The number of runs in a string, On-line construction of suffix trees, An efficient algorithm for online square detection, La reconnaissance des facteurs d'un langage fini dans un texte en temps linéaire. (Recognition of the factors of a finite language in a text in linear time), On the Structure of Consistent Partitions of Substring Set of a Word, Covering a string, Online Detection of Repetitions with Backtracking, Matching a set of strings with variable length don't cares, On-line construction of position heaps, A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String, Parameterized DAWGs: efficient constructions and bidirectional pattern searches, Fast detection of specific fragments against a set of sequences, THE STRUCTURE OF FACTOR ORACLES, Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets, Efficient algorithms for three variants of the LPF table, Computing longest previous non-overlapping factors, Parallel construction of minimal suffix and factor automata, Efficient string matching on packed texts, An efficient algorithm to test square-freeness of strings compressed by straight-line programs, Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Efficient parallel algorithms to test square-freeness and factorize strings, Text searching allowing for inversions and translocations of factors, New simple efficient algorithms computing powers and runs in strings, A variation on the Boyer-Moore algorithm, A string-matching interpretation of the equation \(x^ m y^ n = z^ p\), Approximate string-matching with \(q\)-grams and maximal matches, Data compression with factor automata, WEIGHTED AUTOMATA FOR FULL-TEXT INDEXING, Efficient on-line repetition detection, Approximate string matching with suffix automata, Finding similar consensus between trees: An algorithm and a distance hierarchy, Computing longest previous factor in linear time and applications, Computing the longest previous factor, On-line construction of compact directed acyclic word graphs, Linear time algorithms for finding and representing all the tandem repeats in a string, The ``runs conjecture, Forty Years of Text Indexing, Ternary directed acyclic word graphs, Identifying consensus of trees through alignment, Special factors and the combinatorics of suffix and factor automata, The wide window string matching algorithm, On suffix extensions in suffix trees, La reconnaissance des facteurs d'un mot dans un texte, Minimal forbidden factors of circular words, A faster algorithm for matching a set of patterns with variable length don't cares, Lempel-Ziv factorization powered by space efficient suffix trees, Unnamed Item, Unnamed Item, Optimal parallel algorithms for periods, palindromes and squares, THE DESIGN PRINCIPLES AND ALGORITHMS OF A WEIGHTED GRAMMAR LIBRARY, Unnamed Item, Fully-online suffix tree and directed acyclic word graph construction for multiple texts, Speeding up two string-matching algorithms, Fibonacci arrays and their two-dimensional repetitions, A Linear-Time Algorithm for Seeds Computation, Repetitions in strings: algorithms and combinatorics, Minimisation of automata, Indexing text with approximate \(q\)-grams, Optimal discovery of repetitions in 2D, Reducing space for index implementation., ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The smallest automaton recognizing the subwords of a text
- Optimal off-line detection of repetitions in a string
- On the computational power of pushdown automata
- A fast string searching algorithm
- Efficient string matching
- A Space-Economical Suffix Tree Construction Algorithm
- Fast Pattern Matching in Strings
- Compression of individual sequences via variable-rate coding
- The theory of languages
