Nathanaël Fijalkow

According to our database, Nathanaël Fijalkow authored at least 80 papers between 2010 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Scarlet: Scalable Anytime Algorithms for Learning Fragments of Linear Temporal Logic.

Ritam Raha, Rajarshi Roy, Nathanaël Fijalkow, Daniel Neider

J. Open Source Softw., January, 2024

Playing Safe, Ten Years Later.

Thomas Colcombet, Nathanaël Fijalkow, Florian Horn

Log. Methods Comput. Sci., 2024

LTL learning on GPUs.

Mojtaba Valizadeh, Nathanaël Fijalkow, Martin Berger

CoRR, 2024

Theoretical foundations for programmatic reinforcement learning.

Guruprerana Shabadi, Nathanaël Fijalkow, Théo Matricon

CoRR, 2024

Synthesizing Efficiently Monitorable Formulas in Metric Temporal Logic.

Ritam Raha, Rajarshi Roy, Nathanaël Fijalkow, Daniel Neider, Guillermo A. Pérez

Proceedings of the Verification, Model Checking, and Abstract Interpretation, 2024

2023

The Futures of Reactive Synthesis (Dagstuhl Seminar 23391).

Nathanaël Fijalkow, Bernd Finkbeiner, Guillermo A. Pérez, Elizabeth Polgreen, Rémi Morvan

Dagstuhl Reports, 2023

Learning temporal formulas from examples is hard.

Corto Mascle, Nathanaël Fijalkow, Guillaume Lagarde

CoRR, 2023

Games on Graphs.

Nathanaël Fijalkow, Nathalie Bertrand, Patricia Bouyer-Decitre, Romain Brenguier, Arnaud Carayol, John Fearnley, Hugo Gimbert, Florian Horn, Rasmus Ibsen-Jensen, Nicolas Markey, Benjamin Monmege, Petr Novotný, Mickael Randour, Ocan Sankur, Sylvain Schmitz, Olivier Serre, Mateusz Skomra

CoRR, 2023

From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History-)Determinism.

Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow, Karoliina Lehtinen

CoRR, 2023

WikiCoder: Learning to Write Knowledge-Powered Code.

Théo Matricon, Nathanaël Fijalkow, Gaëtan Margueritte

Proceedings of the Model Checking Software - 29th International Symposium, 2023

How to Play Optimally for Regular Objectives?

Patricia Bouyer, Nathanaël Fijalkow, Mickael Randour, Pierre Vandenhove

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

DeepSynth: Scaling Neural Program Synthesis with Distribution-based Search.

Théo Matricon, Nathanaël Fijalkow, Guillaume Lagarde, Kevin Ellis

J. Open Source Softw., October, 2022

The Theory of Universal Graphs for Infinite Duration Games.

Thomas Colcombet, Nathanaël Fijalkow, Pawel Gawrychowski, Pierre Ohlmann

Log. Methods Comput. Sci., 2022

Probabilistic automata of bounded ambiguity.

Nathanaël Fijalkow, Cristian Riveros, James Worrell

Inf. Comput., 2022

A robust class of linear recurrence sequences.

Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote, Filip Mazowiecki

Inf. Comput., 2022

Scalable Anytime Algorithms for Learning Fragments of Linear Temporal Logic.

Ritam Raha, Rajarshi Roy, Nathanaël Fijalkow, Daniel Neider

Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, 2022

Public and Private Affairs in Strategic Reasoning.

Nathanaël Fijalkow, Bastien Maubert, Aniello Murano, Sasha Rubin, Moshe Y. Vardi

Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning, 2022

Scaling Neural Program Synthesis with Distribution-Based Search.

Nathanaël Fijalkow, Guillaume Lagarde, Théo Matricon, Kevin Ellis, Pierre Ohlmann, Akarsh Nayan Potta

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

The Game of Synthesis.

Nathanaël Fijalkow

, 2022

2021

Alternating Tree Automata with Qualitative Semantics.

Raphaël Berthon, Nathanaël Fijalkow, Emmanuel Filiot, Shibashis Guha, Bastien Maubert, Aniello Murano, Laureline Pinault, Sophie Pinchinat, Sasha Rubin, Olivier Serre

ACM Trans. Comput. Log., 2021

Controlling a random population.

Thomas Colcombet, Nathanaël Fijalkow, Pierre Ohlmann

Log. Methods Comput. Sci., 2021

Scalable Anytime Algorithms for Learning Formulas in Linear Temporal Logic.

Ritam Raha, Rajarshi Roy, Nathanaël Fijalkow, Daniel Neider

CoRR, 2021

