One FLAT World Seminar

The hardness of decision-tree complexity

Speaker: Bruno Loff

June 5, 2024 at 13:00 UTC

In the world of formal languages, we have always been interested in the problem of finding the smallest “algorithm” for deciding a given language. Moore’s algorithm for DFA minimization is a standard part of a first course in theory of computing. Jiang and Ravikumar have shown, on the other hand, that NFA minimization is PSPACE-hard. [Read More]

Using automata to prove theorems about sequences

Speaker: Jeffrey Shallit

May 8, 2024 at 13:00 UTC

Automata have proven very useful in practice, both for text searching and the analysis of various kinds of discrete systems. In this talk, however, I will show that they are also useful for (rigorously) proving theorems about sequences, and hence become a new and exciting tool for number theorists and combinatorialists. As an example, I will talk about a sequence of Benoit Cloitre, defined by a certain recurrence involving Fibonacci numbers. Many properties of this sequence were conjectured, and using automata we can now resolve all of them. The proofs are done using Walnut, a free open-source theorem-prover for automatic... [Read More]

Non-regular complexity

Speaker: Szilárd Zsolt Fazekas

April 10, 2024 at 08:00 UTC

Given a computational model \(\cal A\), we will call another model \(\cal B\) an extension of \(\cal A\) if computation steps possible in a system (machine, grammar, etc.) of type \(\cal A\) are also possible in systems of type \(\cal B\) and the latter allow some operations that are not possible in the former. Such a relationship between models is exhibited by context-free grammars as extensions of regular grammars, or one-way jumping automata and automata with translucent letters as extensions of finite automata. The operations available in the extensions but not in the original model can be viewed as a... [Read More]

Using the past for resolving the future

Speaker: Orna Kupferman

March 6, 2024 at 14:00 UTC

Nondeterminism models an ability to see the future: An automaton with an infinite look ahead can successfully resolve its nondeterministic choices. An automaton is history deterministic (HD) if it can successfully resolve its nondeterministic choices in a way that only depends on the past. Formally, an HD automaton has a strategy that maps each finite word to the transition to be taken after the word is read and following this strategy results in accepting all the words in the language of the automaton. Beyond being theoretically interesting and intriguing, HD automata can replace deterministic automata in several applications, most notably... [Read More]

Store languages of automata models, with applications

Speaker: Ian McQuillan

February 7, 2024 at 14:00 UTC

The store language of an automaton is a language-theoretic encoding of the contents of every data store that can appear at any point in an accepting computation. While this is an older concept, it is not a particularly well-studied one. In this talk, previous results regarding store languages from the literature are reviewed, and the store languages of many existing types of automata from the literature are described. Several applications of store languages are then presented, including towards verification, to help with decision problems, and with closure properties.