##
Post-edited
Applications of algebra to automatic sequences and pattern avoidance - Lecture 1

Bell, Jason P. (Auteur de la Conférence) | CIRM (Editeur )

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Bell, Jason P. (Auteur de la Conférence) | CIRM (Editeur )

We will cover some of the more important results from commutative and noncommutative algebra as far as applications to automatic sequences, pattern avoidance, and related areas. Well give an overview of some applications of these areas to the study of automatic and regular sequences and combinatorics on words.

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Rigo, Michel (Auteur de la Conférence) | CIRM (Editeur )

The general aim of these lectures is to present some interplay between combinatorial game theory (CGT) and combinatorics on (multidimensional) words.

In the first introductory lecture, we present some basic concepts from combinatorial game theory (positions of a game, Nim-sum, Sprague-Grundy function, Wythoff’s game, ...). We also review some concepts from combinatorics on words. We thus introduce the well-known k-automatic sequences and review some of their characterizations (in terms of morphisms, finiteness of their k-kernel,...). These sequences take values in a finite set but the Sprague-Grundy function of a game, such as Nim of Wythoff, is usually unbounded. This provides a motivation to introduce k-regular sequences (in the sense of Allouche and Shallit) whose k-kernel is not finite, but finitely generated.

In the second lecture, games played on several piles of token naturally give rise to a multi-dimensional setting. Thus, we reconsider k-automatic and k-regular sequences in this extended framework. In particular, determining the structure of the bidimensional array encoding the (loosing) P-positions of the Wythoff’s game is a long-standing and challenging problem in CGT. Wythoff’s game is linked to non-standard numeration system: P-positions can be determined by writing those in the Fibonacci system. Next, we present the concept of shape-symmetric morphism: instead of iterating a morphism where images of letters are (hyper-)cubes of a fixed length k, one can generalize the procedure to images of various parallelepipedic shape. The shape-symmetry condition introduced twenty years ago by Maes permits to have well-defined fixed point.

In the last lecture, we move to generalized numeration systems: abstract numeration systems (built on a regular language) and link them to morphic (multidimensional) words. In particular, pictures obtained by shape-symmetric morphisms coincide with automatic sequences associated with an abstract numeration system. We conclude these lectures with some work in progress about games with a finite rule-set. This permits us to discuss a bit Presburger definable sets. The general aim of these lectures is to present some interplay between combinatorial game theory (CGT) and combinatorics on (multidimensional) words.

In the first introductory lecture, we present some basic concepts from combinatorial game theory (positions of a game, Nim-sum, Sprague-Grundy function, Wythoff’s game, ...). We also review some concepts from combinatorics on words. We thus introduce the well-known k-automatic sequences and review ...

In the first introductory lecture, we present some basic concepts from combinatorial game theory (positions of a game, Nim-sum, Sprague-Grundy function, Wythoff’s game, ...). We also review some concepts from combinatorics on words. We thus introduce the well-known k-automatic sequences and review some of their characterizations (in terms of morphisms, finiteness of their k-kernel,...). These sequences take values in a finite set but the Sprague-Grundy function of a game, such as Nim of Wythoff, is usually unbounded. This provides a motivation to introduce k-regular sequences (in the sense of Allouche and Shallit) whose k-kernel is not finite, but finitely generated.

In the second lecture, games played on several piles of token naturally give rise to a multi-dimensional setting. Thus, we reconsider k-automatic and k-regular sequences in this extended framework. In particular, determining the structure of the bidimensional array encoding the (loosing) P-positions of the Wythoff’s game is a long-standing and challenging problem in CGT. Wythoff’s game is linked to non-standard numeration system: P-positions can be determined by writing those in the Fibonacci system. Next, we present the concept of shape-symmetric morphism: instead of iterating a morphism where images of letters are (hyper-)cubes of a fixed length k, one can generalize the procedure to images of various parallelepipedic shape. The shape-symmetry condition introduced twenty years ago by Maes permits to have well-defined fixed point.

