2016 | OriginalPaper | Chapter
Reduction of Nondeterministic Tree Automata
Authors : Ricardo Almeida, Lukáš Holík, Richard Mayr
Published in: Tools and Algorithms for the Construction and Analysis of Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
EXPTIME
-complete, we describe methods to compute good approximations in polynomial time.libvata
tree automata library, and tested its performance on a given collection of tree automata from various applications of libvata
in regular model checking and shape analysis, as well as on various classes of randomly generated tree automata. Our algorithm yields substantially smaller and sparser automata than all previously known reduction techniques, and it is still fast enough to handle large instances.