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

Volume

1

fYear

2006

fDate

20-24 June 2006

Firstpage

402

Lastpage

409

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer and Computational Sciences, 2006. IMSCCS '06. First International Multi-Symposiums on

Conference_Location

Hanzhou, Zhejiang

Print_ISBN

0-7695-2581-4

Type

conf

DOI

10.1109/IMSCCS.2006.60

Filename

4673581