Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Dynamic programming for reduced NFAs for approximate string and sequence matching

Jan Holub — 2002

Kybernetika

searching for all occurrences of a pattern (string or sequence) in some text, where the pattern can occur with some limited number of errors given by edit distance. Several methods were designed for the approximate string matching that simulate nondeterministic finite automata (NFA) constructed for this problem. This paper presents reduced NFAs for the approximate string matching usable in case, when we are interested only in occurrences having edit distance less than or equal to a given integer,...

The finite automata approaches in stringology

Jan Holub — 2012

Kybernetika

We present an overview of four approaches of the finite automata use in stringology: deterministic finite automaton, deterministic simulation of nondeterministic finite automaton, finite automaton as a model of computation, and compositions of finite automata solutions. We also show how the finite automata can process strings build over more complex alphabet than just single symbols (degenerate symbols, strings, variables).

Page 1

Download Results (CSV)