BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Taylor Smith (St. Francis Xavier University)
DTSTART:20250409T130000Z
DTEND:20250409T140000Z
DTSTAMP:20260423T035729Z
UID:FLAT/9
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/FLAT/9/">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
END:VCALENDAR