107 citations · 207 across the 14 of their papers we have counts for
15 papers
Separating Automatic Relations
Pablo Barceló, Diego Figueira, Rémi Morvan
We study the separability problem for automatic relations (i.e., relations on finite words definable by synchronous automata) in terms of recognizable relations (i.e., finite union…
PDL on Steroids: on Expressive Extensions of PDL with Intersection and Converse
Diego Figueira, Santiago Figueira, Edwin Pin
We introduce CPDL+, a family of expressive logics rooted in Propositional Dynamic Logic (PDL). In terms of expressive power, CPDL+ strictly contains PDL extended with intersection…
Conjunctive Regular Path Queries under Injective Semantics
Diego Figueira, Miguel Romero
We introduce injective semantics for Conjunctive Regular Path Queries (CRPQs), and study their fundamental properties. We identify two such semantics: atom-injective and query-inje…
A Simple Algorithm for Consistent Query Answering under Primary Keys
Diego Figueira, Anantha Padmanabha, Luc Segoufin +1
We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is…
Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries
Diego Figueira, Rémi Morvan
We show that the problem of whether a query is equivalent to a query of tree-width is decidable, for the class of Unions of Conjunctive Regular Path Queries with two-way naviga…
Universality Problem for Unambiguous VASS
Wojciech Czerwiński, Diego Figueira, Piotr Hofman
We study languages of unambiguous VASS, that is, Vector Addition Systems with States, whose transitions read letters from a finite alphabet, and whose acceptance condition is defin…
Containment of Simple Regular Path Queries
Diego Figueira, Adwait Godbole, S. Krishna +3
Testing containment of queries is a fundamental reasoning task in knowledge representation. We study here the containment problem for Conjunctive Regular Path Queries (CRPQs), a na…
Boundedness of Conjunctive Regular Path Queries
Pablo Barceló, Diego Figueira, Miguel Romero
We study the boundedness problem for unions of conjunctive regular path queries with inverses (UC2RPQs). This is the problem of, given a UC2RPQ, checking whether it is equivalent t…
Playing with Repetitions in Data Words Using Energy Games
Diego Figueira, Anirban Majumdar, M. Praveen
We introduce two-player games which build words over infinite alphabets, and we study the problem of checking the existence of winning strategies. These games are played by two pla…
Bottom-up automata on data trees and vertical XPath
Diego Figueira, Luc Segoufin
A data tree is a finite tree whose every node carries a label from a finite alphabet and a datum from some infinite domain. We introduce a new model of automata over unranked data…
Reasoning about Data Repetitions with Counter Systems
Stephane Demri, Diego Figueira, M Praveen
We study linear-time temporal logics interpreted over data words with multiple attributes. We restrict the atomic formulas to equalities of attribute values in successive positions…
Graph Logics with Rational Relations
Pablo Barcelo, Diego Figueira, Leonid Libkin
We investigate some basic questions about the interaction of regular and rational relations on words. The primary motivation comes from the study of logics for querying graph topol…
Satisfiability for two-variable logic with two successor relations on finite linear orders
Diego Figueira
We study the finitary satisfiability problem for first order logic with two variables and two binary relations, corresponding to the induced successor relations of two finite linea…
Relating timed and register automata
Diego Figueira, Piotr Hofman, Sławomir Lasota
Timed automata and register automata are well-known models of computation over timed and data words respectively. The former has clocks that allow to test the lapse of time between…
Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma
Diego Figueira, Santiago Figueira, Sylvain Schmitz +1
Dickson's Lemma is a simple yet powerful tool widely used in termination proofs, especially when dealing with counters or related data structures. However, most computer scientists…