Efficient Implementation for Deterministic Finite Tree Automata Minimization

Autor:	Younes Guellouma, Hadda Cherroun
Jazyk:	angličtina
Rok vydání:	2016
Předmět:	automata theory minimization trees asymptotic complexity Electronic computers. Computer science QA75.5-76.95
Zdroj:	Journal of Computing and Information Technology, Vol 24, Iss 4, Pp 311-322 (2016)
Druh dokumentu:	article
ISSN:	1330-1136 1846-3908
DOI:	10.20532/cit.2016.1002867
Popis:	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.
Databáze:	Directory of Open Access Journals
Externí odkaz:	https://doaj.org/article/d834d45a585c42eb8d4185a77f4dbfe1 Zobrazit plný text záznamu View record in DOAJ