We have hosted two insightful research talks at Brno University of Technology. The events brought together local and international researchers to engage with the latest developments in theoretical computer science and system verification.
On July 17, we welcomed Dr. Yong Li from the Trustworthy Intelligent Systems Group at the Institute of Software, Chinese Academy of Sciences for a talk titled: “A Family of Finite Automata for Recognizing and Learning ω-Regular Languages” Dr. Li introduced a novel representation of ω-regular languages through families of deterministic finite automata (FDFAs). He presented a new model—limit FDFAs—which are more succinct than previous approaches and offer complementary strengths when used alongside recurrent FDFAs. The presentation also discussed practical trade-offs in automata design, such as increased succinctness at the cost of constructiveness, and proposed new directions for efficient automata construction using right congruences.
On July 18, Dr. Nicolas Mazzocchi from the Slovak University of Technology in Bratislava delivered a talk on “Temporal Explorability Games” In this presentation, Dr. Mazzocchi examined games played on temporal graphs, where edge availability is influenced by discrete time. He highlighted how game complexity changes significantly depending on whether an adversary is present and how the graph is specified. While solving explorability games on static graphs aligns with reachability games, on temporal graphs the complexity aligns with generalized reachability—becoming NP-complete for one-player and PSPACE-complete for two-player settings. The talk also explored symbolic representations of temporal graphs and their impact on computational hardness. Missed it? Play the recording [link: https://drive.google.com/file/d/17dKKu66pNUM4CgbQCuDJLuj73uEyn0LK/view?usp=sharing].