Antoine Amarilli

collaborators

12 papers

cs.FL2026

On the Complexity of Language Membership for Probabilistic Words

Antoine Amarilli, MikaÃ«l Monet, Paul RaphaÃ«l +1

We study the membership problem to context-free languages (CFLs) on probabilistic words, that specify for each position a probability distribution on the letters. Our task is to co…

cs.DS2026

Tractable Gap-Constraint Languages for Complex Event Recognition

Antoine Amarilli, Florin Manea, Tina Ringleb +1

For strings $u, D \in I^£^{*}$ , 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 \{…

cs.DS2026

Gray Codes With Constant Delay and Constant Auxiliary Space

Antoine Amarilli, Claire David, Nadime Francis +3

We give the first two algorithms to enumerate all binary words of ${0, 1}^{ℓ}$ (like Gray codes) while ensuring that the delay and the auxiliary space is independent from $ℓ$ ,…

cs.LO2026

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.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…

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…