The color coding means:

: all participate
: Doctoral students participate

Please find the abstracts below the schedule and note that some of the slides are made available here, internally.

Plenary seminar sessions are hosted on Zoom. Student seminar sessions are hosted on a local instance of BigBlueButton. Access links can be found in the timetable below. Passcodes are going to be sent via e-mail, to the internal mailing list.

The passcodes to the virtual meetings can also be inquired from Sandy Seifarth.

Timetable

Abstracts

Joël Ouaknine: The Skolem Landscape

The Skolem Problem asks how to determine algorithmically whether a given linear recurrence sequence (such as the Fibonacci numbers) has a zero. It is a central question in dynamical systems and number theory, and has many connections to other branches of mathematics and computer science. Unfortunately, its decidability has been open for nearly a century! In this talk, I will present a survey of what is known on the Skolem Problem and related questions, including recent and ongoing developments.

Tobias John: Verification of Ontology-Guided Controllers

Ontologies are an established way to organize complex knowledge, which proved their usefulness in many different domains. Therefore, it is natural to use this powerful concept in the domain of controllers for autonomous robotic vehicles. Such controllers organize the knowledge about their environment in a domain specific ontology and take actions based on inferred knowledge from the ontology. As these systems operate often in remote or hostile environments, reliable operation is a must. We discuss a concept to use traditional model checkers for such controllers.

Yury Savateev: Deciding FO-definability of Regular Languages

We prove that, similarly to known PSpace-completeness of recognising FO(<)-definability of the language L(A) of a DFA A, deciding both FO(<,≡)- and FO(<,MOD)-definability (corresponding to circuit complexity in AC0 and ACC0) are PSpace-complete. We obtain these results by first showing that known algebraic characterisations of FO-definability of L(A) can be captured by ‘localisable’ properties of the transition monoid of A. Using our criterion, we then generalise the known proof of PSpace-hardness of FO(<)-definability, and establish the upper bounds not only for arbitrary DFAs but also for 2NFAs.

Mikołaj Bojańczyk: Transducers of polynomial growth

Transducers are like automata, but instead of accepting/rejecting they produce an output, such as a string or a tree. In my talk, I will discuss some recent results transducers, mainly about the class of polyregular transducers, which can be seen as a candidate for the notion of “regular” string-to-string transducers of polynomial growth. I will discuss how this class can be characterised in many different ways, including logic, automata, and λ-calculus.

Simon Knäuer: Network satisfaction problems solved by Datalog

We will explain the network satisfaction problem of a finite relation algebra and recall the P vs. NP-complete dichotomy result for symmetric relation algebras with a flexible atom. We present a new strengthening of this result, namely a Datalog vs. NP-complete dichotomy for this class.

Teodora Nasz: The HOM problem for weighted regular tree languages

The HOM problem, which asks whether the image of a regular tree language under a given tree homomorphism is again regular, is known to be decidable [Godoy & Giménez: The HOM problem is decidable. JACM 60(4), 2013]. However, the problem remains open for regular weighted tree languages. It is demonstrated that the main notion used in the unweighted setting, the tree automaton with equality and inequality constraints, can straightforwardly be generalized to the weighted setting and can represent the image of any regular weighted tree language under any nondeleting, nonerasing tree homomorphism. Several closure properties as well as decision problems are also investigated for the weighted tree languages generated by weighted tree automata with constraints.