- Deadline for submission (extended)
- April 29th, 2016
- Notification to authors
- June 1st, 2016
- Camera-ready version
- June 15th, 2016
- 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.