Author name cluster

Francesco Tapparo

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

I&C Journal 2010 Journal Article

An efficient simulation algorithm based on abstract interpretation

Francesco Ranzato
Francesco Tapparo

A number of algorithms for computing the simulation preorder and equivalence are available. Let Σ denote the state space, → the transition relation and P sim the partition of Σ induced by simulation equivalence. The algorithms by Henzinger, Henzinger, Kopke and by Bloom and Paige run in O ( | Σ | | → | ) -time and, as far as time complexity is concerned, they are the best available algorithms. However, these algorithms have the drawback of a space complexity that is more than quadratic in the size of the state space Σ. The algorithm by Gentilini, Piazza, Policriti — subsequently corrected by van Glabbeek and Ploeger — appears to provide the best compromise between time and space complexity. Gentilini et al. ’s algorithm runs in O ( | P sim | 2 | → | ) -time while the space complexity is in O ( | P sim | 2 + | Σ | log | P sim | ). We present here a new efficient simulation algorithm that is obtained as a modification of Henzinger et al. ’s algorithm and whose correctness is based on some techniques used in applications of abstract interpretation to model checking. Our algorithm runs in O ( | P sim | | → | ) -time and O ( | P sim | | Σ | log | Σ | ) -space. Thus, this algorithm improves the best known time bound while retaining an acceptable space complexity that is in general less than quadratic in the size of the state space | Σ |. An experimental evaluation showed good comparative results with respect to Henzinger, Henzinger and Kopke’s algorithm.

Details DOI

I&C Journal 2008 Journal Article

Generalizing the Paige–Tarjan algorithm by abstract interpretation

Francesco Ranzato
Francesco Tapparo

The Paige and Tarjan algorithm (PT) for computing the coarsest refinement of a state partition which is a bisimulation on some Kripke structure is well known. It is also well known in model checking that bisimulation is equivalent to strong preservation of CTL or, equivalently, of Hennessy–Milner logic. Drawing on these observations, we analyze the basic steps of the PT algorithm from an abstract interpretation perspective, which allows us to reason on strong preservation in the context of arbitrary (temporal) languages and of generic abstract models, possibly different from standard state partitions, specified by abstract interpretation. This leads us to design a generalized Paige–Tarjan algorithm, called GPT, for computing the minimal refinement of an abstract interpretation-based model that strongly preserves some given language. It turns out that PT is a straight instance of GPT on the domain of state partitions for the case of strong preservation of Hennessy–Milner logic. We provide a number of examples showing that GPT is of general use. We first show how a well-known efficient algorithm for computing stuttering equivalence can be viewed as a simple instance of GPT. We then instantiate GPT in order to design a new efficient algorithm for computing simulation equivalence that is competitive with the best available algorithms. Finally, we show how GPT allows to deal with strong preservation of new languages by providing an efficient algorithm that computes the coarsest refinement of a given partition that strongly preserves a language generated by the reachability operator.

Details DOI