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:20260422T225756Z UID:FLAT/1 DESCRIPTION:Title: Sto re languages of automata models\, with applications\nby Ian McQuillan (University of Saskatchewan) as part of One FLAT World Seminar\n\n\nAbstra ct\nThe 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 accep ting computation. While this is an older concept\, it is not a particularl y well-studied one. In this talk\, previous results regarding store langua ges from the literature are reviewed\, and the store languages of many exi sting types of automata from the literature are described. Several applica tions of store languages are then presented\, including towards verificati on\, to help with decision problems\, and with closure properties.\n LOCATION:https://researchseminars.org/talk/FLAT/1/ END:VEVENT BEGIN:VEVENT SUMMARY:Orna Kupferman (Hebrew University) DTSTART:20240306T140000Z DTEND:20240306T150000Z DTSTAMP:20260422T225756Z UID:FLAT/2 DESCRIPTION:Title: Usi ng the past for resolving the future\nby Orna Kupferman (Hebrew Univer sity) as part of One FLAT World Seminar\n\n\nAbstract\nNondeterminism mode ls an ability to see the future: An automaton with an infinite look ahead can successfully resolve its nondeterministic choices. An automaton is his tory deterministic (HD) if it can successfully resolve its nondeterministi c choices in a way that only depends on the past. Formally\, an HD automat on 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 a ll the words in the language of the automaton. Beyond being theoretically interesting and intriguing\, HD automata can replace deterministic automat a in several applications\, most notably reactive synthesis\, and they att ract a lot of interest in the research community. The talk describes the d evelopment of HD $\\omega$-regular automata\, relates history determinism to other types of bounded nondeterminism\, discuss the determinization of HD automata and their succinctness with respect to deterministic ones\, an d discusses variants\, extensions\, and open problems around HD automata.\ n LOCATION:https://researchseminars.org/talk/FLAT/2/ END:VEVENT BEGIN:VEVENT SUMMARY:Szilárd Zsolt Fazekas (Akita University) DTSTART:20240410T080000Z DTEND:20240410T090000Z DTSTAMP:20260422T225756Z UID:FLAT/3 DESCRIPTION:Title: Non -regular complexity\nby Szilárd Zsolt Fazekas (Akita University) as p art 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 steps pos sible in a system (machine\, grammar\, etc.) of type A are also possible i n systems of type B and the latter allow some operations that are not poss ible in the former. Such a relationship between models is exhibited by con text-free grammars as extensions of regular grammars\, or one-way jumping automata and automata with translucent letters as extensions of finite aut omata. The operations available in the extensions but not in the original model can be viewed as a computational resource and hence can be analyzed quantitatively\, similarly to computational complexity theory. Recent year s saw both the continuation of lines of inquiry from decades ago\, countin g the non-regular rules used in context-free derivations (Bordihn and Mitr ana\, '20)\, and the start of new ones\, counting the number of jumps/swee ps used during computations with the aforementioned extended automata mode ls (Fazekas and Mercaş\, '22-23\, Mitrana et al.\, '24). As the base mode l in all three cases generates/accepts the class of regular languages\, th e complexity notions introduced can be viewed as a measure of how non-regu lar a machine\, grammar or language is. In this talk I give an overview of the research concerning the hierarchies of language classes defined throu gh these non-regular complexity measures\, and propose some questions for further investigation.\n LOCATION:https://researchseminars.org/talk/FLAT/3/ END:VEVENT BEGIN:VEVENT SUMMARY:Jeffrey Shallit (University of Waterloo) DTSTART:20240508T130000Z DTEND:20240508T140000Z DTSTAMP:20260422T225756Z UID:FLAT/4 DESCRIPTION:Title: Usi ng automata to prove theorems about sequences\nby Jeffrey Shallit (Uni versity of Waterloo) as part of One FLAT World Seminar\n\n\nAbstract\nAuto mata 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 abo ut sequences\, and hence become a new and exciting tool for number theoris ts and combinatorialists. As an example\, I will talk about a sequence of Benoit Cloitre\, defined by a certain recurrence involving Fibonacci numbe rs. 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 sequences\, originally designed by Hamoon Mousavi.\n\nThis is joint work with Benoit Cloitre.\n LOCATION:https://researchseminars.org/talk/FLAT/4/ END:VEVENT BEGIN:VEVENT SUMMARY:Bruno Loff (University of Lisbon) DTSTART:20240605T130000Z DTEND:20240605T140000Z DTSTAMP:20260422T225756Z UID:FLAT/5 DESCRIPTION:Title: The hardness of decision tree complexity\nby Bruno Loff (University of Li sbon) as part of One FLAT World Seminar\n\n\nAbstract\nIn the world of for mal languages\, we have always been interested in the problem of finding t he smallest “algorithm” for deciding a given language. Moore’s algor ithm for DFA minimization is a standard part of a first course in theory o f computing. Jiang and Ravikumar have shown\, on the other hand\, that NFA minimization is PSPACE-hard.\n\nWe will discuss a related problem for the computational model of deterministic decision trees. Let $f$\nbe a Boolea n function given as either a truth table or as a circuit. In both of these cases\, how difficult is it to find the smallest complexity of a decision tree for computing $f$? (This is commonly known as the “query complexit y” of $f$). We will show that this problem is NC_1-hard and PSPACE-hard\ , respectively. The second bound is tight\, and the first bound is close t o being tight.\n LOCATION:https://researchseminars.org/talk/FLAT/5/ END:VEVENT BEGIN:VEVENT SUMMARY:Stefano Crespi Reghizzi (Politecnico di Milano and CNR-IEIIT) DTSTART:20241218T140000Z DTEND:20241218T150000Z DTSTAMP:20260422T225756Z UID:FLAT/6 DESCRIPTION:Title: Cro sswords of formal languages\nby Stefano Crespi Reghizzi (Politecnico d i Milano and CNR-IEIIT) as part of One FLAT World Seminar\n\n\nAbstract\nT he definition of crosswords as row-column combinations of words over an al phabet is\napplied to regular and context-free (CF) languages\, thus produ cing picture (2D)\nlanguages. The letter-to-letter projection of regular c rosswords coincides with the\nwell-known family of (tiling system) recogni zable pictures. Recent results for the CF case\,\nand especially for the D yck languages\, are presented\, that culminate in a generalized\nChomsky-S chützenberger Theorem (CST) for CF crosswords. CST represents the family\ nof pictures defined by projection of context-free crosswords\, while it f ully characterizes the\nmore general family where the crossword is applied to CF languages over two alphabets\,\nwhose Cartesian product becomes the picture alphabet. Dyck crosswords exhibit a rich\nspectrum of 2D patterns that combine the syntax trees of their CF components. Simpler\nDyck subfa milies generalize in 2D the well-nesting property of Dyck words.\n LOCATION:https://researchseminars.org/talk/FLAT/6/ END:VEVENT BEGIN:VEVENT SUMMARY:Martin Kutrib (Universität Gießen) DTSTART:20250219T140000Z DTEND:20250219T150000Z DTSTAMP:20260422T225756Z UID:FLAT/7 DESCRIPTION:Title: Cel lular automata: Communication matters\nby Martin Kutrib (Universität Gießen) as part of One FLAT World Seminar\n\n\nAbstract\nWe consider syst ems of a huge number of interacting finite automata as massively parallel systems.\nThe finite automata (also called cells) are arranged as one-dime nsional array and work synchronously\nat discrete time steps. Naturally\, the communication between the cells is necessary for non-trivial computati ons\nand\, in fact\, the amount of communication matters. Here\, we focus mainly on measuring the amount of\ncommunication quantitatively by the num ber of messages sent by the cells. Recent results on the computational\nca pacity as well as on decidability problems in such restricted cellular aut omata are discussed. In particular\,\nfundamental types of communication a re considered and the questions of how much communication is\nnecessary to accomplish a certain task and of whether there are communication hierarch ies are addressed.\nSince even for systems with drastically bounded commun ication many properties are undecidable\, another\nquestion is to what ext ent the systems have to be limited in order to regain decidable properties .\nWe present some selected results on these topics and want to draw atten tion to the overall picture and\nto some of the main ideas involved.\n LOCATION:https://researchseminars.org/talk/FLAT/7/ END:VEVENT BEGIN:VEVENT SUMMARY:Shinnosuke Seki (University of Electro-Communications\, Tokyo) DTSTART:20241120T140000Z DTEND:20241120T150000Z DTSTAMP:20260422T225756Z UID:FLAT/8 DESCRIPTION:Title: RNA co-transcriptionality - A platform for in vivo programming of molecular m achines\nby Shinnosuke Seki (University of Electro-Communications\, To kyo) as part of One FLAT World Seminar\n\n\nAbstract\nTranscription is a p rocess 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$) a ccording to the loss-less mapping $A \\to U$\, $C \\to G$\, $G \\to C$\, a nd $T \\to A$. The resulting RNA sequence\, called transcript\, folds upon itself while being transcribed. This co-transcriptional folding (CF) is d riven primarily by having helices form between complementary domains (fact ors)\, which bind with each other in the anti-parallel manner via base pai rs $A-U$\, $C-G$\, and $G-U$ and then twist\, and secondly by having helic es stacked coaxially. This platform has proven programmable in vitro by Ge ary\, Rothemund\, and Andersen\; indeed\, they demonstrated how to program a quasi-planar rectangular RNA tile into a transcript (in fact\, into its DNA template) and a single CF-pathway any other of which is hardly taken\ , guaranteeing a high success rate.\n\nThis “Hello World” program has brought up the following two problems among others:\n\n1. How can we progr am a computation on this platform\, that is\, how to design a transcript t hat accommodates multiple CF-pathways and takes one of them depending on a n input and what has folded so far?\n\n2. How can we maximize success rate by choosing a CF-pathway properly?\n\nThis talk will devote its first hal f to motivating these problems by providing background information on mole cular 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 Turi ng-universal computation on this platform by using a model of CF-driven co mputation called oritatami.\n LOCATION:https://researchseminars.org/talk/FLAT/8/ END:VEVENT BEGIN:VEVENT SUMMARY:Taylor Smith (St. Francis Xavier University) DTSTART:20250409T130000Z DTEND:20250409T140000Z DTSTAMP:20260422T225756Z UID:FLAT/9 DESCRIPTION:Title: Two -dimensional automata theory - Decidability\, complexity\, and algorithms< /a>\nby Taylor Smith (St. Francis Xavier University) as part of One FLAT W orld Seminar\n\n\nAbstract\nA two-dimensional (2D) automaton is a natural extension of the finite automaton model that operates on two-dimensional w ords\; 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 s tandard 2D automaton model is Turing-equivalent and thus more difficult to reason about\, recent work has focused on the properties of restricted va riants of 2D automata: namely\, variants where the input head can move in only three (or even two) directions through the input word.\nIn this talk\ , I will discuss some of the major results in the area of two-dimensional automata theory and draw connections between 2D automata and formal langua ge theory\, with a focus on the closure\, decidability\, and complexity pr operties of restricted variants of 2D automata. I will also present recent algorithmic work on computing efficient randomized approximate solutions to 2D decision problems that are computationally hard to solve. Throughout \, I will share a number of open problems that will guide the future study of 2D automaton models.\n LOCATION:https://researchseminars.org/talk/FLAT/9/ END:VEVENT BEGIN:VEVENT SUMMARY:Flavio D'Alessandro (Sapienza Università di Roma) DTSTART:20250430T130000Z DTEND:20250430T140000Z DTSTAMP:20260422T225756Z UID:FLAT/10 DESCRIPTION:Title: On the intersection problem for quantum finite automata\nby Flavio D'Ale ssandro (Sapienza Università di Roma) as part of One FLAT World Seminar\n \n\nAbstract\nIn this talk we consider the quantum finite automata accordi ng 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 t he decidability of the Emptiness problem (for languages accepted by the mo del with strict threshold) obtained by Blondel\, Jeandel\, Koiran\, and Po rtier\, and of one of its generalisation\, called the Intersection Problem \, obtained by Bertoni\, Choffrut et al. In this presentation\, we will hi ghlight\, in particular\, the role of algebraic groups in defining the afo rementioned decidability constructs\, and\, time permitting\, describe som e recent developments.\n LOCATION:https://researchseminars.org/talk/FLAT/10/ END:VEVENT BEGIN:VEVENT SUMMARY:Nelma Moreira (Universidade do Porto & CMUP) DTSTART:20250530T130000Z DTEND:20250530T140000Z DTSTAMP:20260422T225756Z UID:FLAT/11 DESCRIPTION:Title: Sy nchronised shuffles and team automata\nby Nelma Moreira (Universidade do Porto & CMUP) as part of One FLAT World Seminar\n\n\nAbstract\nThe shuf fle operation has been extensively studied in formal language theory.\nReg ular expressions with shuffle provide succinct representations for modelli ng concurrent systems. However\, even for regular languages\, shuffle is h ard: membership is NP-complete\, inequivalence is EXP-complete\, the conve rsion to NFAs is in the worst-case exponential\, and the conversion to DFA s is double exponential. There are also numerous open problems\, such as e stablishing tight bounds for state complexity even for the shuffle of two words.\nStandard shuffle models the pure interleaving of two concurrent sy stems. To model synchronisation\, and inspired in the Team Automata framew ork\, synchronised shuffle operators allow us to specify symbols on which the operands must or can synchronise instead of interleave. Intersection i s thus an extreme case of synchronisation.\nWe consider conversions of reg ular expressions with several generalised synchronised shuffle operators t o NFAs\, as well as studying some asymptotic average complexities.\n LOCATION:https://researchseminars.org/talk/FLAT/11/ END:VEVENT BEGIN:VEVENT SUMMARY:Stavros Konstantinidis (Saint Mary's University) DTSTART:20250618T120000Z DTEND:20250618T130000Z DTSTAMP:20260422T225756Z 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 Semina r\n\n\nAbstract\nThe first part of the talk deals with sets (languages) of all inputs $w\\in\\Sigma^*$ on which the output sets of two given transdu cers $S$ and $T$ differ\; formally $\\Delta(S\,T) = \\{ w\\in\\Sigma^* : S(w) \\neq T(w)\\}$\,\nwhere $S$ and $T$ are finite transducers (nondeterm inistic\, in general) with the same domain $\\Sigma$.\nHow hard is the pro blem $\\{(S\,T\,w) : S(w) ≠ T(w)\\}$ in general --- that is the problem of deciding whether $S(w) ≠ T(w)$ given $S$\, $T$\, and $w$ --- and when (at least) one of $S\,T$ is of a restricted type (e.g.\, finite-valued)?\ n\nDepending on restrictions on $S\,T$\, we have language classes like\n\n - $\\Delta(\\text{FINVAL}) = \\{\\Delta(S\,T) : S\,T$ are finite-valued$\\ }$ and\n\n- $\\Delta(\\text{FUNC}\,\\text{TR}) = \\{\\Delta(S\,T) : S$ is functional and $T$ is any transducer$\\}$.\n\nHow do these language classe s compare between themselves and between standard ones like $\\text{CSL}$\ , $\\text{OCL}$\, $\\text{NCM}$\, $\\text{NP}$?\n\n\nThe second part of th e talk deals with the recent method of PRAX algorithms for giving approxim ate answers to standard hard problems (in particular $\\text{PSPACE}$-comp lete ones like NFA universality) in polynomial time using randomization (s ampling). The method is meant to be easily and efficiently implementable. While the method is more meaningful in the context of information theory\, we also consider it in a broader theoretical context. For example\, we te st that the set of solutions of certain simple Diophantine equations is ap proximately empty with high probability.\n LOCATION:https://researchseminars.org/talk/FLAT/12/ END:VEVENT BEGIN:VEVENT SUMMARY:Ryan Williams (Massachusetts Institute of Technology (MIT)) DTSTART:20251015T130000Z DTEND:20251015T140000Z DTSTAMP:20260422T225756Z UID:FLAT/13 DESCRIPTION:Title: Si mulating time with square-root space\nby Ryan Williams (Massachusetts Institute of Technology (MIT)) as part of One FLAT World Seminar\n\n\nAbst ract\nWe show that for all functions $t(n) \\geq n$\, every multitape Turi ng machine running in time $t$ can be simulated using only $O(\\sqrt{t \\l og t})$ space. This is a substantial improvement over Hopcroft\, Paul\, an d Valiant's simulation of time $t$ in $O({t}/{\\log t})$ space from 50 yea rs ago [FOCS 1975\, JACM 1977]. Among other results\, our simulation impli es 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 explic it problems solvable in $O(n)$ space which require at least $n^2/poly(\\lo g n)$ time on every multitape Turing machine\, thereby making a little pro gress on the $\\text{P}$ versus $\\text{PSPACE}$ problem. Our simulation r educes the problem of simulating time-bounded multitape Turing machines to a series of implicitly-defined Tree Evaluation instances with nice parame ters\, leveraging the remarkable space-efficient algorithm for Tree Evalua tion recently found by Cook and Mertz [STOC 2024].\n LOCATION:https://researchseminars.org/talk/FLAT/13/ END:VEVENT BEGIN:VEVENT SUMMARY:Alexander Rubtsov (HSE University\, Russia) DTSTART:20251105T140000Z DTEND:20251105T150000Z DTSTAMP:20260422T225756Z UID:FLAT/14 DESCRIPTION:Title: Co mputational model for parsing expression grammars\nby Alexander Rubtso v (HSE University\, Russia) as part of One FLAT World Seminar\n\n\nAbstrac t\nParsing Expression Grammars (PEGs) have recently gained significant pra ctical relevance\, being adopted in compilers such as those for Python and Zig\, as well as in parsing libraries for many modern programming languag es. Despite their popularity\, the computational foundations of PEGs remai n less explored than those of classical grammar formalisms.\n\nIn this tal k\, I will present a new computational model for PEGs that extends determi nistic pushdown automata. This model enables a structural study of Parsing Expression Languages (PEL): in particular\, we show that PELs contain the Boolean closure of the regular closure of deterministic context-free lang uages (DCFLs) and are closed under left concatenation with this class.\n\n We also propose a two-way variation of the model. For this version\, we de velop a linear-time simulation algorithm\, analogous to Cook’s classical algorithm for two-way DPDAs. These results bridge the gap between theoret ical and practical aspects of PEGs\, offering a foundation for further com plexity-theoretic and algorithmic analysis.\n LOCATION:https://researchseminars.org/talk/FLAT/14/ END:VEVENT BEGIN:VEVENT SUMMARY:Nicola Prezza (Università Ca' Foscari Venezia) DTSTART:20251126T140000Z DTEND:20251126T150000Z DTSTAMP:20260422T225756Z UID:FLAT/15 DESCRIPTION:Title: Fr om text indexing to regular language indexing\nby Nicola Prezza (Unive rsità Ca' Foscari Venezia) as part of One FLAT World Seminar\n\n\nAbstra ct\nSince the invention of suffix sorting (in particular\, of suffix trees ) in the 70's\, the problem of indexed pattern matching has been heavily s tudied in the literature. This problem has a natural language-theoretic in terpretation: given a string $S$\, build a (linear-space) data structure a nswering membership queries in the substring closure of $S$. This interpre tation was recently made more interesting by several works showing that su ffix sorting can be naturally extended to some nonlinear structures\, nota bly labeled trees and de Bruijn graphs. This line of work culminated in th e invention of Wheeler automata\, a class of NFAs admitting efficient and elegant solutions to a large number of hard problems on automata (includin g membership). In this talk\, I will first give an introduction to the ric h theory of Wheeler automata and Wheeler languages. I will then show how t hese ideas can be generalized to arbitrary NFAs\, comparing this solution to other existing approaches for indexing arbitrary regular languages.\n LOCATION:https://researchseminars.org/talk/FLAT/15/ END:VEVENT BEGIN:VEVENT SUMMARY:Antonio Casares Santos (University of Kaiserslautern-Landau) DTSTART:20251217T140000Z DTEND:20251217T150000Z DTSTAMP:20260422T225756Z UID:FLAT/16 DESCRIPTION:Title: Tr ansition-based vs. state-based acceptance for automata over infinite words \nby Antonio Casares Santos (University of Kaiserslautern-Landau) as p art of One FLAT World Seminar\n\n\nAbstract\nIn the context of automata ov er infinite words\, acceptance is traditionally defined in terms of the st ates visited infinitely often during a run. However\, there is a growing t rend towards defining acceptance based on transitions rather than states.\ n\nIn this talk\, I will survey a number of results showing the striking d ifferences between the two models\, and provide arguments in favour of usi ng transitions as the standard acceptance method. Along the way\, we will revisit key historical results that have shaped the theory of automata ove r infinite words.\n LOCATION:https://researchseminars.org/talk/FLAT/16/ END:VEVENT BEGIN:VEVENT SUMMARY:Mikhail Volkov (Ural Federal University) DTSTART:20260225T140000Z DTEND:20260225T150000Z DTSTAMP:20260422T225756Z UID:FLAT/17 DESCRIPTION:Title: Ad versarial synchronization\nby Mikhail Volkov (Ural Federal University) as part of One FLAT World Seminar\n\n\nAbstract\nWe study a variant of th e synchronization game on finite deterministic\nautomata. In this game\, A lice chooses one input letter of an automaton\n$A$ on each of her moves wh ile Bob may respond with an arbitrary finite\nword over the input alphabet of $A$\; Alice wins if the word obtained by\ninterleaving her letters wit h Bob's responses resets $A$. We prove that\nif Alice has a winning strate gy in this game on $A$\, then $A$ admits a reset\nword whose length is str ictly smaller than the number of states of $A$.\nIn contrast\, for any $k$ \, we exhibit automata with shortest reset-word\nlength quadratic in the n umber of states\, on which Alice nevertheless\nwins a version of the game in which Bob's responses are restricted\nto arbitrary words of length at m ost $k$.\n\nWe provide polynomial-time algorithms for deciding the winner in various\nsynchronization games\, and we analyze the relationships betwe en variants\nof synchronization games on fixed-size automata.\n\nThis is a joint work with Anton Lipin.\n LOCATION:https://researchseminars.org/talk/FLAT/17/ END:VEVENT BEGIN:VEVENT SUMMARY:Klaus Sutner (Carnegie Mellon University) DTSTART:20260325T140000Z DTEND:20260325T150000Z DTSTAMP:20260422T225756Z UID:FLAT/18 DESCRIPTION:Title: Th e structure of Abelian automata\nby Klaus Sutner (Carnegie Mellon Univ ersity) as part of One FLAT World Seminar\n\n\nAbstract\nWe study invertib le Mealy automata acting on finite binary words\, viewed as automorphisms of the rooted infinite binary tree. We give a detailed structural characte rization of the automata whose associated automaton groups are free Abelia n\, and use Groebner bases to determine the linear “residuation matrix ” that encodes the recursive action of these automorphisms on subtrees.\ n\nThere are several natural decision problems associated with the orbits of the automorphisms defined by these automata\, such as orbit membership and the computation of “time stamps” (the first time a configuration a ppears along an orbit). We present some partial results concerning the com putational complexity of these problems. Finally\, we explore connections 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 Tim Be cker and Chris Grossack.\n LOCATION:https://researchseminars.org/talk/FLAT/18/ END:VEVENT BEGIN:VEVENT SUMMARY:Florin Manea (Georg-August Universität Göttingen) DTSTART:20260408T130000Z DTEND:20260408T140000Z DTSTAMP:20260422T225756Z UID:FLAT/19 DESCRIPTION:Title: Op timal enumeration of regular pattern matches\nby Florin Manea (Georg-A ugust Universität Göttingen) as part of One FLAT World Seminar\n\n\nAbst ract\nEnumerating all matches of a regular expression with capture variabl es (variable regex\, for short) to a document is a fundamental task in tex tual information extraction\, e.g.\, in connection to document spanners. S tate-of-the-art results [Amarilli et al.\, ACM TODS 2021] show how the mat ches of a variable regex\, representable by a sequential variable-set auto maton\, to a document can be enumerated with delay constant in the size of the document and polynomial in the size of the query\, after a preprocess ing requiring time linear in the size of the document and polynomial in th e size of the query.\n\nWe consider here the matching problem for regular expressions with capture variables which can be represented as regular pat terns: $w_0x_0 w_1x_1 \\cdots w_{k}x_k w_{k+1}$\, where\, for $i\\in \\{0\ ,\\ldots\,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 i n the intersection of information extraction and stringology\, as it can a lso 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 t ext $T$. We provide an optimal enumeration algorithm for this problem.\nAf ter a preprocessing requiring linear time in the size of the document $T$ and the size of the query pattern $\\alpha$\, we can enumerate all matches with worst-case constant delay (in combined complexity\, i.e.\, both in t he document- and the query-size).\n\nBased on: Paweł Gawrychowski\, Flori n Manea\, Stefan Siemer\, Paul Sarnighausen-Cahn.\n“Optimal Enumeration of Regular Pattern Matches\,”\nto appear in PODS 2026.\n LOCATION:https://researchseminars.org/talk/FLAT/19/ END:VEVENT BEGIN:VEVENT SUMMARY:Dmitry Chistikov (University of Warwick) DTSTART:20260429T130000Z DTEND:20260429T140000Z DTSTAMP:20260422T225756Z UID:FLAT/20 DESCRIPTION:Title: Th ree views on Presburger arithmetic\nby Dmitry Chistikov (University of Warwick) as part of One FLAT World Seminar\n\nInteractive livestream: htt ps://fc-up-pt.zoom.us/j/85946529834\nPassword hint: Subscribe to the maili ng list to receive the password\n\nAbstract\nLinear integer arithmetic\, a lso known as Presburger arithmetic\, is a logic\nthat allows one to expres s linear constraints on integers: equalities\,\ninequalities\, and divisib ility by fixed integers. Sets of natural numbers that\ncan be defined in t his logic are ultimately periodic sets. More generally\,\nthese are semi-l inear sets\, introduced in the 1960s by Parikh.\n\nThis talk will introduc e Presburger arithmetic and three methods for deciding\nwhether a given se ntence in it is true. These methods are rooted in geometry\,\nautomata the ory\, and symbolic computation\, respectively. We will also discuss\nhow t hese methods and ideas extend to other arithmetic theories and other\nprob lems (including some recent research results).\n LOCATION:https://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:20260422T225756Z UID:FLAT/21 DESCRIPTION:Title: Au tomata-based verification of quantum circuits\nby Ondřej Lengál (Brn o University of Technology) as part of One FLAT World Seminar\n\nInteracti ve livestream: https://fc-up-pt.zoom.us/j/85946529834\nPassword hint: Subs cribe to the mailing list to receive the password\n\nAbstract\nDevelopment of quantum programs is hard due to their intricate structure and inherent ly probabilistic nature. Computer-aided tool support is therefore essentia l. Computer-based reasoning over quantum programs is\, however\, also chal lenging due to the exponential size of the program's state. In this talk\, I will present a recent framework for automated formal verification of qu antum programs that uses automata to represent complex sets of quantum sta tes compactly.\n LOCATION:https://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:20260422T225756Z 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://researchseminars.org/talk/FLAT/22/ URL:https://fc-up-pt.zoom.us/j/85946529834 END:VEVENT END:VCALENDAR