Efficient Implementation for Deterministic Finite Tree Automata Minimization

Younes Guellouma, Hadda Cherroun

Abstract


We address the problem of deterministic finite tree automata (DFTA) minimization. We describe a new alternative to implement both standard and incremental tree automata minimization using a well-defined graph representing the automaton to be minimized. We show that the asymptotic complexity of the standard implementation is linearithmic and the incremental one is O(n^3 log (n)) where n is the DFTA size.

Keywords


automata theory, minimization, trees, asymptotic complexity

Full Text:

PDF


DOI: https://doi.org/10.20532/cit.2016.1002867

Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

Crossref Similarity Check logo

Crossref logologo_doaj