13 citations · 30 across the 13 of their papers we have counts for
8 papers · 1 filter
Deciding the Common Fragment of CTL with Past and LTL
Massimo Benerecetti, Dario Della Monica, Angelo Matteo +2
A central goal of language theory is to compare formalisms by understanding their relative expressive power. One challenging question in this direction is the problem of determinin…
Automaton-based Characterisations of First Order Logic over Infinite Trees
Massimo Benerecetti, Dario Della Monica, Angelo Matteo +2
We study the expressive power of First-Order Logic (\FO) over (unordered) infinite trees, with the aim of identifying robust characterisations in terms of branching-time specificat…
An Automaton-based Characterisation of First-Order Logic over Infinite Trees
Massimo Benerecetti, Dario Della Monica, Angelo Matteo +2
In this paper, we study First Order Logic (FO) over (unordered) infinite trees and its connection with branching-time temporal logics. More specifically, we provide an automata-the…
The Logic of Prefixes and Suffixes is Elementary under Homogeneity
Dario Della Monica, Angelo Montanari, Gabriele Puppis +1
In this paper, we study the finite satisfiability problem for the logic BE under the homogeneity assumption. BE is the cornerstone of Halpern and Shoham's interval temporal logic,…
An algebraic approach to MSO-definability on countable linear orderings
Olivier Carton, Thomas Colcombet, Gabriele Puppis
We develop an algebraic notion of recognizability for languages of words indexed by countable linear orderings. We prove that this notion is effectively equivalent to definability…
A decidable weakening of Compass Logic based on cone-shaped cardinal directions
Angelo Montanari, Gabriele Puppis, Pietro Sala
We introduce a modal logic, called Cone Logic, whose formulas describe properties of points in the plane and spatial relationships between them. Points are labelled by proposition…
Inference From Visible Information And Background Knowledge
Michael Benedikt, Pierre Bourhis, Balder ten Cate +2
We provide a wide-ranging study of the scenario where a subset of the relations in a relational vocabulary are visible to a user --- that is, their complete contents are known ---…
Decidability of the interval temporal logic ABBar over the natural numbers
A. Montanari, G. Puppis, P. Sala +1
In this paper, we focus our attention on the interval temporal logic of the Allen's relations "meets", "begins", and "begun by" (ABBar for short), interpreted over natural numbers.…