Transducers and repetitions

DOI10.1016/0304-3975(86)90041-1zbMATH Open0615.68053DBLPjournals/tcs/Crochemore86OpenAlexW2154104338WikidataQ61677987 ScholiaQ61677987MaRDI QIDQ1820587FDOQ1820587

Maxime Crochemore

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

zbMATH Keywords

Algorithmsfactor transducer of a wordrepetition searching in wordssubsequential suffix transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient string matching
• Compression of individual sequences via variable-rate coding
• On the computational power of pushdown automata
• Optimal off-line detection of repetitions in a string
• A fast string searching algorithm
• A Space-Economical Suffix Tree Construction Algorithm
• Fast Pattern Matching in Strings
• The smallest automaton recognizing the subwords of a text
• The theory of languages

Cited In (71)

• On the Structure of Consistent Partitions of Substring Set of a Word
• Speeding up two string-matching algorithms
• Fast detection of specific fragments against a set of sequences
• Forty Years of Text Indexing
• A Heuristic For Computing Repeats With A Factor Oracle: Application To Biological Sequences
• Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets
• Title not available (Why is that?)
• THE DESIGN PRINCIPLES AND ALGORITHMS OF A WEIGHTED GRAMMAR LIBRARY
• Optimal discovery of repetitions in 2D
• Fully-online suffix tree and directed acyclic word graph construction for multiple texts
• Identifying consensus of trees through alignment
• New simple efficient algorithms computing powers and runs in strings
• The ``runs conjecture
• Efficient algorithms for three variants of the LPF table
• Transducers with Origin Information
• ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS
• General suffix automaton construction algorithm and space bounds
• Approximate string-matching with \(q\)-grams and maximal matches
• An efficient algorithm for online square detection
• Finding similar consensus between trees: An algorithm and a distance hierarchy
• Computing longest previous factor in linear time and applications
• Ternary directed acyclic word graphs
• Special factors and the combinatorics of suffix and factor automata
• Parameterized DAWGs: efficient constructions and bidirectional pattern searches
• Approximate string matching with suffix automata
• On suffix extensions in suffix trees
• From Nerode's congruence to suffix automata with mismatches
• 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)
• A faster algorithm for matching a set of patterns with variable length don't cares
• Minimal forbidden factors of circular words
• A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String
• Minimisation of automata
• Matching a set of strings with variable length don't cares
• Lempel-Ziv factorization powered by space efficient suffix trees
• A fast algorithm for finding the positions of all squares in a run-length encoded string
• La reconnaissance des facteurs d'un mot dans un texte
• Covering a string
• On-line construction of position heaps
• Indexing text with approximate \(q\)-grams
• Efficient parallel algorithms to test square-freeness and factorize strings
• A metric index for approximate string matching
• Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations
• The wide window string matching algorithm
• An efficient algorithm to test square-freeness of strings compressed by straight-line programs
• Repetitions in strings: algorithms and combinatorics
• Speeding up two string-matching algorithms
• Data compression with factor automata
• Title not available (Why is that?)
• Computing the longest previous factor
• Linear time algorithms for finding and representing all the tandem repeats in a string
• On-line construction of compact directed acyclic word graphs
• A Linear-Time Algorithm for Seeds Computation
• Efficient on-line repetition detection
• Reducing space for index implementation.
• On-line construction of suffix trees
• Parallel construction of minimal suffix and factor automata
• Computing longest previous non-overlapping factors
• THE STRUCTURE OF FACTOR ORACLES
• Text searching allowing for inversions and translocations of factors
• A string-matching interpretation of the equation \(x^ m y^ n = z^ p\)
• A variation on the Boyer-Moore algorithm
• Optimal parallel algorithms for periods, palindromes and squares
• Title not available (Why is that?)
• The number of runs in a string
• Fibonacci arrays and their two-dimensional repetitions
• Online Detection of Repetitions with Backtracking
• Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
• Efficient string matching on packed texts
• Pseudo-minimal transducer
• WEIGHTED AUTOMATA FOR FULL-TEXT INDEXING
• Title not available (Why is that?)

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Iterating transducers 👍 👎
• Iterating transducers 👍 👎
• On Reversible Transducers 👍 👎
• Invertible Transducers, Iteration and Coordinates 👍 👎

This page was built for publication: Transducers and repetitions

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