An optimal parallel algorithm to convert a regular expression into its Glushkov automaton

AbstractThe aim of this paper is to describe a CREW-PRAM optimal algorithm which converts a regular expression of size s into its Glushkov automaton in O(log s) time using O(s2log s) processors. This algorithm makes use of the star-normal form of an expression as defined by Brüggemann-Klein (1993) and is based on the sequential algorithm due to Ziadi et al. (1997) which computes an original representation of Glushkov automaton in O(s) time