BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Ian McQuillan (University of Saskatchewan)
DTSTART:20240207T140000Z
DTEND:20240207T150000Z
DTSTAMP:20260404T110957Z
UID:FLAT/1
DESCRIPTION:Title: Store languages of automata models\, with applications\nby Ian McQ
uillan (University of Saskatchewan) as part of One FLAT World Seminar\n\n\
nAbstract\nThe store language of an automaton is a language-theoretic enco
ding of the contents of every data store that can appear at any point in a
n accepting computation. While this is an older concept\, it is not a part
icularly well-studied one. In this talk\, previous results regarding store
languages from the literature are reviewed\, and the store languages of m
any existing types of automata from the literature are described. Several
applications of store languages are then presented\, including towards ver
ification\, to help with decision problems\, and with closure properties.\
n
LOCATION:https://stable.researchseminars.org/talk/FLAT/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Orna Kupferman (Hebrew University)
DTSTART:20240306T140000Z
DTEND:20240306T150000Z
DTSTAMP:20260404T110957Z
UID:FLAT/2
DESCRIPTION:Title: Using the past for resolving the future\nby Orna Kupferman (Hebrew
University) as part of One FLAT World Seminar\n\n\nAbstract\nNondetermini
sm 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 nondeter
ministic 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 b
e taken after the word is read and following this strategy results in acce
pting all the words in the language of the automaton. Beyond being theoret
ically interesting and intriguing\, HD automata can replace deterministic
automata in several applications\, most notably reactive synthesis\, and t
hey attract a lot of interest in the research community. The talk describe
s the development of HD $\\omega$-regular automata\, relates history deter
minism to other types of bounded nondeterminism\, discuss the determinizat
ion of HD automata and their succinctness with respect to deterministic on
es\, and discusses variants\, extensions\, and open problems around HD aut
omata.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Szilárd Zsolt Fazekas (Akita University)
DTSTART:20240410T080000Z
DTEND:20240410T090000Z
DTSTAMP:20260404T110957Z
UID:FLAT/3
DESCRIPTION:Title: Non-regular complexity\nby Szilárd Zsolt Fazekas (Akita Universit
y) as part of One FLAT World Seminar\n\n\nAbstract\nGiven a computational
model A\, we will call another model B an extension of A if computation st
eps possible in a system (machine\, grammar\, etc.) of type A are also pos
sible in systems of type B and the latter allow some operations that are n
ot possible in the former. Such a relationship between models is exhibited
by context-free grammars as extensions of regular grammars\, or one-way j
umping automata and automata with translucent letters as extensions of fin
ite automata. The operations available in the extensions but not in the or
iginal model can be viewed as a computational resource and hence can be an
alyzed quantitatively\, similarly to computational complexity theory. Rece
nt years saw both the continuation of lines of inquiry from decades ago\,
counting the non-regular rules used in context-free derivations (Bordihn a
nd Mitrana\, '20)\, and the start of new ones\, counting the number of jum
ps/sweeps used during computations with the aforementioned extended automa
ta models (Fazekas and Mercaş\, '22-23\, Mitrana et al.\, '24). As the ba
se model in all three cases generates/accepts the class of regular languag
es\, the complexity notions introduced can be viewed as a measure of how n
on-regular a machine\, grammar or language is. In this talk I give an over
view of the research concerning the hierarchies of language classes define
d through these non-regular complexity measures\, and propose some questio
ns for further investigation.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jeffrey Shallit (University of Waterloo)
DTSTART:20240508T130000Z
DTEND:20240508T140000Z
DTSTAMP:20260404T110957Z
UID:FLAT/4
DESCRIPTION:Title: Using automata to prove theorems about sequences\nby Jeffrey Shall
it (University of Waterloo) as part of One FLAT World Seminar\n\n\nAbstrac
t\nAutomata have proven very useful in practice\, both for text searching
and the analysis of various kinds of discrete systems. In this talk\, howe
ver\, I will show that they are also useful for (rigorously) proving theor
ems about sequences\, and hence become a new and exciting tool for number
theorists and combinatorialists. As an example\, I will talk about a seque
nce of Benoit Cloitre\, defined by a certain recurrence involving Fibonacc
i numbers. Many properties of this sequence were conjectured\, and using a
utomata we can now resolve all of them. The proofs are done using Walnut\,
a free open-source theorem-prover for automatic sequences\, originally de
signed by Hamoon Mousavi.\n\nThis is joint work with Benoit Cloitre.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bruno Loff (University of Lisbon)
DTSTART:20240605T130000Z
DTEND:20240605T140000Z
DTSTAMP:20260404T110957Z
UID:FLAT/5
DESCRIPTION:Title: The hardness of decision tree complexity\nby Bruno Loff (Universit
y of Lisbon) as part of One FLAT World Seminar\n\n\nAbstract\nIn the world
of formal languages\, we have always been interested in the problem of fi
nding the smallest “algorithm” for deciding a given language. Moore’
s algorithm for DFA minimization is a standard part of a first course in t
heory of computing. Jiang and Ravikumar have shown\, on the other hand\, t
hat NFA minimization is PSPACE-hard.\n\nWe will discuss a related problem
for the computational model of deterministic decision trees. Let $f$\nbe a
Boolean function given as either a truth table or as a circuit. In both o
f these cases\, how difficult is it to find the smallest complexity of a d
ecision tree for computing $f$? (This is commonly known as the “query co
mplexity” of $f$). We will show that this problem is NC_1-hard and PSPAC
E-hard\, respectively. The second bound is tight\, and the first bound is
close to being tight.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stefano Crespi Reghizzi (Politecnico di Milano and CNR-IEIIT)
DTSTART:20241218T140000Z
DTEND:20241218T150000Z
DTSTAMP:20260404T110957Z
UID:FLAT/6
DESCRIPTION:Title: Crosswords of formal languages\nby Stefano Crespi Reghizzi (Polite
cnico di Milano and CNR-IEIIT) as part of One FLAT World Seminar\n\n\nAbst
ract\nThe definition of crosswords as row-column combinations of words ove
r an alphabet is\napplied to regular and context-free (CF) languages\, thu
s producing picture (2D)\nlanguages. The letter-to-letter projection of re
gular crosswords coincides with the\nwell-known family of (tiling system)
recognizable pictures. Recent results for the CF case\,\nand especially fo
r the Dyck languages\, are presented\, that culminate in a generalized\nCh
omsky-Schützenberger Theorem (CST) for CF crosswords. CST represents the
family\nof pictures defined by projection of context-free crosswords\, whi
le it fully characterizes the\nmore general family where the crossword is
applied to CF languages over two alphabets\,\nwhose Cartesian product beco
mes the picture alphabet. Dyck crosswords exhibit a rich\nspectrum of 2D p
atterns that combine the syntax trees of their CF components. Simpler\nDyc
k subfamilies generalize in 2D the well-nesting property of Dyck words.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Martin Kutrib (Universität Gießen)
DTSTART:20250219T140000Z
DTEND:20250219T150000Z
DTSTAMP:20260404T110957Z
UID:FLAT/7
DESCRIPTION:Title: Cellular automata: Communication matters\nby Martin Kutrib (Univer
sität Gießen) as part of One FLAT World Seminar\n\n\nAbstract\nWe consid
er systems of a huge number of interacting finite automata as massively pa
rallel systems.\nThe finite automata (also called cells) are arranged as o
ne-dimensional array and work synchronously\nat discrete time steps. Natur
ally\, the communication between the cells is necessary for non-trivial co
mputations\nand\, in fact\, the amount of communication matters. Here\, we
focus mainly on measuring the amount of\ncommunication quantitatively by
the number of messages sent by the cells. Recent results on the computatio
nal\ncapacity as well as on decidability problems in such restricted cellu
lar automata are discussed. In particular\,\nfundamental types of communic
ation are considered and the questions of how much communication is\nneces
sary to accomplish a certain task and of whether there are communication h
ierarchies are addressed.\nSince even for systems with drastically bounded
communication many properties are undecidable\, another\nquestion is to w
hat extent the systems have to be limited in order to regain decidable pro
perties.\nWe present some selected results on these topics and want to dra
w attention to the overall picture and\nto some of the main ideas involved
.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shinnosuke Seki (University of Electro-Communications\, Tokyo)
DTSTART:20241120T140000Z
DTEND:20241120T150000Z
DTSTAMP:20260404T110957Z
UID:FLAT/8
DESCRIPTION:Title: RNA co-transcriptionality - A platform for in vivo programming of mole
cular machines\nby Shinnosuke Seki (University of Electro-Communicatio
ns\, Tokyo) as part of One FLAT World Seminar\n\n\nAbstract\nTranscription
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\, fol
ds upon itself while being transcribed. This co-transcriptional folding (C
F) is driven primarily by having helices form between complementary domain
s (factors)\, which bind with each other in the anti-parallel manner via b
ase pairs $A-U$\, $C-G$\, and $G-U$ and then twist\, and secondly by havin
g helices stacked coaxially. This platform has proven programmable in vitr
o by Geary\, Rothemund\, and Andersen\; indeed\, they demonstrated how to
program a quasi-planar rectangular RNA tile into a transcript (in fact\, i
nto its DNA template) and a single CF-pathway any other of which is hardly
taken\, guaranteeing a high success rate.\n\nThis “Hello World” progr
am has brought up the following two problems among others:\n\n1. How can w
e program a computation on this platform\, that is\, how to design a trans
cript that accommodates multiple CF-pathways and takes one of them dependi
ng on an input and what has folded so far?\n\n2. How can we maximize succe
ss rate by choosing a CF-pathway properly?\n\nThis talk will devote its fi
rst half to motivating these problems by providing background information
on molecular programming\, and particularly on helix-based RNA structures
such as hairpin and pseudoknot\, coaxial stacking among them\, CF-kinetics
\, and RNA triple (not double) helix. Its second half is on programming of
a Turing-universal computation on this platform by using a model of CF-dr
iven computation called oritatami.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Taylor Smith (St. Francis Xavier University)
DTSTART:20250409T130000Z
DTEND:20250409T140000Z
DTSTAMP:20260404T110957Z
UID:FLAT/9
DESCRIPTION:Title: Two-dimensional automata theory - Decidability\, complexity\, and algo
rithms\nby Taylor Smith (St. Francis Xavier University) as part of One
FLAT World Seminar\n\n\nAbstract\nA two-dimensional (2D) automaton is a n
atural extension of the finite automaton model that operates on two-dimens
ional 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 r
esults were established in the 1970s and 1980s\, but there has been a resu
rgence of interest in variants of the model in the past decade or so. Sinc
e the standard 2D automaton model is Turing-equivalent and thus more diffi
cult to reason about\, recent work has focused on the properties of restri
cted variants of 2D automata: namely\, variants where the input head can m
ove in only three (or even two) directions through the input word.\nIn thi
s talk\, I will discuss some of the major results in the area of two-dimen
sional automata theory and draw connections between 2D automata and formal
language theory\, with a focus on the closure\, decidability\, and comple
xity properties of restricted variants of 2D automata. I will also present
recent algorithmic work on computing efficient randomized approximate sol
utions to 2D decision problems that are computationally hard to solve. Thr
oughout\, I will share a number of open problems that will guide the futur
e study of 2D automaton models.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Flavio D'Alessandro (Sapienza Università di Roma)
DTSTART:20250430T130000Z
DTEND:20250430T140000Z
DTSTAMP:20260404T110957Z
UID:FLAT/10
DESCRIPTION:Title: On the intersection problem for quantum finite automata\nby Flavi
o D'Alessandro (Sapienza Università di Roma) as part of One FLAT World Se
minar\n\n\nAbstract\nIn 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\, descr
ibe some recent developments.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nelma Moreira (Universidade do Porto & CMUP)
DTSTART:20250530T130000Z
DTEND:20250530T140000Z
DTSTAMP:20260404T110957Z
UID:FLAT/11
DESCRIPTION:Title: Synchronised shuffles and team automata\nby Nelma Moreira (Univer
sidade do Porto & CMUP) as part of One FLAT World Seminar\n\n\nAbstract\nT
he shuffle operation has been extensively studied in formal language theor
y.\nRegular expressions with shuffle provide succinct representations for
modelling concurrent systems. However\, even for regular languages\, shuff
le is hard: membership is NP-complete\, inequivalence is EXP-complete\, th
e conversion to NFAs is in the worst-case exponential\, and the conversion
to DFAs is double exponential. There are also numerous open problems\, su
ch as establishing tight bounds for state complexity even for the shuffle
of two words.\nStandard shuffle models the pure interleaving of two concur
rent systems. To model synchronisation\, and inspired in the Team Automata
framework\, synchronised shuffle operators allow us to specify symbols on
which the operands must or can synchronise instead of interleave. Interse
ction is thus an extreme case of synchronisation.\nWe consider conversions
of regular expressions with several generalised synchronised shuffle oper
ators to NFAs\, as well as studying some asymptotic average complexities.\
n
LOCATION:https://stable.researchseminars.org/talk/FLAT/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stavros Konstantinidis (Saint Mary's University)
DTSTART:20250618T120000Z
DTEND:20250618T130000Z
DTSTAMP:20260404T110957Z
UID:FLAT/12
DESCRIPTION:Title: On the difference set of two transducers and PRAX algorithms\nby
Stavros Konstantinidis (Saint Mary's University) as part of One FLAT World
Seminar\n\n\nAbstract\nThe first part of the talk deals with sets (langua
ges) of all inputs $w\\in\\Sigma^*$ on which the output sets of two given
transducers $S$ and $T$ differ\; formally $\\Delta(S\,T) = \\{ w\\in\\Sigm
a^* : S(w) \\neq T(w)\\}$\,\nwhere $S$ and $T$ are finite transducers (no
ndeterministic\, in general) with the same domain $\\Sigma$.\nHow hard is
the problem $\\{(S\,T\,w) : S(w) ≠ T(w)\\}$ in general --- that is the p
roblem of deciding whether $S(w) ≠ T(w)$ given $S$\, $T$\, and $w$ --- a
nd when (at least) one of $S\,T$ is of a restricted type (e.g.\, finite-va
lued)?\n\nDepending on restrictions on $S\,T$\, we have language classes l
ike\n\n- $\\Delta(\\text{FINVAL}) = \\{\\Delta(S\,T) : S\,T$ are finite-va
lued$\\}$ and\n\n- $\\Delta(\\text{FUNC}\,\\text{TR}) = \\{\\Delta(S\,T) :
S$ is functional and $T$ is any transducer$\\}$.\n\nHow do these language
classes compare between themselves and between standard ones like $\\text
{CSL}$\, $\\text{OCL}$\, $\\text{NCM}$\, $\\text{NP}$?\n\n\nThe second par
t of the talk deals with the recent method of PRAX algorithms for giving a
pproximate answers to standard hard problems (in particular $\\text{PSPACE
}$-complete ones like NFA universality) in polynomial time using randomiza
tion (sampling). The method is meant to be easily and efficiently implemen
table. While the method is more meaningful in the context of information t
heory\, we also consider it in a broader theoretical context. For example\
, we test that the set of solutions of certain simple Diophantine equation
s is approximately empty with high probability.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ryan Williams (Massachusetts Institute of Technology (MIT))
DTSTART:20251015T130000Z
DTEND:20251015T140000Z
DTSTAMP:20260404T110957Z
UID:FLAT/13
DESCRIPTION:Title: Simulating time with square-root space\nby Ryan Williams (Massach
usetts Institute of Technology (MIT)) as part of One FLAT World Seminar\n\
n\nAbstract\nWe show that for all functions $t(n) \\geq n$\, every multita
pe Turing machine running in time $t$ can be simulated using only $O(\\sqr
t{t \\log t})$ space. This is a substantial improvement over Hopcroft\, Pa
ul\, and Valiant's simulation of time $t$ in $O({t}/{\\log t})$ space from
50 years ago [FOCS 1975\, JACM 1977]. Among other results\, our simulatio
n implies that bounded fan-in circuits of size $s$ can be evaluated on any
input in only $\\sqrt{s} \\cdot poly(\\log s)$ space\, and that there are
explicit problems solvable in $O(n)$ space which require at least $n^2/po
ly(\\log n)$ time on every multitape Turing machine\, thereby making a lit
tle progress on the $\\text{P}$ versus $\\text{PSPACE}$ problem. Our simul
ation reduces the problem of simulating time-bounded multitape Turing mach
ines to a series of implicitly-defined Tree Evaluation instances with nice
parameters\, leveraging the remarkable space-efficient algorithm for Tree
Evaluation recently found by Cook and Mertz [STOC 2024].\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Rubtsov (HSE University\, Russia)
DTSTART:20251105T140000Z
DTEND:20251105T150000Z
DTSTAMP:20260404T110957Z
UID:FLAT/14
DESCRIPTION:Title: Computational model for parsing expression grammars\nby Alexander
Rubtsov (HSE University\, Russia) as part of One FLAT World Seminar\n\n\n
Abstract\nParsing Expression Grammars (PEGs) have recently gained signific
ant practical relevance\, being adopted in compilers such as those for Pyt
hon and Zig\, as well as in parsing libraries for many modern programming
languages. Despite their popularity\, the computational foundations of PEG
s remain less explored than those of classical grammar formalisms.\n\nIn t
his talk\, I will present a new computational model for PEGs that extends
deterministic pushdown automata. This model enables a structural study of
Parsing Expression Languages (PEL): in particular\, we show that PELs cont
ain the Boolean closure of the regular closure of deterministic context-fr
ee languages (DCFLs) and are closed under left concatenation with this cla
ss.\n\nWe also propose a two-way variation of the model. For this version\
, we develop a linear-time simulation algorithm\, analogous to Cook’s cl
assical algorithm for two-way DPDAs. These results bridge the gap between
theoretical and practical aspects of PEGs\, offering a foundation for furt
her complexity-theoretic and algorithmic analysis.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nicola Prezza (Università Ca' Foscari Venezia)
DTSTART:20251126T140000Z
DTEND:20251126T150000Z
DTSTAMP:20260404T110957Z
UID:FLAT/15
DESCRIPTION:Title: From text indexing to regular language indexing\nby Nicola Prezza
(Università Ca' Foscari Venezia) as part of One FLAT World Seminar\n\n\
nAbstract\nSince the invention of suffix sorting (in particular\, of suffi
x trees) in the 70's\, the problem of indexed pattern matching has been he
avily studied in the literature. This problem has a natural language-theor
etic interpretation: given a string $S$\, build a (linear-space) data stru
cture answering membership queries in the substring closure of $S$. This i
nterpretation was recently made more interesting by several works showing
that suffix sorting can be naturally extended to some nonlinear structures
\, notably labeled trees and de Bruijn graphs. This line of work culminate
d in the invention of Wheeler automata\, a class of NFAs admitting efficie
nt and elegant solutions to a large number of hard problems on automata (i
ncluding membership). In this talk\, I will first give an introduction to
the rich theory of Wheeler automata and Wheeler languages. I will then sho
w how these ideas can be generalized to arbitrary NFAs\, comparing this so
lution to other existing approaches for indexing arbitrary regular languag
es.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Antonio Casares Santos (University of Kaiserslautern-Landau)
DTSTART:20251217T140000Z
DTEND:20251217T150000Z
DTSTAMP:20260404T110957Z
UID:FLAT/16
DESCRIPTION:Title: Transition-based vs. state-based acceptance for automata over infinit
e words\nby Antonio Casares Santos (University of Kaiserslautern-Landa
u) as part of One FLAT World Seminar\n\n\nAbstract\nIn the context of auto
mata over infinite words\, acceptance is traditionally defined in terms of
the states visited infinitely often during a run. However\, there is a gr
owing trend towards defining acceptance based on transitions rather than s
tates.\n\nIn this talk\, I will survey a number of results showing the str
iking differences between the two models\, and provide arguments in favour
of using transitions as the standard acceptance method. Along the way\, w
e will revisit key historical results that have shaped the theory of autom
ata over infinite words.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mikhail Volkov (Ural Federal University)
DTSTART:20260225T140000Z
DTEND:20260225T150000Z
DTSTAMP:20260404T110957Z
UID:FLAT/17
DESCRIPTION:Title: Adversarial synchronization\nby Mikhail Volkov (Ural Federal Univ
ersity) as part of One FLAT World Seminar\n\n\nAbstract\nWe study a varian
t of the synchronization game on finite deterministic\nautomata. In this g
ame\, Alice chooses one input letter of an automaton\n$A$ on each of her m
oves while Bob may respond with an arbitrary finite\nword over the input a
lphabet of $A$\; Alice wins if the word obtained by\ninterleaving her lett
ers with Bob's responses resets $A$. We prove that\nif Alice has a winning
strategy in this game on $A$\, then $A$ admits a reset\nword whose length
is strictly smaller than the number of states of $A$.\nIn contrast\, for
any $k$\, we exhibit automata with shortest reset-word\nlength quadratic i
n the number of states\, on which Alice nevertheless\nwins a version of th
e game in which Bob's responses are restricted\nto arbitrary words of leng
th at most $k$.\n\nWe provide polynomial-time algorithms for deciding the
winner in various\nsynchronization games\, and we analyze the relationship
s between variants\nof synchronization games on fixed-size automata.\n\nTh
is is a joint work with Anton Lipin.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Klaus Sutner (Carnegie Mellon University)
DTSTART:20260325T140000Z
DTEND:20260325T150000Z
DTSTAMP:20260404T110957Z
UID:FLAT/18
DESCRIPTION:Title: The structure of Abelian automata\nby Klaus Sutner (Carnegie Mell
on University) as part of One FLAT World Seminar\n\n\nAbstract\nWe study i
nvertible Mealy automata acting on finite binary words\, viewed as automor
phisms of the rooted infinite binary tree. We give a detailed structural c
haracterization of the automata whose associated automaton groups are free
Abelian\, and use Groebner bases to determine the linear “residuation m
atrix” that encodes the recursive action of these automorphisms on subtr
ees.\n\nThere are several natural decision problems associated with the or
bits of the automorphisms defined by these automata\, such as orbit member
ship and the computation of “time stamps” (the first time a configurat
ion appears along an orbit). We present some partial results concerning th
e computational complexity of these problems. Finally\, we explore connect
ions with canonical normal forms in the associated numeration systems\, in
the spirit of Knuth’s work from the 1960s.\n\nThis is joint work with T
im Becker and Chris Grossack.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Florin Manea (Georg-August Universität Göttingen)
DTSTART:20260408T130000Z
DTEND:20260408T140000Z
DTSTAMP:20260404T110957Z
UID:FLAT/19
DESCRIPTION:Title: Optimal enumeration of regular pattern matches\nby Florin Manea (
Georg-August Universität Göttingen) as part of One FLAT World Seminar\n\
nInteractive livestream: https://fc-up-pt.zoom.us/j/85946529834\nPassword
hint: Subscribe to the mailing list to receive the password\n\nAbstract\nE
numerating all matches of a regular expression with capture variables (var
iable regex\, for short) to a document is a fundamental task in textual in
formation extraction\, e.g.\, in connection to document spanners. State-of
-the-art results [Amarilli et al.\, ACM TODS 2021] show how the matches of
a variable regex\, representable by a sequential variable-set automaton\,
to a document can be enumerated with delay constant in the size of the do
cument and polynomial in the size of the query\, after a preprocessing req
uiring time linear in the size of the document and polynomial in the size
of the query.\n\nWe consider here the matching problem for regular express
ions with capture variables which can be represented as regular patterns:
$w_0x_0 w_1x_1 \\cdots w_{k}x_k w_{k+1}$\, where\, for $i\\in \\{0\,\\ldot
s\,k+1\\}$\, $w_i$ is a string of terminal letters and\, for $i\\in \\{0\,
\\ldots\,k\\}$\, $x_i$ is a variable. This problem naturally lies in the i
ntersection of information extraction and stringology\, as it can also be
seen as computing all the ways in which $k+1$ given strings $w_0\,\\ldots\
,w_{k+1}$ occur\, in this order and without overlaps\, in a given text $T$
. We provide an optimal enumeration algorithm for this problem.\nAfter a p
reprocessing requiring linear time in the size of the document $T$ and the
size of the query pattern $\\alpha$\, we can enumerate all matches with w
orst-case constant delay (in combined complexity\, i.e.\, both in the docu
ment- and the query-size).\n\nBased on: Paweł Gawrychowski\, Florin Manea
\, Stefan Siemer\, Paul Sarnighausen-Cahn.\n“Optimal Enumeration of Regu
lar Pattern Matches\,”\nto appear in PODS 2026.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/19/
URL:https://fc-up-pt.zoom.us/j/85946529834
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dmitry Chistikov (University of Warwick)
DTSTART:20260429T130000Z
DTEND:20260429T140000Z
DTSTAMP:20260404T110957Z
UID:FLAT/20
DESCRIPTION:by Dmitry Chistikov (University of Warwick) as part of One FLA
T World Seminar\n\nInteractive livestream: https://fc-up-pt.zoom.us/j/8594
6529834\nPassword hint: Subscribe to the mailing list to receive the passw
ord\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/20/
URL:https://fc-up-pt.zoom.us/j/85946529834
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ondřej Lengál (Brno University of Technology)
DTSTART:20260520T130000Z
DTEND:20260520T140000Z
DTSTAMP:20260404T110957Z
UID:FLAT/21
DESCRIPTION:Title: Automata-based verification of quantum circuits\nby Ondřej Leng
ál (Brno University of Technology) as part of One FLAT World Seminar\n\nI
nteractive livestream: https://fc-up-pt.zoom.us/j/85946529834\nPassword hi
nt: Subscribe to the mailing list to receive the password\n\nAbstract\nDev
elopment of quantum programs is hard due to their intricate structure and
inherently probabilistic nature. Computer-aided tool support is therefore
essential. Computer-based reasoning over quantum programs is\, however\, a
lso challenging due to the exponential size of the program's state. In thi
s talk\, I will present a recent framework for automated formal verificati
on of quantum programs that uses automata to represent complex sets of qua
ntum states compactly.\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/21/
URL:https://fc-up-pt.zoom.us/j/85946529834
END:VEVENT
BEGIN:VEVENT
SUMMARY:Markus Holzer (Justus-Liebig-Universität Gießen)
DTSTART:20260610T130000Z
DTEND:20260610T140000Z
DTSTAMP:20260404T110957Z
UID:FLAT/22
DESCRIPTION:by Markus Holzer (Justus-Liebig-Universität Gießen) as part
of One FLAT World Seminar\n\nInteractive livestream: https://fc-up-pt.zoom
.us/j/85946529834\nPassword hint: Subscribe to the mailing list to receive
the password\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/FLAT/22/
URL:https://fc-up-pt.zoom.us/j/85946529834
END:VEVENT
END:VCALENDAR