×

An implementation of deterministic tree automata minimization. (English) Zbl 1139.68357

Holub, Jan (ed.) et al., Implementation and application of automata. 12th international conference, CIAA 2007, Prague, Czech Republic, July 16–18, 2007. Revised selected papers. Berlin: Springer (ISBN 978-3-540-76335-2/pbk). Lecture Notes in Computer Science 4783, 122-129 (2007).
Summary: A frontier-to-root deterministic finite-state tree automaton (DTA) can be used as a compact data structure to store collections of unranked ordered trees. DTAs are usually sparser than string automata, as most transitions are undefined and therefore, special care must be taken in order to minimize them efficiently. However, it is difficult to find simple and detailed descriptions of the minimization procedure in the published literature. Here, we fully describe a simple implementation of the standard minimization algorithm that needs a time in \(\mathcal{O}(|A|^2)\), with \(|A|\) being the size of the DTA.
For the entire collection see [Zbl 1137.68010].

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brainerd, W. S., The minimalization of tree automata, Information and Control, 13, 5, 484-491 (1968) · Zbl 0181.01602 · doi:10.1016/S0019-9958(68)90917-0
[2] Gécseg, F., Steinby, M.: Tree Automata. Akadémiai Kiadó, Budapest (1984) · Zbl 0537.68056
[3] Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (1997) release (October 1rst, 2002), available on http://www.grappa.univ-lille3.fr/tata
[4] Hopcroft, J.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Reading: Addison-Wesley, Reading · Zbl 0426.68001
[5] Blum, N., An O(n log n) implementation of the standard method for minimizing n-state finite automata, Information Processing Letters, 57, 2, 65-69 (1996) · Zbl 0875.68649 · doi:10.1016/0020-0190(95)00199-9
[6] Watson, B.W.: A taxonomy of finite automata minimization algorithmes. Computing Science Note 93/44, Eindhoven University of Technology, The Netherlands (1993)
[7] Marcus, M. P.; Santorini, B.; Marcinkiewicz, M., Building a large annotated corpus of english: the penn treebank, Computational Linguistics, 19, 313-330 (1993)
[8] Paige, R.; Tarjan, R. E., Three partition refinement algorithms, SIAM J. Computing, 16, 6, 973-989 (1987) · Zbl 0654.68072 · doi:10.1137/0216062
[9] Carrasco, R.C., Daciuk, J., Forcada, M.L.: Incremental construction of minimal tree automata (submitted, 2007) · Zbl 1180.68168
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.