English»Algorithms»Finite State Automata and Regular Expressions | searchivarius.org
log in | about 
  
Top level » Algorithms » Finite State Automata and Regular Expressions

A finite state machine (FSM) or finite state automaton (plural: automata) is a model of behavior composed of states, transitions and actions. A state stores information about the past, i.e. it reflects the input changes from the system start to the present moment. A transition indicates a state change and is described by a condition that would need to be fulfilled to enable the transition Read more

Fast Approximate Search in Large Dictionaries  S. Mihov, K. Schulz - Approximate dictionary searching on the top of Universal Levenshtein automata. In addition, authors try important acceleration algorithms such as pattern partitioning and the technique of Mor and Fraenkel.
Incremental Construction of Finite-State Automata and Transducers, and their Use in the Natural Language Processing  Jan Daciuk - Ph.D of Jan Daciuk devoted to the algorithms of fast construction of minimal automata.
A Partial Deterministic Automaton for Approximate String Matching  Gonzalo Navarro - An approach based on a deterministic finite state automaton can achieve O(N)running time. However, the exponential dependence of the number of states on the pattern size and the maximal allowed edit distance limits its practicality. The author studies the idea of "lazy" automaton creation: states of the automaton are created "on the fly" while scanning a text.
Fast String Correction with Levenshtein Automata  K. Schulz, S. Mihov - A description of Universal Levenshtein Automaton.
Implementing Regular Expressions  Russ Cox -

The page collects resources about implementing regular expression search efficiently, including the well-known article: “Regular Expression Matching Can Be Simple And Fast”