gr10

Th. Genet, V. Rusu. Equational Approximations for Tree Automata Completion. Journal of Symbolic Computation, 45(5):574-597, May 2010.

Download [help]

Download paper: Doi page

Download paper: Adobe portable document (pdf)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic

Abstract

In this paper we deal with the verification of safety properties of infinite-state systems modeled by term rewriting systems. An over-approximation of the set of reachable terms of a term rewriting system image is obtained by automatically constructing a finite tree automaton. The construction is parameterized by a set E of equations on terms, and we also show that the approximating automata recognize at most the set of image-reachable terms. Finally, we present some experiments carried out with the implementation of our algorithm. In particular, we show how some approximations from the literature can be defined using equational approximations

Contact

Vlad Rusu http://www.irisa.fr/vertecs/Equipe/Rusu/vlad-rusu.html

BibTex Reference

@article{gr10,
   Author = {Genet, Th. and Rusu, V.},
   Title = {Equational Approximations for Tree Automata Completion},
   Journal = {Journal of Symbolic Computation},
   Volume = {    45},
   Number = {5},
   Pages = {574--597},
   Month = {May},
   Year = {2010}
}

EndNote Reference [help]

Get EndNote Reference (.ref)