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 so-called τ-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 Arnoux-Rauzy 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 self-similar 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 Fibonacci-like Wang shifts
Motivated by the study of Fibonacci-like Wang shifts, we define a numeration system for Z and Z2 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 Z2 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 non-negative 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: Flip-Swap Languages in 2-Gray Code Order
A flip-swap language is a set S of binary strings of length n such that S ∪ 0n is closed under two operations (when applicable): (1) Flip the leftmost 1; and (2) Swap the leftmost 1 with the bit to its right. Flip-swap languages model many combinatorial objects including necklaces, Lyndon words, prefix normal words, left factors of k-ary Dyck words, and feasible solutions to 0-1 knapsack problems. We prove that any flip-swap language forms a cyclic 2-Gray 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 flip-swap languages in O(n)-amortized per string, except for prefix normal words of length n which require O(n1.864)-amortized per string. Our work generalizes results on necklaces and Lyndon words by Vajnovski [Inf. Process. Lett. 106(3):96-99, 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 non-empty 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 3-avoidable
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 non-erasing morphism. A pattern p is said to be k-avoidable if there exists an infinite word over a k-letter alphabet that avoids p. A pattern is doubled if every variable occurs at least twice. Doubled patterns are known to be 3-avoidable. Currie, Mol, and Rampersad have considered a generalized notion which allows variable occurrences to be reversed. That is, h(VR) is the mirror image of h(V) for every V∈Δ. We show that doubled patterns with reversal are 3-avoidable.
Watch video Download video Download slides
- 11h30: Marcella Anselmo, Manuela Flores and Maria Madonia
Quaternary n-cubes and Isometric Words
A k-ary n-cube is a graph with kn 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 k-ary word f as a factor is here introduced and called the k-ary n-cube 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 f-free words u and v, u can be transformed in v by exchanging one by one the bits on which they differ and generating only f-free words. These two approaches are here considered in the case of a k-ary 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 non-isometric words and their index, in the case of a quaternary alphabet.
Download slides
- 14h: Invited Speaker
Nathalie Aubrun (CNRS, Université Paris-Saclay, FR)
1D substitutions as tilings and applications
In this talk I will present a graphical way to represent orbits of bi-infinite words under the action of a one-dimensional substitution. Then I will present two applications in symbolic dynamics on groups: one about surface groups and the other about amenable Baumslag-Solitar 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 square-free words quickly
An efficient, when compared to exhaustive enumeration, algorithm for computing the number of square-free 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 Text-Searching
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 non-deterministic 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 text-searching 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 worst-case 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 speed-up 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 so-called 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 3-dimensional 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 bi-infinite 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 Burrows-Wheeler transform is a non-increasing 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 d-letter 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 one-sided infinite words x=x0x1x2… 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 Maria-Romina Ivan and Imre Leader.
Friday, Sept. 17th
Chair: Luca Zamboni
- 14h: Invited Speaker
Julien Leroy (Université de Liège, BE)
Rauzy graphs, S-adicity 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 real-world 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 real-world benchmarks are PSPACE-complete 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 k-binomial monoids
Two finite words u and v are k-binomial 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 so-called k-binomial monoid defined by the k-binomial equivalence relation on words. We remark that the k-binomial 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 k-binomial monoids. We characterise 2-binomial conjugacy and 2-binomial commutativity. We also consider k-binomial commutativity for k>2.
- 16h30: Closing
|