New Algorithms for Combinations of Objectives using Separating Automata.

Ashwani Anand, Nathanaël Fijalkow, Aliénor Goubault-Larrecq, Jérôme Leroux, Pierre Ohlmann

Proceedings of the Proceedings 12th International Symposium on Games, 2021

Lower Bounds for Arithmetic Circuits via the Hankel Matrix.

Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre

Comput. Complex., 2021

The complexity of learning linear temporal formulas from examples.

Nathanaël Fijalkow, Guillaume Lagarde

Proceedings of the 15th International Conference on Grammatical Inference, 2021

Optimal Transformations of Games and Automata Using Muller Conditions.

Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Statistical Comparison of Algorithm Performance Through Instance Selection.

Théo Matricon, Marie Anastacio, Nathanaël Fijalkow, Laurent Simon, Holger H. Hoos

Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming, 2021

2020

Consistent Unsupervised Estimators for Anchored PCFGs.

Alexander Clark, Nathanaël Fijalkow

Trans. Assoc. Comput. Linguistics, 2020

Lower bounds for the state complexity of probabilistic languages and the language of prime numbers.

Nathanaël Fijalkow

J. Log. Comput., 2020

Trace Refinement in Labelled Markov Decision Processes.

Nathanaël Fijalkow, Stefan Kiefer, Mahsa Shirmohammadi

Log. Methods Comput. Sci., 2020

Optimal transformations of Muller conditions.

Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow

CoRR, 2020

Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games.

Nathanaël Fijalkow, Pawel Gawrychowski, Pierre Ohlmann

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Assume-Guarantee Synthesis for Prompt Linear Temporal Logic.

Nathanaël Fijalkow, Bastien Maubert, Aniello Murano, Moshe Y. Vardi

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020

The Theory of Universal Graphs for Games: Past and Future.

Nathanaël Fijalkow

Proceedings of the Coalgebraic Methods in Computer Science, 2020

Data Generation for Neural Programming by Example.

Judith Clymo, Adrià Gascón, Brooks Paige, Nathanaël Fijalkow, Haik Manukian

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

Complete Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem.

Nathanaël Fijalkow, Pierre Ohlmann, Joël Ouaknine, Amaury Pouly, James Worrell

Theory Comput. Syst., 2019

Expressiveness of probabilistic modal logics: A gradual approach.

Florence Clerc, Nathanaël Fijalkow, Bartek Klin, Prakash Panangaden

Inf. Comput., 2019

Verification of Neural Networks: Specifying Global Robustness using Generative Models.

Nathanaël Fijalkow, Mohit Kumar Gupta

CoRR, 2019

Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games.

Wojciech Czerwinski, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdzinski, Ranko Lazic, Pawel Parys

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

On the Monniaux Problem in Abstract Interpretation.

Nathanaël Fijalkow, Engel Lefaucheux, Pierre Ohlmann, Joël Ouaknine, Amaury Pouly, James Worrell

Proceedings of the Static Analysis - 26th International Symposium, 2019

On the decidability of reachability in linear time-invariant systems.

Nathanaël Fijalkow, Joël Ouaknine, Amaury Pouly, João Sousa Pinto, James Worrell

Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control, 2019

Universal Graphs and Good for Games Automata: New Tools for Infinite Duration Games.

Thomas Colcombet, Nathanaël Fijalkow

Proceedings of the Foundations of Software Science and Computation Structures, 2019

2018

Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees.

Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann

Electron. Colloquium Comput. Complex., 2018

The complexity of mean payoff games using universal graphs.

Nathanaël Fijalkow, Pawel Gawrychowski, Pierre Ohlmann

CoRR, 2018

Parity games and universal graphs.

Thomas Colcombet, Nathanaël Fijalkow

CoRR, 2018

An Optimal Value Iteration Algorithm for Parity Games.

Nathanaël Fijalkow

CoRR, 2018

The State Complexity of Alternating Automata.

Nathanaël Fijalkow

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

Timed Comparisons of Semi-Markov Processes.

Mathias Ruggaard Pedersen, Nathanaël Fijalkow, Giorgio Bacci, Kim G. Larsen, Radu Mardare

Proceedings of the Language and Automata Theory and Applications, 2018

Quantifying Bounds in Strategy Logic.

Nathanaël Fijalkow, Bastien Maubert, Aniello Murano, Sasha Rubin

Proceedings of the 27th EACSL Annual Conference on Computer Science Logic, 2018

2017

Monadic Second-Order Logic with Arbitrary Monadic Predicates.

Nathanaël Fijalkow, Charles Paperman

ACM Trans. Comput. Log., 2017

