×

An optimal parallel algorithm to convert a regular expression into its Glushkov automaton. (English) Zbl 0915.68086

Summary: The 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(s^{2}/\log s)\) processors. This algorithm makes use of the star-normal form of an expression as defined by A. Brüggemann-Klein [Theor. Comput. Sci. 120, No. 2, 197-213 (1993; Zbl 0811.68096)] and is based on the sequential algorithm due to D. Ziadi, J.-L. Ponty and J.-M. Champarnaud [Bull. Belg. Math. Soc. – Simon Stevin 4, No. 1, 177-203 (1997)] which computes an original representation of Glushkov automaton in \(O(s)\) time.

MSC:

68W15 Distributed algorithms

Citations:

Zbl 0811.68096
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bar-On, I.; Vishkin, U., Optimal parallel generation of a computation tree form, (ACM Transactions on Programming Languages and Systems (1985)), 348-357 · Zbl 0564.68037
[2] Brüggemann-Klein, A., Regular expressions into finite automata, Theoret. Comput. Sci., 120, 197-213 (1993) · Zbl 0811.68096
[3] Chang, C.-H.; Paige, R., New theoretical and computational results for regular languages, (Apostolico; Crochemore; Galil; Manber, 3rd Ann. Symp. on Combinatorial Pattern Matching Proc.. 3rd Ann. Symp. on Combinatorial Pattern Matching Proc., Lecture Notes in Computer Science, vol. 644 (1992), Springer: Springer Berlin), 88-108
[4] Gibbons, A. M.; Rytter, W., Efficient Parallel Algorithms (1988), Cambridge University Press: Cambridge University Press Cambridge, MA · Zbl 0771.68015
[5] Glushkov, V. M., The abstract theory of automata, Russian Math. Surveys, 16, 1-53 (1961) · Zbl 0104.35404
[6] Hopcroft, J. E.; Ullman, J., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[7] McNaughton, R.; Yamada, H., Regular expression and state graphs for automata, IRA Trans. Electron. Comput. EC-9, 1, 39-47 (1960) · Zbl 0156.25501
[8] Ponty, J.-L.; Ziadi, D.; Champarnaud, J.-M., A new quadratic algorithm to convert a regular expression into an automaton, (Raymond, D.; Wood, D., First Workshop on Implementing Automata, WIA’96. First Workshop on Implementing Automata, WIA’96, London-Ontario. First Workshop on Implementing Automata, WIA’96. First Workshop on Implementing Automata, WIA’96, London-Ontario, Lecture Notes in Computer Science (1997), Springer: Springer Berlin), to appear · Zbl 0949.68090
[9] Rytter, W., A note on parallel transformations of regular expressions to nondeterministic finite automata, Inform. Process. Lett., 31, 103-109 (1989) · Zbl 0682.68060
[10] Sedgewick, R., Algorithms (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0529.68002
[11] Thompson, K., Regular expression search algorithms, Common ACM, 11, 6, 419-422 (1968) · Zbl 0164.46205
[12] Watson, B., Taxonomies and toolkits of regular language algorithms, (CIP-DATA Koninklijke Bibliotheek, Den Haag. CIP-DATA Koninklijke Bibliotheek, Den Haag, Ph.D. Thesis (1995), Eindhoven University of Technology) · Zbl 0832.68064
[13] Ziadi, D., Algorithmique parallèle et séquentielle des automates, (Thèse de doctorat (1996), Université de Rouen)
[14] Ziadi, D.; Ponty, J.-L.; Champarnaud, J.-M., Passage d’une expression rationnelle à un automate fini non-déterministe, Bull. Belg. Math. Soc., 4, 177-203 (1997) · Zbl 0915.68123
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.