Kai Salomaa – State Complexity of Neighbourhoods of Regular Languages

Abstract:
The neighbourhood of a language consists of all strings that are within a given distance from some string of the language. Calude, Yu and K.S. (J.UCS 2002) have shown that neighbourhoods of regular languages with respect to an additive distance or quasi-distance are always regular. Edit-distance is the best known example of an additive distance. However, the original construction from 2002 yields only a very large finite automaton for the neighbourhood of a regular language and the state complexity of neighbourhoods has been investigated more recently. Also e.g. the prefix, suffix and infix distance, although not additive, preserve regularity in the above sense.

This talk surveys work on state complexity of neighbourhoods of regular languages and related questions, such as the state complexity of approximate pattern matching. Since complementation does not change the size of a deterministic finite automaton (DFA), the state complexity of the edit-distance neighbourhood of radius r gives also the optimal size of a DFA recognizing the set of strings having distance at least r+1 from any string of the language. Thus, the optimal size of a DFA for the neighbourhood of radius r can be viewed as the state complexity of error detection on a channel that introduces at most r errors.

A tight lower bound is known for the state complexity of edit-distance neighbourhoods. A limitation of the result is that the construction needs an alphabet that depends linearly on the number of states of the DFA. Constructing a DFA for a prefix distance neighbourhood does not incur an exponential size blow-up as is the case for edit-distance.  A tight state complexity lower bound for prefix distance neighbourhoods is given using an n state DFA over an alphabet of n-1 symbols. The general upper bound cannot be reached using a smaller alphabet.

Martin Kutrib – Reversibility in Finite-State Devices

Abstract:
Computing models that have a read-only input tape, may be equipped with further resources, and evolve in discrete time are considered from the viewpoint of logical reversibility. Since such abstract models may serve as prototypes of machines which can be physically constructed, and by the observation that loss of information results in heat dissipation, it is interesting to study computations without loss of information, that is, reversible computations. In essence, the reversibility of a deterministic computation means that every configuration has a unique successor configuration and a unique predecessor configuration.

The talk covers the notion of reversibility and its possible definitions. In which way is the predecessor configuration computed? Do we have to consider all possible configurations as potential predecessors? Or only configurations that are reachable from some initial configurations? We present some selected aspects as gradual reversibility, time-symmetry, and decidability as well as results on the computational and descriptional capacity of several logical reversible devices.

Thomas Colcombet – Hybrid-set-vector automata and gluing of categories

Abstract:
In this talk, we will introduce a novel quatitative form of automata: hybrid-set-vector automata. These are joint generalizations of deterministic finite state automata and automata weighted over a field. These automata enjoy the existence of (algebraically) minimal recognizers for a function (i.e. series), while being (in some sense) more compact than automata weighted over a field.

The description of why these good minimal recognizers exist is properly eplained at the level of categories. Hence, this talk will be the occasion to give a high-level overview of the categorical reasons for minimizability, and introduce informally the concept of gluing of categories that underlies the definition of hybrid-set-vector automata (as well as other forms of interesting automata models).

This is joint work with Daniela Petrişan.

Artur Jez – Recompression: new approach to word equations

Abstract:
Word equations is given by two strings over disjoint alphabets of letters and variables and we ask whether there is a substitution that satisfies this equation. Recently, a new \PSPACE{} solution to this problem was proposed, it is based on compressing simple substrings of the equation (replacing pairs $ab$ by a new symbol $c$, where $a\neq b$ and replacing maximal substrings $a^\ell$ by a new symbol $a_\ell$) and modifying the  equation so that such operations are sound; those modifications boil down to substitutions $X \to aX$ and $X\to Xb$.

The analysis focuses on the way the equation is stored and changed rather than on the combinatorics of words. This approach greatly simplified many existing proofs and algorithms. Moreover, it is also applicable to restricted cases (for instance: one-variable equations) and to generalisations (regular constraints, involution, partial commutation etc.). This approach was also recently used to show that satisfiability of word equations can be tested in nondeterministic linear space, thus showing that the satisfiability of word equations is context-sensitive.