•  Viliam Geffert, Košice, Slovakia

Title: Binary Coded Unary Regular Languages

Abstract: L is a binary coded unary regular language, if there exists a unary regular language L' such that a^x is in L' if and only if the binary representation of x is in L. If a unary language L' is accepted by an optimal deterministic finite automaton (DFA) A' with n states, then its binary coded version L is regular and can be accepted by a DFA A using at most n states, but at least 1+log(n) states. There are witness languages matching these upper and lower bounds exactly, for each n.

We shall also present a more precise analysis, depending on the size of the initial segment and on the factorization of the loop length in the unary A'.
The conversion in the opposite way is not always granted: there are binary regular languages the unary versions of which are not even context free.

The corresponding conversion of a unary nondeterministic finite automaton (NFA) to a binary NFA uses O(n^2) states and introduces a binary version of Chrobak normal form.

To access the version that includes mathematical formulated, click on this link.

•  Friedrich Otto, Kassel, Germany

 Title: A Survey on Automata with Translucent Letters

Abstract: In this survey we present the various types of automata with translucent letters that have been studied in the literature. These include the finite automata and the pushdown automata with translucent letters, which are obtained as reinterpretations of certain cooperating distributed systems of a restricted type of restarting automaton, the linear automaton with translucent letters, and the visibly pushdown automaton with translucent letters. For each of these types of automata with translucent letters, it has been shown that they accept those trace languages which are obtained from the class of languages that is accepted by the corresponding type of automaton without translucent letters.

• Cem Say, Istanbul, Türkiye
  

 Title: Finite automata as verifiers

Abstract: An interactive proof system is characterized by the computational abilities of its two components (called the "prover" and the "verifier") and the nature of the interaction between them. The verifier is the weaker party, who is supposed to be able to check the claims of the more powerful prover. We focus on the weakest possible kind of computational model, namely, the finite automaton, in the role of the verifier. We will provide an overview of the literature and talk about recent work involving new concepts, like constant-randomness machines and thermodynamic complexity considerations.