| Summary: | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>m</mi><mspace width="3.33333pt"></mspace><mo form="prefix">log</mo><mspace width="3.33333pt"></mspace><mi>m</mi><mo>+</mo><msup><mi>m</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula>, where <i>m</i> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>m</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>m</mi><mo>×</mo><mo stretchy="false">|</mo><msub><mi>Q</mi><msub><mo>≡</mo><mi>e</mi></msub></msub><mo stretchy="false">|</mo><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mrow><mo stretchy="false">|</mo></mrow><msub><mi>Q</mi><msub><mo>≡</mo><mi>e</mi></msub></msub><mrow><mo stretchy="false">|</mo></mrow></mrow></semantics></math></inline-formula> denotes the number of states of the equation automaton, by an epsilon-removal and Bubenzer minimization algorithm of an Acyclic Deterministic Finite Automata (ADFA).
|
|---|