Implementation of algorithms from the paper
Monoid machines: a O(log n) parser for regular languages
Armando B. Matos
2006
Supplies parse functions which convert the input DFA into its
corresponding transitional monoid representation and parses the input string
according to the algorithms outlined in the paper.
p prefixes indicate paralell methods
The sequential algorithm runs in linear time in the input word size and the
parallel algorithm approaches logarithmic time as the number of processes increases.
See the file for a write up including an example and pertinent definitions from the paper.
Use:
Use either the parse or pparse functions to parse an input word by converting the input DFA to its
transitional monoid and running the algorithm.
Can create DFA accept function on input, or use supplied createAccept' finals start to create one for you.
Enjoy!
*Idiomatic Haskell edits and parallel implementation by Samuel Schlesinger.
----------------------------------------------------------------------------
An OCaml implementation of sequential algorithm has been added as well.