103 citations · 300 across the 45 of their papers we have counts for
6 papers · 1 filter
Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
Antoine Amarilli, Pierre Bourhis, Stefan Mengel +1
We give an algorithm to enumerate the results on trees of monadic second-order (MSO) queries represented by nondeterministic tree automata. After linear time preprocessing (in the…
Connecting Knowledge Compilation Classes and Width Parameters
Antoine Amarilli, Florent Capelli, Mikaël Monet +1
The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structure…
When Can We Answer Queries Using Result-Bounded Data Interfaces?
Antoine Amarilli, Michael Benedikt
We consider answering queries on data available through access methods, that provide lookup access to the tuples matching a given binding. Such interfaces are common on the Web; fu…
Evaluating Datalog via Tree Automata and Cycluits
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 show that clique-frontier-gu…
Constant-Delay Enumeration for Nondeterministic Document Spanners
Antoine Amarilli, Pierre Bourhis, Stefan Mengel +1
We consider the information extraction framework known as document spanners, and study the problem of efficiently computing the results of the extraction from an input document, wh…
Computing Possible and Certain Answers over Order-Incomplete Data
Antoine Amarilli, Mouhamadou Lamine Ba, Daniel Deutch +1
This paper studies the complexity of query evaluation for databases whose relations are partially ordered; the problem commonly arises when combining or transforming ordered data f…