5 papers · 1 filter
Tractable Gap-Constraint Languages for Complex Event Recognition
Antoine Amarilli, Florin Manea, Tina Ringleb +1
For strings , a subsequence embedding of in is a function with for every $i \in \{…
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 (like Gray codes) while ensuring that the delay and the auxiliary space is independent from ,…
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…
Confluence of the Node-Domination and Edge-Domination Hypergraph Rewrite Rules
Antoine Amarilli, Mikaël Monet, Rémi De Pretto
In this note, we study two rewrite rules on hypergraphs, called edge-domination and node-domination, and show that they are confluent. These rules are rather natural and commonly u…
A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automata
Antoine Amarilli, Marcelo Arenas, YooJung Choi +3
This document is an introduction to two related formalisms to define Boolean functions: binary decision diagrams, and Boolean circuits. It presents these formalisms and several of…