output
20132022
most citedA Circuit-Based Approach to Efficient Enumeration

22 citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

12 papers

cs.LO2022

Tighter Bounds for Query Answering with Guarded TGDs

Antoine Amarilli, Michael Benedikt

We consider the complexity of the open-world query answering problem, where we wish to determine certain answers to conjunctive queries over incomplete datasets specified by an ini…

cs.DB2022★ 1 cited

Linear Programs with Conjunctive Database Queries

Florent Capelli, Nicolas Crosetti, Joachim Niehren +1

In this paper, we study the problem of optimizing a linear program whose variables are the answers to a conjunctive query. For this we propose the language LP(CQ) for specifying li…

cs.FL2021

Locality and Centrality: The Variety ZG

Antoine Amarilli, Charles Paperman

We study the variety ZG of monoids where the elements that belong to a group are central, i.e., commute with all other elements. We show that ZG is local, that is, the semidirect p…

cs.FL2020

A note on the class of languages generated by F-systems over regular languages

Jorge C. Lucero, Sławek Staworko

An F-system is a computational model that performs a folding operation on words of a given language, following directions coded on words of another given language. This paper consi…

cs.DB2018★ 4 cited

Relational to RDF Data Exchange in Presence of a Shape Expression Schema

Iovka Boneva, Jose Lozano, Sławek Staworko

We study the relational to RDF data exchange problem, where the tar- get constraints are specified using Shape Expression schema (ShEx). We investi- gate two fundamental problems:…

cs.FL2018

Continuity of Functional Transducers: A Profinite Study of Rational Functions

Michaël Cadilhac, Olivier Carton, Charles Paperman

A word-to-word function is continuous for a class of languages~ if its inverse maps _languages to~. This notion provides a basis for an algeb…

cs.LO2017★ 2 cited

Definability and Interpolation within Decidable Fixpoint Logics

Michael Benedikt, Pierre Bourhis, Michael Vanden Boom

We look at characterizing which formulas are expressible in rich decidable logics such as guarded fixpoint logic, unary negation fixpoint logic, and guarded negation fixpoint logic…

cs.DS2017★ 22 cited

A Circuit-Based Approach to Efficient Enumeration

Antoine Amarilli, Pierre Bourhis, Louis Jachiet +1

We study the problem of enumerating the satisfying valuations of a circuit while bounding the delay, i.e., the time needed to compute each successive valuation. We focus on the cla…

cs.DB2017★ 3 cited

Combined Tractability of Query Evaluation via Tree Automata and Cycluits (Extended Version)

Antoine Amarilli, Pierre Bourhis, Mikaël Monet +1

We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We introduce a new Datalog frag…

cs.DB2015★ 2 cited

Shape Expressions Schemas

Iovka Boneva, Jose E. Labra Gayo, Eric G. Prud'hommeaux +1

We present Shape Expressions (ShEx), an expressive schema language for RDF designed to provide a high-level, user friendly syntax with intuitive semantics. ShEx allows to describe…

cs.DB2013★ 3 cited

XPath Node Selection over Grammar-Compressed Trees

Sebastian Maneth, Tom Sebastian

XML document markup is highly repetitive and therefore well compressible using grammar-based compression. Downward, navigational XPath can be executed over grammar-compressed trees…

cs.DB2013★ 8 cited

Simple Schemas for Unordered XML

Iovka Boneva, Radu Ciucanu, Slawek Staworko

We consider unordered XML, where the relative order among siblings is ignored, and propose two simple yet practical schema formalisms: disjunctive multiplicity schemas (DMS), and i…