Antoine Amarilli

activity

20122026

most citedPredicting Completeness in Knowledge Bases

103 citations · 300 across the 45 of their papers we have counts for

collaborators

Showing 2026Show all

7 papers · 1 filter

cs.DB2026

Path Length Existence Problems in Bounded-Treewidth Probabilistic Graphs

Antoine Amarilli, Mikaël Monet, Harshul Sagar

We consider the problem of computing the probability of existence of a source-to-target path or walk satisfying a given length constraint in an input probabilistic graph. The lengt…

cs.FL2026

Conditional Membership in Regular Languages

Antoine Amarilli, Sebastien Felipe Labbe, Charles Paperman

We study a formulation of regular language membership as a promise problem, which we dub conditional membership: we fix a promise language $P$ and a target language $T \subseteq P$ …

cs.DS2026

Tractable Gap-Constraint Languages for Complex Event Recognition

Antoine Amarilli, Florin Manea, Tina Ringleb +1

For strings $u, D \in Σ^{*}$ , a subsequence embedding of $u$ in $D$ is a function $e : {1, 2, \dots, ∣ u ∣} \to {1, 2, \dots, ∣ D ∣}$ with $e (i) < e (i + 1)$ for every $i \in \{1,2,…

cs.DS2026

The S-Hamiltonian Cycle Problem

Antoine Amarilli, Arthur Lombardo, Mikaël Monet

Determining if an input undirected graph is Hamiltonian, i.e., if it has a cycle that visits every vertex exactly once, is one of the most famous NP-complete problems. We consider…

cs.FL2026

Constant-Time Dynamic Enumeration of Word Infixes in a Regular Language

Antoine Amarilli, Sven Dziadek, Luc Segoufin

For a fixed regular language $L$ , the enumeration of $L$ -infixes is the following task: we are given an input word $w = a_{1} \dots a_{n}$ and we must enumerate the infixes of $w$ tha…

cs.FL2026

Out-of-Order Membership in Regular Languages

Antoine Amarilli, Sebastien Labbe, Charles Paperman

We introduce the task of out-of-order membership to a formal language L, where the letters of a word w are revealed one by one in an adversarial order. The length |w| is known in a…