15 citations · 47 across the 12 of their papers we have counts for
5 papers · 1 filter
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…