Program
Program
Times are GMT+2 (Time Zone of Paris, France)
Monday, Sept. 13th
Chair: Svetlana Puzynina
 14h15: Invited speaker
Zuzana Masáková (Czech Technical University in Prague, CZ)
Infinite words connected to numeration: βintegers and Erdös spectrum
The famous Fibonacci word as the `nicest’ of sturmian sequences can be presented in a number of ways. Each of the definitions leads to family of infinite words that have the Fibonacci word as its special case. In the talk we will present two of the definitions that are connected to numeration systems. One of the possibilities is to see the Fibonacci word as a coding of distances between consecutive numbers with integer expansion in the numeration system having for base the golden ratio τ=(1+√5)/2, the socalled τintegers. In general, βintegers with β being a Parry number provide an interesting family of pure morphic infinite words over a finite alphabet containing a class of sequences with affine factor complexity which do not belong to the category of interval exchange or ArnouxRauzy words. Another way to see the Fibonacci word in the frame of numeration systems is to consider the Erdös spectrum of τ. The spectrum of a real number β>1 with digit set D⊂R is defined as the set of polynomials with coefficients in D evaluated in β. If the base β is taken to be a Pisot number and the digits are consecutive integers including zero, the spectrum is a selfsimilar Delone set of finite local complexity which is coded by a morphic infinite word. We review the properties of such infinite words and show how geometric characteristics of the spectrum such as discreteness and relative density decide about good arithmetic behavior of the corresponding numeration system.
Watch video Download video
 15h15: Coffee break
Chair: Zuzana Masáková
 15h45: Sébastien Labbé and Jana Lepšová
A numeration system for Fibonaccilike Wang shifts
Motivated by the study of Fibonaccilike Wang shifts, we define a numeration system for Z and Z^{2} based on the binary alphabet {0,1}. We introduce a set of 16 Wang tiles that admits a valid tiling of the plane described by a deterministic finite automaton with output taking as input the representation of a position (m,n) in Z^{2} and outputing a Wang tile.
Download slides
 16h15: Elena Barcucci, Antonio Bernini and Renzo Pinzani
Strings from linear recurrences: a Gray code
Each strictly increasing sequence of positive integers can be used to define a numeration system so that any nonnegative integer can represented by a suitable and unique string of digits. We consider sequences defined by a two termed linear recurrence with constant coefficients having some particular properties and investigate on the possibility to define a Gray code for the set of the strings arising from them.
Watch video Download video Download slides
 16h45: Joe Sawada, Aaron Williams and Dennis Wong
Inside the Binary Reflected Gray Code: FlipSwap Languages in 2Gray Code Order
A flipswap language is a set S of binary strings of length n such that S ∪ 0^{n} is closed under two operations (when applicable): (1) Flip the leftmost 1; and (2) Swap the leftmost 1 with the bit to its right. Flipswap languages model many combinatorial objects including necklaces, Lyndon words, prefix normal words, left factors of kary Dyck words, and feasible solutions to 01 knapsack problems. We prove that any flipswap language forms a cyclic 2Gray code when listed in binary reflected Gray code (BRGC) order. Furthermore, a generic successor rule computes the next string when provided with a membership tester. The rule generates each string in the aforementioned flipswap languages in O(n)amortized per string, except for prefix normal words of length n which require O(n^{1.864})amortized per string. Our work generalizes results on necklaces and Lyndon words by Vajnovski [Inf. Process. Lett. 106(3):9699, 2008].
Watch video Download video Download slides
Tuesday, Sept. 14th
Chair: Aleksi Sareela
 9h30: Invited Speaker
Golnaz Badkobeh (Goldsmiths, University of London, UK)
Avoidability of Patterns
A pattern P is a string of variables. A string w avoids a pattern P, if for every substitution φ of the variables of P with nonempty words, φ(P) is not a factor of w. Thue initiated the study of avoidability by showing that there exists an infinite binary word that avoids pattern ABABA (overlaps), and an infinite ternary word that avoids pattern AA (squares). During the last century, this field of study has grown remarkably. This talk gives an overview of a selection of results concerning avoidability.
Watch video Download video
 10h30: Coffee break
Chair: Golnaz Badkobeh
 11h: Pascal Ochem
Doubled patterns with reversal are 3avoidable
In combinatorics on words, a word w over an alphabet Σ is said to avoid a pattern p over an alphabet Δ if there is no factor f of w such that f=h(p) where h:Δ^{*}→Σ^{*} is a nonerasing morphism. A pattern p is said to be kavoidable if there exists an infinite word over a kletter alphabet that avoids p. A pattern is doubled if every variable occurs at least twice. Doubled patterns are known to be 3avoidable. Currie, Mol, and Rampersad have considered a generalized notion which allows variable occurrences to be reversed. That is, h(V^{R}) is the mirror image of h(V) for every V∈Δ. We show that doubled patterns with reversal are 3avoidable.
Watch video Download video Download slides
 11h30: Marcella Anselmo, Manuela Flores and Maria Madonia
Quaternary ncubes and Isometric Words
A kary ncube is a graph with k^{n} vertices, each associated to a word of length n over an alphabet of cardinality k. The subgraph obtained deleting those vertices which contain a given kary word f as a factor is here introduced and called the kary ncube avoiding f. When, for any n, such a subgraph is isometric to the cube, the word $f$ is said isometric. In the binary case, isometric words can be equivalently defined, independently from hypercubes. A binary word f is isometric if and only if it is good, i.e., for any pair of ffree words u and v, u can be transformed in v by exchanging one by one the bits on which they differ and generating only ffree words. These two approaches are here considered in the case of a kary alphabet, showing that they are still coincident for k=3, but they are not from k=4 on. Bad words are then characterized in terms of their overlaps with errors. Further properties are obtained on nonisometric words and their index, in the case of a quaternary alphabet.
Download slides
 14h: Invited Speaker
Nathalie Aubrun (CNRS, Université ParisSaclay, FR)
1D substitutions as tilings and applications
In this talk I will present a graphical way to represent orbits of biinfinite words under the action of a onedimensional substitution. Then I will present two applications in symbolic dynamics on groups: one about surface groups and the other about amenable BaumslagSolitar groups. Based on a joint work with S. Barbierbi and E. Moutot and a joint work with M. Schraudner.
Watch video Download video
 15h: Coffee break
Chair: Nathalie Aubrun
 15h30: Vladislav Makarov
Counting ternary squarefree words quickly
An efficient, when compared to exhaustive enumeration, algorithm for computing the number of squarefree words of length n over the alphabet {a, b, c} is presented.
Watch video Download video
 16h: Simone Faro and Stefano Scafiti
The Range Automaton: An Efficient Approach to TextSearching
String matching is one of the most extensively studied problems in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last few decades a myriad of alternative solutions have been proposed, based on very different techniques. However automata have always played a very important role in the design of efficient string matching algorithms. In this paper we introduce the Range Automaton, a weak yet efficient variant of the nondeterministic suffix automaton of a string whose configuration can be encoded in a very simple form and which is particularly suitable to be used for solving textsearching problems. As a first example of its effectiveness we present an efficient string matching algorithm based on the Range Automaton, named Backward Range Automaton Matcher, which turns out to be very fast in many practical cases. Despite our algorithm has a quadratic worstcase time complexity, experimental results show that it obtains in most cases the best running times when compared against the most effective automata based algorithms. In the case of long patterns, the speedup reaches 250%. This makes our proposed solution one of the most flexible algorithms in practical cases.
Wednesday, Sept. 15th
Chair: Elena Barcucci
 14h: Szymon Łopaciuk and Daniel Reidenbach
On Billaud Words and Their Companions
The Billaud Conjecture, which has been open since 1993, is a fundamental problem on finite words w and their heirs, i.e., the words obtained by deleting every occurrence of a given letter from w. It posits that every morphically primitive word, i.e. a word which is a fixed point of the identity morphism only, has at least one morphically primitive heir. In this paper, we introduce and investigate the related class of socalled Billaud words, i.e. words whose all heirs are morphically imprimitive. We provide a characterisation of morphically imprimitive Billaud words, using a new concept. We show that there are two phenomena through which words can have morphically imprimitive heirs, and we highlight that only one of those occurs in morphically primitive words. Finally, we examine our concept further, use it to rephrase the Billaud Conjecture and study its difficulty.
Watch video Download video
 14h30: Dora Bulgakova, Nicolas Buzhinsky and Yegor Goncharov
On Balanced and Abelian Properties of Circular Words over a Ternary Alphabet
We revisit the question of classification of balanced circular words and focus on the case of a ternary alphabet. We propose a 3dimensional generalisation of the discrete approximation representation of Christoffel words. By considering the minimal bound 3 for abelian complexity of balanced circular words over a ternary alphabet, we provide a classification of all circular words over a ternary alphabet with abelian complexity subject to this bound. This result also allows us to construct an uncountable set of biinfinite aperiodic words with abelian complexity equal to 3.
 15h: Coffee break
Chair: Michel Rigo
 15h30: Mélodie Lapointe
Perfectly clustering words are primitive positive elements of the free group
A word over a totally ordered alphabet is perfectly clustering if its BurrowsWheeler transform is a nonincreasing word. A famous example of a family of perfectly clustering words are Christoffel words and their conjugates. In this paper, we show another similarity between perfectly clustering words and Christoffel words: Both are positive primitive elements of the free group.
Watch video Download video Download slides
 16h: Antonio Cafure and Eda Cesaratto
Binary cyclotomic polynomials: representation via words and algorithms
Cyclotomic polynomials are basic objects in Number Theory. Their properties depend on the number of distinct primes that intervenes in the factorization of their order, and the binary case is thus the first nontrivial case. This paper sees the vector of coefficients of the polynomial as a word on a ternary alphabet {1, +1, 0}. It designs an efficient algorithm that computes in a very efficient way a compact representation of this word. This algorithm is of linear time with respect to the size of the output, and, thus, optimal. Finally, we discuss how to recover known properties of coefficients of binary cyclotomic polynomials, as well as of coefficients of polynomials associated with numerical semigroups of dimension 2.
Watch video Download video
 16h30: Francesco Dolce, Lubomira Dvorakova and Edita Pelantova
Computation of critical exponent in balanced sequences
We study balanced sequences over a dletter alphabet. Each such sequence v is described by a Sturmian sequence and two constant gap sequences y and y'. We provide an algorithm which for a given y, y' and a quadratic slope of a Sturmian sequence computes the critical exponent of the balanced sequence v.
Watch video Download video
Thursday Sept. 16th
Chair: Jean Néraud
 14h: Invited Speaker
Jeffrey Shallit (University of Waterloo, CA)
Synchronized Sequences
The notion of synchronized sequence, introduced by Carpi and Maggi in 2001, has turned out to be a very useful tool for investigating the properties of words. In this paper I will prove some of the basic properties of synchronization, and give a number of applications to combinatorics on words.
Watch video Download video Download slides
 15h: Coffee break
Chair: Jeffrey Shallit
 15h30: Gwenaël Richomme and Patrice Séébold
A characterization of binary morphisms generating Lyndon infinite words
An infinite word is an infinite Lyndon word if it is smaller, with respect to the lexicographic order, than all its proper suffixes, or equivalently if it has infinitely many finite Lyndon words as prefixes. A characterization of binary endomorphisms generating Lyndon infinite words is provided.
Watch video Download video
 16h: Invited Speaker
Luca Zamboni (Université Claude Bernard Lyon 1, FR)
Colouring problems in infinite words
Given a finite colouring (or finite partition) of the free semigroup A^{+} over a set A, we consider various types of monochromatic factorisations of onesided infinite words x=x_{0}x_{1}x_{2}… in A^{ω}. We show how the existence of certain monochromatic factorisations can be used to characterise both periodicity and eventual periodicity in infinite words. This is joint work with MariaRomina Ivan and Imre Leader.
Friday, Sept. 17th
Chair: Luca Zamboni
 14h: Invited Speaker
Julien Leroy (Université de Liège, BE)
Rauzy graphs, Sadicity and dendricity
Rauzy graphs are a classical and powerful tool to understand combinatorial properties of an infinite word such as its factor complexity or the frequencies of its factors. In this talk, I will present an overview of known results using them. I will then focus on the class of (eventually) dendric words.
Watch video Download video
 15h: Coffee break
Chair: Julien Leroy
 15h30: Murphy Berzish, Joel Day, Vijay Ganesh, Mitja Kulczynski, Florin Manea, Federico Mora and Dirk Nowotka
String Theories Involving Regular Membership Predicates: From Practice to Theory and Back
Widespread use of string solvers in formal analysis of string heavy programs has led to a growing demand for more efficient and reliable techniques which can be applied in this context, especially for realworld cases. Designing an algorithm for the (generally undecidable) satisfiability problem for systems of string constraints requires a thorough understanding of the structure of constraints present in the targeted cases. In this paper, we investigate benchmarks presented in the literature containing regular expression membership predicates, extract different first order logic theories, and prove their decidability, resp. undecidability. Notably, the most common theories in realworld benchmarks are PSPACEcomplete and directly lead to the implementation of a more efficient algorithm to solving string constraints.
Watch video Download video
 16h: Markus Whiteland
Equations over the kbinomial monoids
Two finite words u and v are kbinomial equivalent if each word of length k appears equally many times in u and v as a subword, or scattered factor. We consider equations in the socalled kbinomial monoid defined by the kbinomial equivalence relation on words. We remark that the kbinomial monoid possesses the compactness property, namely, any system of equations has a finite equivalent subsystem. We further show an upper bound, depending on k and the size of the underlying alphabet, on the number of equations in such a finite subsystem. We further consider commutativity and conjugacy in the kbinomial monoids. We characterise 2binomial conjugacy and 2binomial commutativity. We also consider kbinomial commutativity for k>2.
 16h30: Closing
