103 citations · 300 across the 45 of their papers we have counts for
9 papers · 1 filter
Connecting Width and Structure in Knowledge Compilation (Extended Version)
Antoine Amarilli, Mikaël Monet, Pierre Senellart
Several query evaluation tasks can be done via knowledge compilation: the query result is compiled as a lineage circuit from which the answer can be determined. For such tasks, it…
Enumeration on Trees under Relabelings
Antoine Amarilli, Pierre Bourhis, Stefan Mengel
We study how to evaluate MSO queries with free variables on trees, within the framework of enumeration algorithms. Previous work has shown how to enumerate answers with linear-time…
Possible and Certain Answers for Queries over Order-Incomplete Data
Antoine Amarilli, Mouhamadou Lamine Ba, Daniel Deutch +1
To combine and query ordered data from multiple sources, one needs to handle uncertainty about the possible orderings. Examples of such "order-incomplete" data include integrated e…
Topological Sorting under Regular Constraints
Antoine Amarilli, Charles Paperman
We introduce the constrained topological sorting problem (CTS): given a regular language K and a directed acyclic graph G with labeled vertices, determine if G has a topological so…
When Can We Answer Queries Using Result-Bounded Data Interfaces?
Antoine Amarilli, Michael Benedikt
We consider answering queries where the underlying data is available only over limited interfaces which provide lookup access to the tuples matching a given binding, but possibly r…
Conjunctive Queries on Probabilistic Graphs: Combined Complexity
Antoine Amarilli, Mikaël Monet, Pierre Senellart
Query evaluation over probabilistic databases is known to be intractable in many cases, even in data complexity, i.e., when the query is fixed. Although some restrictions of the qu…