Efficient Implementation for Deterministic Finite Tree Automata Minimization

Journal of computing and information technology

Cherroun, Hadda¹  Guellouma, Younes¹ 

[1] Laboratoire LIM, Université Amar Telidji de Laghouat, Laghouat, Algérie

关键词: automata theory;    minimization;    trees;    asymptotic complexity;   

DOI  :  10.20532/cit.2016.1002867

学科分类：计算机科学（综合）

来源: Sveuciliste u Zagrebu

【 摘 要 】

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.

【 授权许可】

CC BY