Computing transitive closures of hedge transformations Online publication date: Tue, 24-Jan-2012
by Tayssir Touili
International Journal of Critical Computer-Based Systems (IJCCBS), Vol. 3, No. 1/2, 2012
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.
Online publication date: Tue, 24-Jan-2012
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Critical Computer-Based Systems (IJCCBS):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.If you still need assistance, please email email@example.com