Research interests

The team Logical Foundations of Computing (LX) is part of the Formal Models and Methods (M2F) department which itself is part of the Laboratoire Bordelais de Recherche en Informatique (LaBRI) .

Our areas of research and/or interest include (but are not limited to!):

  • Automata Theory
  • Formal Languages
  • Logic in computing
  • Algebraic techniques
  • Graphs and logics
  • Computability theory
  • Proof theory
  • Proof complexity
  • Rewriting techniques
  • Higher-order logic
  • Mechanised reasoning
  • Proof assistants

Team members

Gabriel Bathie
PhD Student

Complexity, Automata, Synthesis

Laurent Bienvenu
CR CNRS

Computability theory, Kolmogorov complexity, Logic

Bruno Courcelle
PR emeritus

Logic and graphs

Irène Durand
MCF U. Bordeaux

Term rewriting and automata, Logic and graphs, Common Lisp programming

Nathanaël Fijalkow
CR CNRS

Games, Automata, Synthesis, Learning

Hugo Gimbert
CR CNRS

Games, Automata

David Janin
MCF Bordeaux INP

Automata, Logic, Semigroups

Guillaume Lagarde
MCF U. Bordeaux

Complexity theory, Synthesis

Jérôme Leroux
DR CNRS

Infinite state systems, Logic, Automata, Proof assistants

Sylvain Lombardy
PR Bordeaux INP

Automata, Weighted models, Formal power series

Corto Mascle
PhD student

Automata, Distributed systems, Synthesis

Rémi Morvan
PhD student

Automata, Logic, Algebra, Databases

Joanna Ochremiak
CR CNRS

Logic, Computational, complexity

Vincent Penelle
MCF U. Bordeaux

Infinite graphs, Counter Systems, Automata Theory

Thomas Place
MCF U. Bordeaux

Logic, Automata theory

David Renault
MCF Bordeaux INP

Logic, Graphs, Formal languages

Géraud Sénizergues
PR emeritus

Formal languages, Graphs and logics, Rewriting techniques

Igor Walukiewicz
DR CNRS

Logic, Automata, Synthesis, Games

Pascal Weil
DR CNRS

Logic, Algorithmic problems in groups and monoids

Marc Zeitoun
PR U. Bordeaux

Automata, logic

Former members

Team seminar

Contact for the seminar: Rémi Morvan & Guillaume Lagarde.

