Title: Computing transitive closures of hedge transformations

 

Author: Tayssir Touili

 

Address: LIAFA, CNRS and University Paris Diderot, Paris 7, Case 7014, 75205 Paris Cedex 13, France

 

Journal: Int. J. of Critical Computer-Based Systems, 2012 Vol.3, No.1/2, pp.132 - 150

 

Abstract: We consider the framework of regular hedge model checking where configurations are represented by trees of arbitrary arities, sets of configurations are represented by regular hedge automata, and the dynamic of a system is modelled by a term rewriting system. We consider the problem of computing the transitive closure R*(L) of a hedge automaton L and a (not necessarily structure preserving) term rewriting system R. This construction is not possible in general. Therefore, we present a semi-algorithm that computes, in case of termination, an over-approximation of this reachability set. We show that our procedure computes the exact reachability set in many practical applications. We have successfully applied our technique to compute transitive closures for some mutual exclusion protocols defined on arbitrary width tree topologies, as well as for two interesting XML applications.

 

Keywords: regular model checking; rewriting systems; hedge automata; transitive closures; reachability analysis; hedge transformations; mutual exclusion protocols; XML.

 

DOI: http://dx.doi.org/10.1504/IJCCBS.2012.045079

 

Available online 24 Jan 2012

 

 

Editors Full Text AccessAccess for SubscribersPurchase this articleComment on this article