77 citations
- Université Paris-Est CréteilFR14 papers
- Centre National de la Recherche ScientifiqueFR7 papers
- Laboratoire d'Informatique Algorithmique: Fondements et ApplicationsFR5 papers
- Paris-Est SupFR5 papers
- Institute of Mathematics and Computer ScienceMD3 papers
- Université Paris DiderotFR3 papers
- Åbo Akademi UniversityFI2 papers
- Institut de Mécanique et d'Ingénierie de BordeauxFR2 papers
- Institut national de recherche en sciences et technologies du numériqueFR2 papers
- Laboratoire d'Informatique de Paris-NordFR2 papers
- Laboratoire d'Informatique Gaspard-MongeFR2 papers
- Laboratoire Spécification et VérificationFR2 papers
45 papers
Cellular Automata and Kan Extensions
Alexandre Fernandez, Luidnel Maignan, Antoine Spicher
In this paper, we formalize precisely the sense in which the application of cellular automaton to partial configuration is a natural extension of its local transition function thro…
Property-Directed Verification of Recurrent Neural Networks
Igor Khmelnitsky, Daniel Neider, Rajarshi Roy +6
This paper presents a property-directed approach to verifying recurrent neural networks (RNNs). To this end, we learn a deterministic finite automaton as a surrogate model from a g…
Milliken's tree theorem and its applications: a computability-theoretic perspective
Paul-Elliot Anglès d'Auriac, Peter A. Cholak, Damir D. Dzhafarov +2
Milliken's tree theorem is a deep result in combinatorics that generalizes a vast number of other results in the subject, most notably Ramsey's theorem and its many variants and co…
Processes, Systems and Tests: Defining Contextual Equivalences
Clément Aubert, Daniele Varacca
In this position paper, we would like to offer and defend a new template to study equivalences between programs -- in the particular framework of process algebras for concurrent co…
Lower bounds for algebraic machines, semantically
Luc Pellissier, Thomas Seiller
This paper presents a new semantic method for proving lower bounds in computational complexity. We use it to prove that maxflow, a PTIME complete problem, is not computable in poly…
Games Where You Can Play Optimally with Arena-Independent Finite Memory
Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj +2
For decades, two-player (antagonistic) games on graphs have been a framework of choice for many important problems in theoretical computer science. A notorious one is controller sy…