Efficient Construction of the Equation Automaton

Algorithms

Faissal Ouardi¹  Zineb Lotfi¹  Bilal Elghadyry¹ 

[1] Department of Computer Science, Faculty of Sciences, Mohammed V University in Rabat, Rabat 10000, Morocco;

关键词: regular expressions;    finite automata;    efficient algorithms;   

DOI  :  10.3390/a14080238

来源: DOAJ

【 摘 要 】

This paper describes a fast algorithm for constructing directly the equation automaton from the well-known Thompson automaton associated with a regular expression. Allauzen and Mohri have presented a unified construction of small automata and gave a construction of the equation automaton with time and space complexity in $O(mlogm+m^2)$, where m denotes the number of Thompson automaton transitions. It is based on two classical automata operations, namely epsilon-removal and Hopcroft’s algorithm for deterministic Finite Automata (DFA) minimization. Using the notion of c-continuation, Ziadi et al. presented a fast computation of the equation automaton in $O(m^2)$ time complexity. In this paper, we design an output-sensitive algorithm combining advantages of the previous algorithms and show that its computational complexity can be reduced to $O(m\times |Q_{{\equiv }_e}|)$, where $|Q_{{\equiv }_e}|$ denotes the number of states of the equation automaton, by an epsilon-removal and Bubenzer minimization algorithm of an Acyclic Deterministic Finite Automata (ADFA).

【 授权许可】

Unknown