###
Laurent Bienvenu

CR CNRS

Computability theory, Kolmogorov complexity, Logic

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

MCF U. Bordeaux

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

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

Date | Speaker | Title |
---|---|---|

May 14, 2024 | Alexandra Rogova | TBD (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) |