Accepted papers
 Quaternary ncubes and Isometric Words
Marcella Anselmo, Manuela Flores and Maria Madonia 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.
 Strings from linear recurrences: a Gray code
Elena Barcucci, Antonio Bernini and Renzo Pinzani 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
 String Theories involving Regular Membership Predicates:
From Practice to Theory and Back Murphy Berzish, Joel Day, Vijay Ganesh, Mitja Kulczynski, Florin Manea, Federico Mora and Dirk Nowotk 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.
 Binary cyclotomic polynomials: representation via words and algorithms
Antonio Cafure and Eda Cesaratto 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.
 Computation of critical exponent in balanced sequences
Francesco Dolce, Lubomira Dvorakova and Edita Pelantova 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.
 The Range Automaton: An Efficient Approach to TextSearching
Simone Faro and Stefano Scafiti 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.
 A numeration system for Fibonaccilike Wang shifts
Sébastien Labbé and Jana Lepšová 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.
 Perfectly clustering words are primitive positive elements of the free group
Mélodie Lapointe 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.
 On Billaud Words and Their Companions
Szymon Łopaciuk and Daniel Reidenbach 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.
 Counting ternary squarefree words quickly
Vladislav Makarov 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.
 Doubled patterns with reversal are 3avoidable
Pascal Ochem 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.
 A characterization of binary morphisms generating Lyndon infinite words
Gwenaël Richomme and Patrice Séébold 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.
 Inside the Binary Reflected Gray Code:
FlipSwap Languages in 2Gray Code Order Joe Sawada, Aaron Williams and Dennis Wong 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].
 Equations over the kbinomial monoids
Markus Whiteland 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.
