Exposés invités

  • Golnaz BADKOBEH (Londres, Royaume-Uni)

    Weird and Wonderful Words

    In this talk we will revisit a selected classes of words that have been discussed in the last two decades of Journées Montoises d'Informatique Théorique. This is not a comprehensive survey but an attempt to draw attention to only a few interesting words.

     

  • Gabriele FICI (Palerme, Italie)

    The Shortest Interesting Binary Words

    I will show that there exist two binary words (one of length 4 and one of length 6) that play a special role in many different problems in combinatorics on words. These two words may therefore be considered the shortest interesting binary words. My claim is supported by the fact that these two words appear in no less than 50 papers.

     

  • Matthieu ROSENFELD (Montpellier, France)

    Word reconstruction using queries on subwords or factors

    We consider the word reconstruction problem. In this setting, an oracle knows a secret word W, and you can make some queries to the oracle about W with the goal of  reconstructing W. In particular, we want to reconstruct W after the least possible number of queries.
    With Gwenaël Richomme, we considered the case where the allowed queries are "How many occurrences of u in W as a subword are there?", for any u. Fleischmann et a    l.  gave an algorithm that reconstructs any binary word W of length n in at most n/2 +1 queries. We prove that O((n log n)1/2) queries suffice in the worst case and that O(log n) queries suffices in the average case. In this talk, I will give a general introduction to this problem before focusing on this result.

     

  • Štěpán STAROSTA (Prague, République Tchèque)

    Formalizing languages generated by a morphism in Isabelle/HOL

    We present formalized proofs and the process of formalization of combinatorics on words results in the computer proof assistant Isabelle/HOL (as a part of the Combinatorics on Words Formalized project). The leading presented example is the claim and proof of finiteness of the number of primitive words of unbounded exponent in the language of a non-erasing morphic image of a fixed point. A word v is of unbounded exponent in a language if, for all integers k, the k-th power of v is an element of the language.

     

  • Manon STIPULANTI (Liège, Belgique)

    Binomial: coefficients, equivalence, complexity, and beyond

    In combinatorics on words, for two finite words u and v, the binomial coefficient of u and v is the number of times v appears as a subsequence of u (also called (scattered) subword). For example, with u = alphalpha and v = al, there are 36 ways to select 2 letters among 9, but only 3 of them give back v. Generalizing famous binomial coefficients of integers, the word version has recently received a lot of attention within the combinatorics-on-words community. In particular, a few years ago, in 2015, Michel Rigo and Pavel Salimov introduced the notion of binomial equivalence. This relation gives birth to a refinement of the usual abelian equivalence and Simon’s congruence. Very naturally, one can then associate the corresponding binomial complexity function which, for a given infinite word x, maps an integer n ≥ 0 to the number of length-n factors of x up to the k-binomial equivalence relation. In this talk, I will present a broad overview of the theory of binomial coefficients, equivalence, and complexity functions, focusing on some recent results obtained by Julien Leroy, Michel Rigo, Markus A. Whiteland, and myself.

     

     
Personnes connectées : 2 Vie privée
Chargement...