One FLAT World Seminar

On the intersection problem for quantum finite automata

Speaker: Flavio D'Alessandro

April 30, 2025

In this talk we consider the quantum finite automata according to the model “measure-once” introduced by Moore and Crutchfield in the late 90’s. More precisely, we are interested in some results that prove the decidability of the Emptiness problem (for languages accepted by the model with strict threshold) obtained by Blondel, Jeandel, Koiran, and Portier, and of one of its generalisation, called the Intersection Problem, obtained by Bertoni, Choffrut et al. In this presentation, we will highlight, in particular, the role of algebraic groups in defining the aforementioned decidability constructs, and, time permitting, describe some recent developments.

Two-dimensional automata theory

Decidability, complexity, and algorithms

Speaker: Taylor Smith

April 9, 2025

A two-dimensional (2D) automaton is a natural extension of the finite automaton model that operates on two-dimensional words; that is, on arrays or matrices of symbols. The 2D automaton model has a long history dating back to the 1960s and many of the major results were established in the 1970s and 1980s, but there has been a resurgence of interest in variants of the model in the past decade or so. Since the standard 2D automaton model is Turing-equivalent and thus more difficult to reason about, recent work has focused on the properties of restricted variants of 2D automata: namely,... [Read More]

Cellular automata

Communication matters

Speaker: Martin Kutrib

February 19, 2025

We consider systems of a huge number of interacting finite automata as massively parallel systems. The finite automata (also called cells) are arranged as one-dimensional array and work synchronously at discrete time steps. Naturally, the communication between the cells is necessary for non-trivial computations and, in fact, the amount of communication matters. Here, we focus mainly on measuring the amount of communication quantitatively by the number of messages sent by the cells. Recent results on the computational capacity as well as on decidability problems in such restricted cellular automata are discussed. In particular, fundamental types of communication are considered and... [Read More]

Crosswords of formal languages

Speaker: Stefano Crespi Reghizzi

December 18, 2024

The definition of crosswords as row-column combinations of words over an alphabet is applied to regular and context-free (CF) languages, thus producing picture (2D) languages. The letter-to-letter projection of regular crosswords coincides with the well-known family of (tiling system) recognizable pictures. Recent results for the CF case, and especially for the Dyck languages, are presented, that culminate in a generalized Chomsky-Schützenberger Theorem (CST) for CF crosswords. CST represents the family of pictures defined by projection of context-free crosswords, while it fully characterizes the more general family where the crossword is applied to CF languages over two alphabets, whose Cartesian product... [Read More]

RNA co-transcriptionality

A platform for in vivo programming of molecular machines

Speaker: Shinnosuke Seki

November 20, 2024

Transcription is a process in which an RNA sequence (of bases of 4 types \(A\), \(C\), \(G\), \(U\)) is synthesized from a DNA template sequence (of \(A\), \(C\), \(G\), \(T\)) according to the loss-less mapping \(A \to U\), \(C \to G\), \(G \to C\), and \(T \to A\). The resulting RNA sequence, called transcript, folds upon itself while being transcribed. This co-transcriptional folding (CF) is driven primarily by having helices form between complementary domains (factors), which bind with each other in the anti-parallel manner via base pairs \(A-U\), \(C-G\), and \(G-U\) and then twist, and secondly by having helices stacked... [Read More]

The hardness of decision-tree complexity

Speaker: Bruno Loff

June 5, 2024

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

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

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

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

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.