In the last lecture, we move to generalized numeration systems: abstract numeration systems (built on a regular language) and link them to morphic (multidimensional) words. In particular, pictures obtained by shape-symmetric morphisms coincide with automatic sequences associated with an abstract numeration system. We conclude these lectures with some work in progress about games with a finite rule-set. This permits us to discuss a bit Presburger definable sets. The general aim of these lectures is to present some interplay between combinatorial game theory (CGT) and combinatorics on (multidimensional) words.

In the first introductory lecture, we present some basic concepts from combinatorial game theory (positions of a game, Nim-sum, Sprague-Grundy function, Wythoff’s game, ...). We also review some concepts from combinatorics on words. We thus introduce the well-known k-automatic sequences and review ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Brlek, Srecko (Auteur de la Conférence) | CIRM (Editeur )

The study of palindromes and their generalizations in a word has gained a lot of interest in the last 20 years, motivated by applications in physics, biology, discrete geometry, to name only a few. Using Sebastien Ferenczi as an example, we illustrate the computation of its palindromic complexity and its relation with the usual factor complexity, via an identity attributed to Brlek and Reutenauer involving also the palindromic defect. Periodic infinite words as well as the family of words with language closed by reversal also satisfy the identity. The identity remains valid when palindromic is replaced by $\sigma$-palindromic, and we also discuss some other patterns.
The study of palindromes and their generalizations in a word has gained a lot of interest in the last 20 years, motivated by applications in physics, biology, discrete geometry, to name only a few. Using Sebastien Ferenczi as an example, we illustrate the computation of its palindromic complexity and its relation with the usual factor complexity, via an identity attributed to Brlek and Reutenauer involving also the palindromic defect. Periodic ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Charlier, Émilie (Auteur de la Conférence) | CIRM (Editeur )

The theorem of Büchi-Bruyère states that a subset of $N^d$ is $b$-recognizable if and only if it is $b$-definable. As a corollary, the first-order theory of $(N,+,V_b)$ is decidable (where $V_b(n)$ is the largest power of the base $b$ dividing $n$). This classical result is a powerful tool in order to show that many properties of $b$-automatic sequences are decidable. The first part of my lecture will be devoted to presenting this result and its applications to $b$-automatic sequences. Then I will move to $b$-regular sequences, which can be viewed as a generalization of $b$-automatic sequences to integer-valued sequences. I will explain bow first-order logic can be used to show that many enumeration problems of $b$-automatic sequences give rise to corresponding $b$-regular sequences. Finally, I will consider more general frameworks than integer bases and (try to) give a state of the art of the research in this domain.
The theorem of Büchi-Bruyère states that a subset of $N^d$ is $b$-recognizable if and only if it is $b$-definable. As a corollary, the first-order theory of $(N,+,V_b)$ is decidable (where $V_b(n)$ is the largest power of the base $b$ dividing $n$). This classical result is a powerful tool in order to show that many properties of $b$-automatic sequences are decidable. The first part of my lecture will be devoted to presenting this result and its ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Aubrun, Nathalie (Auteur de la Conférence) | CIRM (Editeur )

Subshifts of finite type are of high interest from a computational point of view, since they can be described by a finite amount of information - a set of forbidden patterns that defines the subshift - and thus decidability and algorithmic questions can be addressed. Given an SFT $X$, the simplest question one can formulate is the following: does $X$ contain a configuration? This is the so-called domino problem, or emptiness problem: for a given finitely presented group $0$, is there an algorithm that determines if the group $G$ is tilable with a finite set of tiles? In this lecture I will start with a presentation of two different proofs of the undecidability of the domino problem on $Z^2$. Then we will discuss the case of finitely generated groups. Finally, the emptiness problem for general subshifts will be tackled.
Subshifts of finite type are of high interest from a computational point of view, since they can be described by a finite amount of information - a set of forbidden patterns that defines the subshift - and thus decidability and algorithmic questions can be addressed. Given an SFT $X$, the simplest question one can formulate is the following: does $X$ contain a configuration? This is the so-called domino problem, or emptiness problem: for a given ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Saarela, Aleksi (Auteur de la Conférence) | CIRM (Editeur )

