Deciding word neighborhood with universal neighborhood automata

作者：Mitankin Petar^*; Mihov Stoyan; Schulz Klaus U

来源：Theoretical Computer Science, 2011, 412(22): 2340-2355.

DOI：10.1016/j.tcs.2011.01.013

• Dynamic programming
• Finite state automata
• Levenshtein distance

Given some form of distance between words, a fundamental operation is to decide whether the distance between two given words to and v is within a given bound. In earlier work, we introduced the concept of a universal Levenshtein automaton for a given distance bound n. This deterministic automaton takes as input a sequence chi of bitvectors computed from w and v. The sequence chi is accepted iff the Levenshtein distance between to and v does not exceed n. The automaton is called universal since the same automaton can be used for arbitrary input words in and v, regardless of the underlying input alphabet. Here, we extend this picture. After introducing a large abstract family of generalized word distances, we exactly characterize those members where word neighborhood can be decided using universal neighborhood automata similar to universal Levenshtein automata. Our theoretical results establish several bridges to the theory of synchronized finite-state transducers and dynamic programming. For small neighborhood bounds, universal neighborhood automata can be held in main memory. This leads to very efficient algorithms for the above decision problem. Evaluation results show that these algorithms are much faster than those based on dynamic programming.

• 出版日期2011-5-13