Publication Details

Reduction of Nondeterministic Tree Automata

HOLÍK, L.; ALMEIDA, R.; MAYR, R. Reduction of Nondeterministic Tree Automata. In Tools and Algorithms for the Construction and Analysis of Systems. Volume 9636 of the series Lecture Notes in Computer Science. Berlin Heidelberg: Springer Verlag, 2016. p. 717-735. ISBN: 978-3-662-49673-2.
Czech title
Redukce nedeterministických stromových automatů
Type
conference paper
Language
English
Authors
URL
Keywords

tree automata, reduction, simulation, lookahead simulation forward simulation, backward simulation

Abstract

We present an efficient algorithm to reduce the size of nondeterministic tree automata, while retaining their language. It is based on new transition pruning techniques, and quotienting of the state space w.r.t. suitable equivalences. It uses criteria based on combinations of downward and upward simulation preorder on trees, and the more general downward and upward language inclusions. Since tree-language inclusion is EXPTIME-complete, we describe methods to compute good approximations in polynomial time. We implemented our algorithm as a module of the well-known libvata tree automata library, and tested its performance on a given collection of tree automata from various applications of libvatain 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.

Annotation

We present an efficient algorithm to reduce the size of nondeterministic tree automata, while retaining their language. It is based on new transition pruning techniques, and quotienting of the state space w.r.t. suitable equivalences. It uses criteria based on combinations of downward and upward simulation preorder on trees, and the more general downward and upward language inclusions. Since tree-language inclusion is EXPTIME-complete, we describe methods to compute good approximations in polynomial time.

We implemented our algorithm as a module of the well-known libvata tree automata library, and tested its performance on a given collection of tree automata from various applications of libvatain 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.

Published
2016
Pages
717–735
Proceedings
Tools and Algorithms for the Construction and Analysis of Systems
Series
Volume 9636 of the series Lecture Notes in Computer Science
ISBN
978-3-662-49673-2
Publisher
Springer Verlag
Place
Berlin Heidelberg
DOI
UT WoS
000406428000046
EID Scopus
BibTeX
@inproceedings{BUT133495,
  author="Lukáš {Holík} and Ricardo {Almeida} and Richard {Mayr}",
  title="Reduction of Nondeterministic Tree Automata",
  booktitle="Tools and Algorithms for the Construction and Analysis of Systems",
  year="2016",
  series="Volume 9636 of the series Lecture Notes in Computer Science",
  pages="717--735",
  publisher="Springer Verlag",
  address="Berlin Heidelberg",
  doi="10.1007/978-3-662-49674-9\{_}46",
  isbn="978-3-662-49673-2",
  url="http://link.springer.com/chapter/10.1007%2F978-3-662-49674-9_46"
}
Back to top