Research Seminar
Past Talks
Logical methods in Computer Science have a long history, as witnessed e.g. by the relative longevity of SQL in relational database management. More recently, Courcelle’s theorem, which combines second-order logic and tree decompositions of graphs, showed that a many NP-complete algorithmic problems in graph theory can be solved in polynomial time on graphs with bounded tree-width (and even on graphs with bounded clique-width). At the heart of the latter result is the notion of monadic second-order transductions, which are a way to encode a graph within a structure using coloring and monadic second-order logic formulas. In this presentation we consider first-order transductions, for which the formulas have to be first-order formulas. As a counterpart for this strong restriction, many algorithmic problems become fixed parameter tractable when restricted to nowhere dense classes, which include classes excluding a topological minor thus, in particular, classes of planar graphs and classes of graphs with bounded degrees.
In this setting, the main challenge is to extend results obtained in the sparse setting (for bounded expansion classes and nowhere dense classes) to the dense setting, in a similar way the results about monadic second-order model checking have been extended from classes with bounded tree-width to classes with bounded clique-width.
I will give a gentle introduction to a new graph parameter called twin-width. In a nutshell, bounded twin-width classes are interesting because they generalize many well-established and seemingly very different classes, while preserving good algorithmic and structural properties. Thus twin-width provides a unifying and generalizing perspective on several phenomena. There are three intertwined points on which I would like to insist:
- How to show that a class has bounded twin-width?
- How to solve problems faster when inputs have low twin-width?
- The Marcus-Tardos Theorem, a central result in combinatorics, and also the engine of twin-width.
If I do my job correctly, anyone attending the tutorial, regardless of their scientific background, will leave with the basic knowledge sufficient for instance to read/watch further material on twin-width much more easily and think about the new open questions.
Parikh automata on finite words (PA) were first introduced by Klaedtke and Rue?. This extension of finite automata processes sequences of symbols that are labeled with vectors of natural numbers. Such a word is accepted if there is an accepting run in the automaton and the sum of the vectors lies in a given semi-linear set. In the first part, we study PA where the size of the vectors is bounded and compare the respective classes of languages to the Chomsky hierarchy. In the second part, we introduce Parikh automata on infinite words. We present two variants and characterize the respective classes of languages similar to Büchi's theorem. We conclude by giving an overview of their closure properties and common decision problems.