Title :
Explicitly Parallel Regular Expressions
Author :
Estrade, Brett D. ; Perkins, A. Louise ; Harris, John M.
Author_Institution :
Center for Comput. & Technol., Louisiana State Univ., Baton Rouge, LA
Abstract :
The equivalence of non-deterministic finite automata (NFA ), deterministic finite automata (DFA), regular expressions (RE), and parallel finite automata (PFA) with augmented regular expressions (PRE) 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, as well as one of our own, to inform a transformation from augmented regular expressions to minimized deterministic finite automata (DFAmin). We then discuss the serialization of augmented regular expressions, and present a brief summary of potential applications, related research, and future directions
Keywords :
finite automata; formal languages; parallel algorithms; DFA; NFA deterministic finite automata; PFA; augmented parallel regular expression; automated transformation algorithm; nondeterministic finite automata; parallel finite automata; Automata; Computer science; Concurrent computing; Convergence; Doped fiber amplifiers; Instruction sets; Interleaved codes; Mathematics; Petri nets; State-space methods;
Conference_Titel :
Computer and Computational Sciences, 2006. IMSCCS '06. First International Multi-Symposiums on
Conference_Location :
Hanzhou, Zhejiang
Print_ISBN :
0-7695-2581-4
DOI :
10.1109/IMSCCS.2006.60
