Fast equation automaton computation. (English) Zbl 1160.68416
Summary: The most efficient known construction of equation automaton is that due to J.-M. Champarnaud and D. Ziadi
[Theor. Comput. Sci. 289, No. 1, 137–163 (2002; Zbl 1061.68109)]. For a regular expression \(E\), it requires \(O(|E|^{2})\) time and space and is based on going from position automaton to equation automaton using c-continuations. This complexity is due to the sorting step that takes \(O(|E|^{2})\) time used to identify the identical sub-expressions of \(E\). In this paper, we present a more efficient construction of the equation automaton which avoids the sorting step and replaces it by a minimization of an acyclic finite deterministic automaton. We show that this minimization allows the identification of identical sub-expressions as well as the sorting step used in Champarnaud and Ziadi’s approach. Using the minimization we get \(O(|E|+|E|\cdot |\mathcal E_E|)\) time and space complexity where \(|\mathcal E_E|\) is the number of states of the equation automaton.
MSC:
| 68Q45 | Formal languages and automata |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R15 | Combinatorics on words |
| 68W30 | Symbolic computation and algebraic computation |
Citations:
Zbl 1061.68109References:
| [1] | Antimirov, V., Partial derivatives of regular expressions and finite automaton constructions, Theoret. Comput. Sci., 155, 291-319 (1996) · Zbl 0872.68120 |
| [2] | Brüggemann-Klein, A., Regular expressions into finite automata, Theoret. Comput. Sci., 120, 197-213 (1993) · Zbl 0811.68096 |
| [3] | Champarnaud, J.-M.; Ziadi, D., Canonical derivatives and finite automaton constructions, Theoret. Comput. Sci., 289, 137-163 (2002) · Zbl 1061.68109 |
| [4] | Champarnaud, J.-M.; Ziadi, D., From Mirkin’s prebases to Antimirov’s word partial derivatives, Fund. Inform., 45, 3, 195-205 (2001) · Zbl 0976.68098 |
| [5] | Chang, C.-H.; Paige, R., From regular expressions to DFA’s using compressed NFA’s, Theoret. Comput. Sci., 178, 1-36 (1997) · Zbl 0912.68105 |
| [6] | Mirkin, B. G., An algorithm for constructing a base in a language of regular expressions, Engrg. Cybernet., 5, 110-116 (1966) |
| [7] | J. Myhill, Finite automata and the representation of events, in: WADD TR-57-624, Wright Patterson AFB, Ohio, 1957, pp. 112-137; J. Myhill, Finite automata and the representation of events, in: WADD TR-57-624, Wright Patterson AFB, Ohio, 1957, pp. 112-137 |
| [8] | Nerode, A., Linear automata transformation, Proc. AMS, 9, 541-544 (1958) · Zbl 0089.33403 |
| [9] | Paige, R.; Tarjan, R. E., Three partition refinement algorithms, SIAM J. Comput., 16, 6 (1987) · Zbl 0654.68072 |
| [10] | Revuz, D., Minimization of acyclic deterministic automata in linear time, Theoret. Comput. Sci., 92, 1, 181-189 (1992), n27 · Zbl 0759.68066 |
| [11] | Yu, S., Regular languages, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. I, Words, Languages, Grammars (1997), Springer-Verlag: Springer-Verlag Berlin), 41-110 · Zbl 0866.68057 |
| [12] | 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.
