15 citations · 47 across the 12 of their papers we have counts for
13 papers
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…
On Computing Probabilistic Explanations for Decision Trees
Marcelo Arenas, Pablo Barceló, Miguel Romero +1
Formal XAI (explainable AI) is a growing area that focuses on computing explanations with mathematical guarantees for the decisions made by ML models. Inside formal XAI, one of the…
Modeling GPU Dynamic Parallelism for Self Similar Density Workloads
Felipe A. Quezada, Cristóbal A. Navarro, Miguel Romero +1
Dynamic Parallelism (DP) is a runtime feature of the GPU programming model that allows GPU threads to execute additional GPU kernels, recursively. Apart from making the programming…
On monotonic determinacy and rewritability for recursive queries and views
Michael Benedikt, Stanislav Kikot, Piotr Ostropolski-Nalewaja +1
A query Q is monotonically determined over a set of views if Q can be expressed as a monotonic function of the view image. In the case of relational algebra views and queries, mono…
Pliability and Approximating Max-CSPs
Miguel Romero, Marcin Wrochna, Stanislav Živný
We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time algorithm for an arbitrarily good approximation of the optimal value in a large class of Max-…
A Rewriting Logic Approach to Stochastic and Spatial Constraint System Specification and Verification
Miguel Romero, Sergio Ramírez, Camilo Rocha +1
This paper addresses the issue of specifying, simulating, and verifying reactive systems in rewriting logic. It presents an executable semantics for probabilistic, timed, and spati…
Point-width and Max-CSPs
Clement Carbonnel, Miguel Romero, Stanislav Zivny
The complexity of (unbounded-arity) Max-CSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of Max-CSPs…
A More General Theory of Static Approximations for Conjunctive Queries
Pablo Barceló, Miguel Romero, Thomas Zeume
Conjunctive query (CQ) evaluation is NP-complete, but becomes tractable for fragments of bounded hypertreewidth. Approximating a hard CQ by a query from such a fragment can thus al…
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…
Reachability Analysis for Spatial Concurrent Constraint Systems with Extrusion
Miguel Romero, Camilo Rocha
Spatial concurrent constraint programming (SCCP) is an algebraic model of spatial modalities in constrained-based process calculi; it can be used to reason about spatial informatio…
The tractability frontier of well-designed SPARQL queries
Miguel Romero
We study the complexity of query evaluation of SPARQL queries. We focus on the fundamental fragment of well-designed SPARQL restricted to the AND, OPTIONAL and UNION operators. Our…
The complexity of general-valued CSPs seen from the other side
Clement Carbonnel, Miguel Romero, Stanislav Zivny
The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand side structures, the results of Dalmau, Kolaiti…
The complexity of reverse engineering problems for conjunctive queries
Pablo Barcelo, Miguel Romero
Reverse engineering problems for conjunctive queries (CQs), such as query by example (QBE) or definability, take a set of user examples and convert them into an explanatory CQ. Des…