From Nerode's congruence to suffix automata with mismatches

DOI10.1016/j.tcs.2009.03.011zbMath1176.68101DBLPjournals/tcs/CrochemoreEGM09OpenAlexW2057270258WikidataQ61677911 ScholiaQ61677911MaRDI QIDQ840766

Filippo Mignosi, A. Gabriele, Maxime Crochemore, Chiara Epifanio

Publication date: 14 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.011

zbMATH Keywords

indexingapproximate string matchingcombinatorics on wordslanguages with mismatchessuffix automata

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items (2)

Indexing a sequence for mapping reads with a single mismatch ⋮ Special factors and the combinatorics of suffix and factor automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new method for approximate indexing and dictionary lookup with one error
• The smallest automaton recognizing the subwords of a text
• Efficient string matching with k mismatches
• Data structures and algorithms for approximate string matching
• On-line construction of compact directed acyclic word graphs
• Transducers and repetitions
• Special issue: Average-case analysis of algorithms
• Reducing space for index implementation.
• Languages with mismatches
• Dictionary matching and indexing with errors and don't cares
• Algorithms on Strings, Trees and Sequences
• Text Indexing and Dictionary Matching with One Error
• Combinatorial Pattern Matching
• Algorithms on Strings
• Developments in Language Theory
• Combinatorial Pattern Matching
• Words and special factors

This page was built for publication: From Nerode's congruence to suffix automata with mismatches