zbMATH — the first resource for mathematics

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].

68Q45 Formal languages and automata
Full Text: DOI