Skoči na glavni sadržaj

Izvorni znanstveni članak

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


Puni tekst: engleski pdf 353 Kb

str. 311-322

preuzimanja: 468

citiraj


Sažetak

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.

Ključne riječi

automata theory, minimization, trees, asymptotic complexity

Hrčak ID:

173010

URI

https://hrcak.srce.hr/173010

Posjeta: 716 *