Approximate string matching using factor automata
type: Item
instance of: scholarly article
title: Approximate string matching using factor automata
zbMATH Open document ID: 0949.68088
DOI: 10.1016/S0304-3975(00)00064-5
published in: Theoretical Computer Science
publication date: 2000-10-26T00:00:00Z
review text: Given a text \(T\) over alphabet \(\Sigma\) and a complete index for \(T\) constructed using the finite automaton (called the factor automaton or DAWG) accepting all the substrings (factors) of text \(T.\) An answer to the query whether a pattern \(P\) occurs in text \(T\) with \(k\) differences is discussed to be done by an algorithm having the time complexity independent on the length of text \(T.\) The algorithm searches for the final state of the finite automaton accepting the intersection of languages \(\text{Fac}(T)\) (the set of all factors of \(T)\) and \(L_{k}(P)\) (the set of all strings having at most \(k\) differences with respect to pattern \(P\)).
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1521894
zbMATH Keywords: approximate pattern matching
zbMATH Keywords: finite automata
zbMATH Keywords: factor automata
zbMATH Keywords: DAWG
author: Jan Holub
author: Bořivoj Melichar
MaRDI profile type: Publication
cites work: Complete inverted files for efficient text retrieval and analysis
cites work: Q4849531
cites work: Q5592246
cites work: Algorithms for approximate string matching
full work available at URL: s0304-3975(00)00064-5
OpenAlex ID: W2033276056
description: scientific article; zbMATH DE number 1521894