Words $u$ and $v$ are defined to be $k$-abelian equivalent if every factor of length at most $k$ appears as many times in $u$ as in $v$. The $k$-abelian complexity function of an infinite word can then be defined so that it maps a number $n$ to the number of $k$-abelian equivalence classes of length-$n$ factors of the word. We consider some variations of extremal behavior of $k$-abelian complexity.

First, we look at minimal and maximal complexity. Studying minimal complexity leads to results on ultimately periodic and Sturmian words, similar to the results by Morse and Hedlund on the usual factor complexity. Maximal complexity is related to counting the number of equivalence classes. As a more complicated topic, we study the question of how much k-abelian complexity can fluctuate between fast growing and slowly growing values. These questions could naturally be asked also in a setting where we restrict our attention to some subclass of all words, like morphic words. Words $u$ and $v$ are defined to be $k$-abelian equivalent if every factor of length at most $k$ appears as many times in $u$ as in $v$. The $k$-abelian complexity function of an infinite word can then be defined so that it maps a number $n$ to the number of $k$-abelian equivalence classes of length-$n$ factors of the word. We consider some variations of extremal behavior of $k$-abelian complexity.

First, we look at minimal and maximal ...

First, we look at minimal and maximal complexity. Studying minimal complexity leads to results on ultimately periodic and Sturmian words, similar to the results by Morse and Hedlund on the usual factor complexity. Maximal complexity is related to counting the number of equivalence classes. As a more complicated topic, we study the question of how much k-abelian complexity can fluctuate between fast growing and slowly growing values. These questions could naturally be asked also in a setting where we restrict our attention to some subclass of all words, like morphic words. Words $u$ and $v$ are defined to be $k$-abelian equivalent if every factor of length at most $k$ appears as many times in $u$ as in $v$. The $k$-abelian complexity function of an infinite word can then be defined so that it maps a number $n$ to the number of $k$-abelian equivalence classes of length-$n$ factors of the word. We consider some variations of extremal behavior of $k$-abelian complexity.

First, we look at minimal and maximal ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Karhumäki, Juhani (Auteur de la Conférence) | CIRM (Editeur )

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Ciobanu, Laura (Auteur de la Conférence) | CIRM (Editeur )

Rivin conjectured that the conjugacy growth series of a hyperbolic group is rational if and only if the group is virtually cyclic. In this talk I will present the proof (joint with Hermiller, Holt and Rees) that the conjugacy growth series of a virtually cyclic group is rational, and then also confirm the other direction of the conjecture, by showing that the conjugacy growth series of a non-elementary hyperbolic group is transcendental (joint with Antolín). The result for non-elementary hyperbolic groups can be used to prove a formal language version of Rivin's conjecture for any finitely generated acylindrically hyperbolic group G, namely that no set of minimal length conjugacy representatives of G can be regular.
Rivin conjectured that the conjugacy growth series of a hyperbolic group is rational if and only if the group is virtually cyclic. In this talk I will present the proof (joint with Hermiller, Holt and Rees) that the conjugacy growth series of a virtually cyclic group is rational, and then also confirm the other direction of the conjecture, by showing that the conjugacy growth series of a non-elementary hyperbolic group is transcendental (joint ...

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Genet, Thomas (Auteur de la Conférence) | CIRM (Editeur )

Tree Automata Completion is an algorithm computing, or approximating, terms reachable by a term rewriting system. For many classes of term rewriting systems whose set of reachable terms is known to be regular, this algorithm is exact. Besides, the same algorithm can handle **any** left-linear term rewriting system, in an approximated way, using equational 2 abstractions. Thanks to those two properties, we will see that regular languages and tree automata completion provide a promising alternative for automatic static analysis of functional programs.
Tree Automata Completion is an algorithm computing, or approximating, terms reachable by a term rewriting system. For many classes of term rewriting systems whose set of reachable terms is known to be regular, this algorithm is exact. Besides, the same algorithm can handle **any** left-linear term rewriting system, in an approximated way, using equational 2 abstractions. Thanks to those two properties, we will see that regular languages and tree ...

Z

- © Powered by Kentika
- |
- 2017
- |
- Mentions légales