output
20062021
most citedModel-checking ATL under Imperfect Information and Perfect Recall Semantics is Undecidable

77 citations

researchers with a paper here
collaborating institutions
Showing 2020Show all

5 papers · 1 filter

cs.LG2020★ 5 cited

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…

math.LO2020★ 3 cited

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…

cs.DC2020★ 1 cited

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…

cs.CC2020

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…

cs.GT2020★ 18 cited

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…