## Important dates

- Deadline for submission
**(extended)** - April 29th, 2016
- Notification to authors
- June 1st, 2016
- Camera-ready version
- June 15th, 2016
- Conference
- July 25th-28th, 2016

# Confirmed Invited Speakers

**Valérie Berthé** (Université Paris-Diderot, France)

*Tree sets: from bifix codes to algebraic word combinatorics*

*Abstract*: Tree sets are languages defined with regard to a tree property:
they are sets of factors of a family of infinite words that are defined in
terms of the possible left and right extensions of their factors, with their
extension graphs being trees. This class of words with linear factor complexity
includes classical families such as Sturmian words, interval exchanges or else
Arnoux-Rauzy words. We discuss here their combinatorial, ergodic and algebraic
properties. This includes algebraic properties of their return words, and of
maximal bifix codes defined with respect to their languages. This lecture is
based on joint work with C. De Felice, V. Delecroix, F. Dolce, J. Leroy, D.
Perrin, C. Reutenauer, G. Rindone.

*Bio*: Valérie Berthé is Senior Researcher in Computer Science at the French
National Centre for Scientific Research CNRS, in Paris (IRIF, Univ. Paris
7-Paris Diderot). She has written about 70 papers in symbolic dynamics, ergodic
theory, combinatorics on words and discrete geometry. She has been scientific
officer at CNRS in charge of the relations between Computer Science and
Mathematics from 2007 to 2010. From 2011 to 2015, she was Deputy Director of
the FSMP (Foundation for Mathematical Sciences of Paris), and she is a member
of the City of Paris' Scientific Council and of the CNRS's Scientific Council.

**Janusz A. (John) Brzozowski** (University of Waterloo, Canada)

*Title*: Towards a Theory of Complexity for Regular Languages

*Abstract*: The state complexity of a regular language is the number of states
in a complete minimal deterministic finite automaton (DFA) recognizing the
language. The state complexity of an operation on regular languages is the
maximal state complexity of the result of the operation as a function of the
state complexities of the operands. The state complexity of an operation gives
a worst-case lower bound on the time and space complexity of the operation, and
has been studied extensively for that reason. The first results on the state
complexity of union, concatenation, Kleene star and four other less often used
operations were stated without proof by Maslov in 1970, but this paper was
unknown in the West for many years. In 1994, Yu, Zhuang and K. Salomaa studied
the complexity of basic operations (union, intersection, concatenation, star
and reversal) and provided complete proofs. Since then, many authors obtained
numerous results for various subclasses of the class of regular languages, and
for various operations. Moreover, other measures of complexity, including the
size of the syntactic semigroup of a language, have been added. In this talk I
will summarize the results obtained in the past few years in the area of
complexity of regular languages and finite automata.

*Bio*: Janusz A. (John) Brzozowski was born in 1935 in Warsaw, Poland. He
received the BASc and MASc degrees in electrical engineering from the
University of Toronto in 1957 and 1959, respectively, and the MA and PhD
degrees in electrical engineering from Princeton University in 1962. He was
Assistant Professor from 1962 to 1965 and Associate Professor from 1965 to 1967
in the Department of Electrical Engineering, University of Ottawa. From 1967 to
1996 he was Professor in the Department of Computer Science, University of
Waterloo. In the periods 1978-1983 and 1987-1989 he was chair of that
department. In 1996 he received the title Distinguished Professor Emeritus
from the University of Waterloo, where he is also Adjunct Professor. In
2005 he was named Canadian Pioneer in Computing by IBM Canada. He
supervised student research for 54 years. Many of his advisees held,
or still hold, important positions in Canadian and foreign
universities, and also in industry. Six of his students won important
awards for their research. Dr. Brzozowski has published many papers
in the areas of regular languages, finite automata, asynchronous
circuits, and testing. He is co-author of Digital Networks
(Prentice-Hall, 1976), and of Asynchronous Circuits (Springer-Verlag,
1995). His present research interests include state complexity of
operations on regular languages, general complexity measures for
regular languages, most complex regular and sub-regular languages,
and nondeterministic finite automata.

**Émilie Charlier** (Université de Liège, Belgique)

*Title: Permutations and shifts*

*Abstract*: The entropy of a symbolic dynamical system is usually defined in
terms of the growth rate of the number of distinct allowed factors of length n.
Bandt, Keller and Pompe showed that, for piecewise monotone interval maps, the
entropy is also given by the number of permutations defined by consecutive
elements in the trajectory of a point. This result was the starting point of
several works of Elizalde where he investigates permutations in shift systems,
notably in full shifts and in beta-shifts. The goal of this talk is to survey
Elizalde's results. I will end by mentioning the case of negative beta-shifts,
which has been simultaneously studied by Elizalde and Moore on the one hand,
and by Steiner and myself on the other hand.

*Bio*: É. Charlier is first assistant at the Mathematics Department of the University of Liège in Belgium. She was a post-doc in the FiDiPro group of the Mathematics and Statistics Department of the University of Turku in Finland, and also a post-doc at the School of Computer Science of the University of Waterloo in Canada. She completed her PhD in 2009, in which she studied questions related to numerations systems. Since then, she has also been interested in combinatoric on words and symbolic dynamical systems, while keeping working in her original research domain.

**Cedric Chauve** (Simon Fraser University, Canada)

*Title: Counting, generating and sampling tree alignments*

*Abstract*: Pairwise alignment of ordered rooted trees is a natural extension
of the classical pairwise sequence alignment, with applications in several
fields, such as RNA secondary structure comparison for example. Motivated by
this application, and the need to explore the space of possibly sub-optimal
alignments, we introduce the notion of unambiguous tree alignment. We first
take an enumerative combinatorics point of view and propose a decomposition
scheme for unambiguous tree alignments, under the form of a context-free
grammar, that leads to precise asymptotic enumerative results, by mean of basic
analytic combinatorics. We then shift our focus to algorithmic questions, and
show our grammar can be refined into a dynamic programming algorithm for
sampling tree alignments under the Gibbs-Boltzmann probability distribution. We
also provide some surprising average case complexity results on the tree
alignment problem. This work, in collaboration with Yann Ponty and Julien
Courtiel, illustrates the potential of considering algorithmic questions from
the point of view of enumerating the solution space.

*Bio*: C. Chauve received his PhD in Theoretical Computer Science from Bordeaux
University in 2000, where he studied tree enumeration and pattern matching
problems under the direction of Serge Dulucq. He then moved to UQAM as an
assistant professor where he discovered bioinformatics under the mentorship of
Anne Bergeron. In 2005 he took a position in the Department of Mathematics of
Simon Fraser University, where he became professor in 2013, after receiving an
Habilitation from Bordeaux University in 2011. There he developed an on-going
research program in computational biology. Through a recent collaboration with
Yann Ponty, he returned to my old interest in tree algorithms, motivated by RNA
bioinformatics.