A fast implementation of incremental minimization of tree automata

We address the problem of minimizing tree automata especially its incremental version. Unlike the classical minimization, incremental version [1] computes equivalences between states in the safe way, like that the algorithm may be halted at any moment, returning a partially minimized tree automata....

Full description

Saved in:
Bibliographic Details
Main Authors: Guellouma, Y., Cherroun, H., Ziadi, D., Nehar, A.
Format: Conference Proceeding
Language:English
Subjects:
Automata
Complexity theory
Context
Deterministic Tree Automata
Electronic mail
Equivalence relation
Merging
Minimization
Partitioning algorithms
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We address the problem of minimizing tree automata especially its incremental version. Unlike the classical minimization, incremental version [1] computes equivalences between states in the safe way, like that the algorithm may be halted at any moment, returning a partially minimized tree automata. However, this incremental version has worse time complexity compared with the classical one which runs in quadratic time of the tree automata size. The purpose of this paper is to improve the implementation of the incremental version. This improvement relies on classical properties of equivalence relations and some implementation tricks.
DOI:10.1109/INNOVATIONS.2012.6207759