Date Speaker Title
July 4, 2024 Pierre Lafourcade The Shapley value and other quantitative responsibility measures in database theory (joint seminar with RATIO)
June 6, 2024 Pascal Weil Recognizable trace languages, propositional dynamic logic and cascade decomposition of asynchronous automata
May 23, 2024 Teodor Knapik Lindenmayer graph languages, first-order theories and expanders
May 14, 2024 Alexandra Rogova Property Graph Languages (joint seminar with RATIO)
May 2, 2024 Thomas Colcombet Bisimulation invariant MSO over finite transition systems
Apr. 18, 2024 Guillaume Lagarde A gentle introduction to arithmetic complexity with a focus on non-commutativity
Apr. 4, 2024 Djamel Eddine Amir Computing and distinguishing compact sets
Mar. 12, 2024 Nathanaël Fijalkow Mechanical mice and how to program them
Mar. 7, 2024 Gabriel Bathie Towards Stronger Depth Lower Bounds
Feb 22, 2024 Rémi Morvan Automatic relations through the prism of graph colourability and algebraic language theory
Feb 8, 2024 Lê Thành Dũng (Tito) Nguyễn Ambiguity/growth of tree automata/transducers made easy via MSO queries
Jan 25, 2024 Dmitry Sokolov Depth-4 Circuits
Jan 11, 2024 Petra Wolf Decomposing Permutation Automata
Dec 14, 2023 Michaël Cadilhac The Regular Languages of Wire Linear AC0
Nov 30, 2023 Diego Figueira PDL on Steroids (joint seminar with RATIO)
Nov 16, 2023 Gabriel Bathie Property testing of regular languages with applications to streaming property testing of visibly pushdown languages
Oct 26, 2023 Laure Daviaud The Big-O Problem for Max-Plus Automata is Decidable
Oct 5, 2023 Sébastien Tavenas Superpolynomial lower bounds against low-depth algebraic circuits
Sep 21, 2023 Antonio Casares A characterisation of half-positionality for omega-regular languages
Sep 7, 2023 - Team meeting & open problem session
June 11, 2023 Kévin Perrot Sandpile: group, Tutte, complexity
May 11, 2023 Marie Fortin How undecidable are HyperLTL and HyperCTL*?
Apr 27, 2023 Edwin Hamel de Le Court Two-player boundedness counter games
Mar 16, 2023 Sarah Winter A Regular and Complete Notion of Delay for Streaming String Transducers
Feb 23, 2023 Sylvain Lombardy Weighted automata and epsilon-transitions
Feb 2, 2023 Aliaume Lopez Preservation theorems and locality of first order logic
Jan 5, 2023 Paweł Parys Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete
Dec 8, 2022 Alessio Mansutti A geometric decision procedure for Presburger arithmetic
Nov 24, 2022 Corentin Barloy The regular languages in circuit classes
Oct 20, 2022 Alexander Shen Entropy, complexity and algorithmic dimension
Sept 19, 2022 Bruno Courcelle Strongly regular trees, the universal coverings of finite weighted graphs
May 19, 2022 Nathan Grosshans Visibly pushdown languages in AC^0
May 5, 2022 Krishna S. Building blocks for regular functions
Apr 14, 2022 Andrei Romashchenko Secret key agreement from the perspective of algorithmic information theory
Mar 31, 2022 Géraud Sénizergues Some new proofs of Shepherdson's theorem
Mar 17, 2022 Sam van Gool Preserving joins at primes: a connection between automata, logic and domains
Mar 3, 2022 Pierre Vandenhove Characterizing ω-regularity through finite-memory determinacy of games on infinite graphs
Feb 10, 2022 Nathan Lhote Weighted automata and expressions over pre-rational monoids
Jan 20, 2022 Alexandre Vigny Separator logic, expressive power and algorithmic applications
Jan 13, 2022 Antoine Amarilli Dynamic membership for regular languages
Dec 2, 2021 Thomas Place The amazing covering problem and its many wonders
Nov 18, 2021 Bruno Courcelle Order-theoretic trees : monadic second-order descriptions and regularity
Oct 21, 2021 Antonio Casares On a correspondence between memory and Rabin automata
Oct 12, 2021 Volker Diekert Regular matching problems for infinite trees
Oct 7, 2021 Rémi Morvan Separation of transfinite regular languages with first-order logic
Sep 23, 2021 Corto Mascle Keyboards as a new model of computation
Jun 24, 2021 Laurent Bienvenu An introduction to algorithmic randomness (part 2/2)
May 27, 2021 Pascal Weil Asynchronous wreath product decompositions for trace languages
May 6, 2021 Gregory Wilsenach Symmetric arithmetic circuits
Apr 15, 2021 Ismael Jecker A Ramsey theorem for finite monoids
Apr 1, 2021 Laurent Bienvenu An introduction to algorithmic randomness (part 1/2)
Mar 18, 2021 Valentino Delle Rose Word problem and Ceers
Mar 4, 2021 Tomasz Steifer Universal coding and prediction on stationary ergodic measures
Feb 18, 2021 Joanna Ochremiak A short introduction to proof complexity (part 2/2)
Feb 11, 2021 Joanna Ochremiak A short introduction to proof complexity (part 1/2)
Jan 28, 2021 Pascal Weil Algorithmic problems in the theory of infinite groups (part 2/2)
Jan 21, 2021 Pascal Weil Algorithmic problems in the theory of infinite groups (part 1/2)
Dec 10, 2020 Anca Muscholl On string transducers with origins
Nov 17, 2020 David Janin Groups, freest inverse semigroups and walking automata on graphs (part 2/2)
Nov 12, 2020 David Janin Groups, freest inverse semigroups and walking automata on graphs (part 1/2)