Original scientific paper
https://doi.org/10.20532/cit.2016.1002867
Efficient Implementation for Deterministic Finite Tree Automata Minimization
Younes Guellouma
; Laboratoire LIM, Université Amar Telidji de Laghouat, Laghouat, Algérie
Hadda Cherroun
; Laboratoire LIM, Université Amar Telidji de Laghouat, Laghouat, Algérie
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(n3 log(n)) where n is the DFTA size.
Keywords
automata theory; minimization; trees; asymptotic complexity
Hrčak ID:
173010
URI
Publication date:
22.12.2016.
Visits: 1.000 *