Source author record

Alessio Mansutti

Alessio Mansutti appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Logic in Computer Science Cryptography and Security Distributed, Parallel, and Cluster Computing

Catalog footprint

What is connected

5works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2021arXiv

Presburger arithmetic with threshold counting quantifiers is easy

We give a quantifier elimination procedures for the extension of Presburger arithmetic with a unary threshold counting quantifier $\exists^{\ge c} y$ that determines whether the number of different $y$ satisfying some formula is at least $c \in \mathbb N$, where $c$ is given in binary. Using a standard quantifier elimination procedure for Presburger arithmetic, the resulting theory is easily seen to be decidable in 4ExpTime. Our main contribution is to develop a novel quantifier-elimination procedure for a more general counting quantifier that decides this theory in 3ExpTime, meaning that it is no harder to decide than standard Presburger arithmetic. As a side result, we obtain an improved quantifier elimination procedure for Presburger arithmetic with counting quantifiers as studied by Schweikardt [ACM Trans. Comput. Log., 6(3), pp. 634-671, 2005], and a 3ExpTime quantifier-elimination procedure for Presburger arithmetic extended with a generalised modulo counting quantifier.

preprint2021arXiv

The Effects of Adding Reachability Predicates in Quantifier-Free Separation Logic

The list segment predicate ls used in separation logic for verifying programs with pointers is well-suited to express properties on singly-linked lists. We study the effects of adding ls to the full quantifier-free separation logic with the separating conjunction and implication, which is motivated by the recent design of new fragments in which all these ingredients are used indifferently and verification tools start to handle the magic wand connective. This is a very natural extension that has not been studied so far. We show that the restriction without the separating implication can be solved in polynomial space by using an appropriate abstraction for memory states whereas the full extension is shown undecidable by reduction from first-order separation logic. Many variants of the logic and fragments are also investigated from the computational point of view when ls is added, providing numerous results about adding reachability predicates to quantifier-free separation logic.

preprint2020arXiv

Modal Logics with Composition on Finite Forests: Expressivity and Complexity (Extra Material)

We investigate the expressivity and computational complexity of two modal logics on finite forests equipped with operators to reason on submodels. The logic ML(|) extends the basic modal logic ML with the composition operator | from static ambient logic, whereas ML(*) contains the separating conjunction * from separation logic. Though both operators are second-order in nature, we show that ML(|) is as expressive as the graded modal logic GML (on finite trees) whereas ML(*) lies strictly between ML and GML. Moreover, we establish that the satisfiability problem for ML(*) is Tower-complete, whereas for ML(|) is (only) AExpPol-complete. As a by-product, we solve several open problems related to sister logics, such as static ambient logic, modal separation logic, and second-order modal logic on finite trees.

preprint2016arXiv

Deciding Hedged Bisimilarity

The spi-calculus is a formal model for the design and analysis of cryptographic protocols: many security properties, such as authentication and strong confidentiality, can be reduced to the verification of behavioural equivalences between spi processes. In this paper we provide an algorithm for deciding hedged bisimilarity on finite processes, which is equivalent to barbed equivalence (and coarser than framed bisimilarity). This algorithm works with any term equivalence satisfying a simple set of conditions, thus encompassing many different encryption schemata.

preprint2015arXiv

Distributed execution of bigraphical reactive systems

The bigraph embedding problem is crucial for many results and tools about bigraphs and bigraphical reactive systems (BRS). Current algorithms for computing bigraphical embeddings are centralized, i.e. designed to run locally with a complete view of the guest and host bigraphs. In order to deal with large bigraphs, and to parallelize reactions, we present a decentralized algorithm, which distributes both state and computation over several concurrent processes. This allows for distributed, parallel simulations where non-interfering reactions can be carried out concurrently; nevertheless, even in the worst case the complexity of this distributed algorithm is no worse than that of a centralized algorithm.