Profinite techniques for probabilistic automata and the Markov Monoid algorithm.

Nathanaël Fijalkow

Theor. Comput. Sci., 2017

Undecidability results for probabilistic automata.

Nathanaël Fijalkow

ACM SIGLOG News, 2017

Profinite Techniques for Probabilistic Automata.

Nathanaël Fijalkow

Bull. EATCS, 2017

Stamina: Stabilisation Monoids in Automata Theory.

Nathanaël Fijalkow, Hugo Gimbert, Edon Kelmendi, Denis Kuperberg

Proceedings of the Implementation and Application of Automata, 2017

Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem.

Nathanaël Fijalkow, Pierre Ohlmann, Joël Ouaknine, Amaury Pouly, James Worrell

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Expressiveness of Probabilistic Modal Logics, Revisited.

Nathanaël Fijalkow, Bartek Klin, Prakash Panangaden

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Lower Bounds for Alternating Online Space Complexity.

Nathanaël Fijalkow

Electron. Colloquium Comput. Complex., 2016

Characterisation of an Algebraic Algorithm for Probabilistic Automata.

Nathanaël Fijalkow

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

The Online Space Complexity of Probabilistic Languages.

Nathanaël Fijalkow

Proceedings of the Logical Foundations of Computer Science - International Symposium, 2016

The Bridge Between Regular Cost Functions and Omega-Regular Languages.

Thomas Colcombet, Nathanaël Fijalkow

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Counting and Randomising in Automata Theory. (Compteurs et Aléas en Théorie des Automates).

Nathanaël Fijalkow

PhD thesis, 2015

Deciding the value 1 problem for probabilistic leaktight automata.

Nathanaël Fijalkow, Hugo Gimbert, Edon Kelmendi, Youssouf Oualhadj

Log. Methods Comput. Sci., 2015

Profinite Techniques for Probabilistic Automata and the Optimality of the Markov Monoid Algorithm.

Nathanaël Fijalkow

CoRR, 2015

Irregular Behaviours for Probabilistic Automata.

Nathanaël Fijalkow, Michal Skrzypczak

Proceedings of the Reachability Problems - 9th International Workshop, 2015

Trading Bounds for Memory in Games with Counters.

Nathanaël Fijalkow, Florian Horn, Denis Kuperberg, Michal Skrzypczak

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Parity and Streett Games with Costs

Nathanaël Fijalkow, Martin Zimmermann

Log. Methods Comput. Sci., 2014

What is known about the Value 1 Problem for Probabilistic Automata?

Nathanaël Fijalkow

CoRR, 2014

Two Recursively Inseparable Problems for Probabilistic Automata.

Nathanaël Fijalkow, Hugo Gimbert, Florian Horn, Youssouf Oualhadj

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Playing Safe.

Thomas Colcombet, Nathanaël Fijalkow, Florian Horn

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

ACME: Automata with Counters, Monoids and Equivalence.

Nathanaël Fijalkow, Denis Kuperberg

Proceedings of the Automated Technology for Verification and Analysis, 2014

2013

Les jeux d'accessibilité généralisée.

Nathanaël Fijalkow, Florian Horn

Tech. Sci. Informatiques, 2013

Emptiness Of Alternating Tree Automata Using Games With Imperfect Information.

Nathanaël Fijalkow, Sophie Pinchinat, Olivier Serre

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

Infinite-state games with finitary conditions.

Krishnendu Chatterjee, Nathanaël Fijalkow

Proceedings of the Computer Science Logic 2013 (CSL 2013), 2013

2012

Deciding the Value 1 Problem for Probabilistic Leaktight Automata.

Nathanaël Fijalkow, Hugo Gimbert, Youssouf Oualhadj

Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

Cost-Parity and Cost-Streett Games.

Nathanaël Fijalkow, Martin Zimmermann

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

A reduction from parity games to simple stochastic games

Krishnendu Chatterjee, Nathanaël Fijalkow

Proceedings of Second International Symposium on Games, 2011

A Class of Probabilistic Automata with a Decidable Value 1 Problem

Nathanaël Fijalkow, Hugo Gimbert, Youssouf Oualhadj

CoRR, 2011

Pushing undecidability of the isolation problem for probabilistic automata

Nathanaël Fijalkow, Hugo Gimbert, Youssouf Oualhadj

CoRR, 2011

Finitary Languages.

Krishnendu Chatterjee, Nathanaël Fijalkow

Proceedings of the Language and Automata Theory and Applications, 2011

2010

The surprizing complexity of reachability games

Nathanaël Fijalkow, Florian Horn

CoRR, 2010