6 papers
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…
Common Foundations for Recursive Shape Languages
Shqiponja Ahmetaj, Iovka Boneva, Jan Hidders +9
As schema languages for RDF data become more mature, we are seeing efforts to extend them with recursive semantics, applying diverse ideas from logic programming and description lo…
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…
Common Foundations for SHACL, ShEx, and PG-Schema
S. Ahmetaj, I. Boneva, J. Hidders +11
Graphs have emerged as an important foundation for a variety of applications, including capturing and reasoning over factual knowledge, semantic data integration, social networks,…
Automata-Theoretic Characterisations of Branching-Time Temporal Logics
Massimo Benerecetti, Laura Bozzelli, Fabio Mogavero +1
Characterisations theorems serve as important tools in model theory and can be used to assess and compare the expressive power of temporal languages used for the specification and…