An Investigation of Equivalent Serialized Forms of Parallel Finite Automata

The equivalence of non-deterministic finite automata, deterministic finite automata, regular expressions, and parallel finite automata with augmented regular expressions is used to relate parallel finite automata to the shuffle operation on regular languages. Our goal is to capitalize on the equivalence of regular expressions and augmented regular expressions to increase parallelization efficiency. We use the existing automated transformation algorithms for the various finite automata listed above to inform a transformation from augmented regular expressions to regular expressions. We then discuss the serialization of augmented regular expressions.