1 citations · 1 across the 3 of their papers we have counts for
7 papers
Notes on kAExp(pol) problems for deterministic machines
Alessio Mansutti
The complexity of several logics, such as Presburger arithmetic, dependence logics and ambient logics, can only be characterised in terms of alternating Turing machines. Despite qu…
Presburger arithmetic with threshold counting quantifiers is easy
Dmitry Chistikov, Christoph Haase, Alessio Mansutti
We give a quantifier elimination procedures for the extension of Presburger arithmetic with a unary threshold counting quantifier that determines whether the nu…
Modal Logics with Composition on Finite Forests: Expressivity and Complexity (Extra Material)
Bartosz Bednarczyk, Stéphane Demri, Raul Fervari +1
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…
Internal Calculi for Separation Logics
Stéphane Demri, Etienne Lozes, Alessio Mansutti
We present a general approach to axiomatise separation logics with heaplet semantics with no external features such as nominals/labels. To start with, we design the first (internal…
The Effects of Adding Reachability Predicates in Quantifier-Free Separation Logic
Stéphane Demri, Etienne Lozes, Alessio Mansutti
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 add…
Loose Graph Simulations
Alessio Mansutti, Marino Miculan, Marco Peressotti
We introduce loose graph simulations (LGS), a new notion about labelled graphs which subsumes in an intuitive and natural way subgraph isomorphism (SGI), regular language pattern m…