A study of some easily parallellizable automata
Sylvie Hamel · Advances in intelligent systems research/Advances in Intelligent Systems Research · 2006
A vector algorithm is an algorithm that applies a bounded number of vector operations to an input vector, regardless of the length of the input.The allowable operations are usually restricted to bit-wise operations available in processors, including shifts and binary addition with carry.This paper studies automata for which it is easy to derive a vector algorithm to compute the sequence of states visited by the automata on a given input sequence.A special case of these automata, shellable automata, is used in pattern matching problems on biological sequences [2].