13th International Conference on Words
13-17 Sep 2021 Rouen (France)

Accepted papers

    • Quaternary n-cubes and Isometric Words
      Marcella Anselmo, Manuela Flores and Maria Madonia
      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.

    • 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 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

    • 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 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.


    • 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 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.

    • The Range Automaton: An Efficient Approach to Text-Searching
      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 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.

    • A numeration system for Fibonacci-like Wang shifts
      Sébastien Labbé and Jana Lepšová
      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.

    • 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 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.

    • 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 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.

    • Counting ternary square-free words quickly
      Vladislav Makarov
      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.

    • Doubled patterns with reversal are 3-avoidable
      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 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.

    • 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:
      Flip-Swap Languages in 2-Gray Code Order

      Joe Sawada, Aaron Williams and Dennis Wong
      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].

    • Equations over the k-binomial monoids
      Markus Whiteland
      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.
Online user: 1 RSS Feed