- Viliam Geffert (P. J. Šafárik University in Košice, Slovakia)
Unary Versus Binary Two-Way Automata
If L is a unary language, then its binary coded version bin(L) is a binary language containing all binary strings representing any 0x in L. It is known that if a unary language L is regular and can be recognized by a minimal one-way deterministic finite automaton (1DFA) with n states, then its binary coded version is also regular and can be recognized by a 1DFA with at most n states, but at least 1+log(n) states.
Here we shall present related results for two-way automata (2DFAs). First, we shall show that each unary 2DFA A’ with n states can be converted to a 2DFA A” recognizing bin(L(A’)) with at most O(n · log n) states. If A’ is minimal and uses only loops of odd lengths, A” will use at most 2n+2 states, but it must use at least n states. For each n>=7, we shall also present a unary witness language for which a minimal 2DFA uses exactly n states, but any minimal 2DFA recognizing its binary coded version uses at least n states, but less than n+log(n) states. - Marek Szykuła (University of Wrocław, Poland)
Synchronizing Automata: Open Problems and Recent Advances
This talk surveys state-of-the-art results and recent developments in the theory of synchronizing automata, centered around the famous Černý conjecture. A deterministic finite automaton is called synchronizing if it admits a reset word whose action maps all states to a single state. The Černý conjecture states that every synchronizing automaton with n states possesses a reset word of length at most (n-1)2. We will survey current open problems and dive into recent directions including completely reachable automata, the relationship between primitivity and synchronization, linear-algebraic methods, and practical algorithms for finding short reset words. The talk will also feature demonstrations of experimental tools for visualizing and exploring the underlying theoretical concepts. - Matthias Wendlandt (University of Giessen, Germany)
Subregular Expressions and Their Expressive Power
Regular expressions are classically built using concatenation, union, and Kleene star. Since regular languages are closed under many additional operations, these operations can also be incorporated into expressions without increasing expressive power. This talk investigates how the expressive capabilities change when alternative sets of operations are used instead of the classical ones.
We consider several variants of subregular expressions, obtained either by omitting standard operations or by replacing them with operations such as complementation or intersection. The talk presents an overview of recent results concerning the expressive power, structural properties, and closure behavior of the resulting language families.
Particular emphasis is placed on language families defined by restricted combinations of operations, including expressions using complement and star, concatenation and complement, or intersection and star, as well as several forms of concatenation-free expressions. We discuss formal characterizations of these families, compare unary and general alphabet cases, and study hierarchies induced by the available operations. The results reveal intricate relationships between the different language classes and provide new insights into the role of individual operations in the description of regular languages.
Home » Invited speakers