Presentation

ALFA'15 is the third edition of the workshop on Automata, Logic, Formal languages, and Algebra. The two previous editions took place

  • in Riga, Latvia, July 7, 2013,
  • in Stellenbosch, South Africa, December 14, 2013.

The third edition takes place in Bordeaux, June 15-16-17 2015, and it co-organized together with the University of Leipzig.

Scope

The study of regular languages has a long tradition. The roots of the theory go back to the mid 1950s. Kleene’s famous theorem states that finite state automata and regular expressions have the same expressive power. Shortly after, Rabin and Scott introduced nondeterministic automata, and Myhill and Nerode characterized regular languages by congruences of finite index. Büchi, Elgot, and Trakhtenbrot have shown that monadic second order logic defines the class of regular languages. Since then, automata and regular languages have become one of the most fundamental concepts in computer science. The algebraic counterpart of regular languages are finite monoids, and in many cases they are the key ingredient for solving decidability problems in this area.

The interest in combining algebra and automata is increasing and impacts different areas of research. An effective characterization of the third level of the quantifier alternation hierarchy of first-order logic was obtained recently, exploiting algebraic and combinatorial techniques. In the field of equations over groups such as context-free and hyperbolic groups, tools from automata theory played an essential role. In connection with compression algorithms, the word problem in automorphism groups of free groups was shown to be decidable in polynomial time. Right-angled Artin groups play a fundamental role in group theory and are studied under formal language aspects in computer science, since the underlying partially commutative structure is used to model concurrent systems.

The workshop intends to bring together researchers who are working at the crossing of these areas. The aim of this workshop is to present ongoing research and new results within these lines of work. This includes extensions to other models (such as trees or graphs) and connections to other areas such as combinatorics on words. The workshop program consists of invited talks only.