m

F Nous contacter

0

Documents  68R15 | enregistrements trouvés : 48

O

-A +A

P Q

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

Research schools;Algebra;Combinatorics;Computer Science;Number Theory

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.

11B85 ; 68Q45 ; 68R15

... Lire [+]

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

Research talks;Combinatorics;Computer Science;Dynamical Systems and Ordinary Differential Equations

We will consider (sub)shifts with complexity such that the difference from $n$ to $n+1$ is constant for all large $n$. The shifts that arise naturally from interval exchange transformations belong to this class. An interval exchange transformation on d intervals has at most $d/2$ ergodic probability measures. We look to establish the correct bound for shifts with constant complexity growth. To this end, we give our current bound and discuss further improvements when more assumptions are allowed. This is ongoing work with Michael Damron. We will consider (sub)shifts with complexity such that the difference from $n$ to $n+1$ is constant for all large $n$. The shifts that arise naturally from interval exchange transformations belong to this class. An interval exchange transformation on d intervals has at most $d/2$ ergodic probability measures. We look to establish the correct bound for shifts with constant complexity growth. To this end, we give our current bound and discuss ...

37B10 ; 37A25 ; 68R15

... Lire [+]

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

- vi; 139 p.
ISBN 978-2-271-12611-5

Localisation : Colloque 1er étage (MARS);Ouvrage RdC (INFO)

informatique mathématique # transduction # mot sturmien # maillage 3D # poset, polynôme, polytope (popopo) # algorithmique distribuée # système d'agents mobiles

68Q45 ; 68R15 ; 68P20 ; 94A08 ; 52A25 ; 06A07

... Lire [+]

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

- xx; 419 p.
ISBN 978-0-8176-4887-9

Applied and numerical harmonic analysis

Localisation : Colloque 1er étage (MONA)

analyse harmonique # système dynamique dérivable # analyse fonctionnelle # equation différentielle aux dérivées partielles # géompétrie # distribution # probabilités

28Axx ; 37Dxx ; 35Jxx ; 43AXX ; 46Exx ; 60Gxx ; 68R15 ; 28C10 ; 42C40 ; 47A10 ; 28-06 ; 28A80 ; 37D45 ; 00B25

... Lire [+]

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

- 421 p.
ISBN 978-3-540-73207-5

Lecture notes in computer science , 4588

Localisation : Collection 1er étage

langage formel # grammaire # analyse numérique # automate # arbre # graphe # combinatoires # propriété algébrique des mots # dynamique formelle # décision # complexité # cryptographie # calcul quantique

68-06 ; 68Q45 ; 00B25 ; 68R15

... Lire [+]

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

- 350 p.
ISBN 978-3-540-56402-7

Lecture notes in computer science , 0657

Localisation : Collection 1er étage

algorithme distribué # algorithme parallèle # combinatoire # concept de graphe théorique # décomposition de graphes # grammaire de graphe # géométrie

05Cxx ; 05Dxx ; 68R10 ; 68R15 ; 68S05

... Lire [+]

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

- 320 p.
ISBN 978-3-540-54891-1

Lecture notes in computer science , 0553

Localisation : Collection 1er étage

algorithme # géométrie # géométrie combinatoire

68Q20 ; 68R15

... Lire [+]

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

- 208 p.
ISBN 978-3-540-17184-3

Lecture notes in computer science , 0242

Localisation : Collection 1er étage

calcul lambda # informatique théorique # langage # langage de programmation # langage de programmation combinatoire # langage de programmation fonctionnel # logique # programmation # programmation automatique # sémantique # système # technique de programmation

68N05 ; 68N15 ; 68Q40 ; 68R15

... Lire [+]

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

Research talks;Computer Science;Dynamical Systems and Ordinary Differential Equations

Dimension groups are invariants of orbital equivalence. We show in this lecture how to compute the dimension group of tree subshifts. Tree subshifts are defined in terms of extension graphs that describe the left and right extensions of factors of their languages: the extension graphs are trees. This class of subshifts includes classical families such as Sturmian, Arnoux-Rauzy subshifts, or else, codings of interval exchanges. We rely on return word properties for tree subshifts: every finite word in the language of a tree word admits exactly d return words, where d is the cardinality of the alphabet.
This is joint work with P. Cecchi, F. Dolce, F. Durand, J. Leroy, D. Perrin, S. Petite.
Dimension groups are invariants of orbital equivalence. We show in this lecture how to compute the dimension group of tree subshifts. Tree subshifts are defined in terms of extension graphs that describe the left and right extensions of factors of their languages: the extension graphs are trees. This class of subshifts includes classical families such as Sturmian, Arnoux-Rauzy subshifts, or else, codings of interval exchanges. We rely on return ...

37A20 ; 37B10 ; 68R15 ; 68Q45

... Lire [+]

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

Research talks;Computer Science;Dynamical Systems and Ordinary Differential Equations;Number Theory

In the way of Arnoux-Ito, we give a general geometric criterion for a subshift to be measurably conjugated to a domain exchange and to a translation on a torus. For a subshift coming from an unit Pisot irreducible substitution, we will see that it becomes a simple topological criterion. More precisely, we define a topology on $\mathbb{Z}^d$ for which the subshift has pure discrete spectrum if and only if there exists a domain of the domain exchange on the discrete line that has non-empty interior. We will see how we can compute exactly such interior using regular languages. This gives a way to decide the Pisot conjecture for any example of unit Pisot irreducible substitution.
Joint work with Shigeki Akiyama.
In the way of Arnoux-Ito, we give a general geometric criterion for a subshift to be measurably conjugated to a domain exchange and to a translation on a torus. For a subshift coming from an unit Pisot irreducible substitution, we will see that it becomes a simple topological criterion. More precisely, we define a topology on $\mathbb{Z}^d$ for which the subshift has pure discrete spectrum if and only if there exists a domain of the domain ...

37B10 ; 28A80 ; 11A63 ; 68R15

... Lire [+]

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

Research schools;Combinatorics;Computer Science;Number Theory

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

91A46 ; 68R15 ; 68Q45

... Lire [+]

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

Research schools;Analysis and its Applications;Combinatorics;Dynamical Systems and Ordinary Differential Equations;Number Theory

28A80 ; 37A30 ; 37B10 ; 37E05 ; 11B85 ; 11B83 ; 68R15

... Lire [+]

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

Research schools;Combinatorics;Computer Science;Dynamical Systems and Ordinary Differential Equations

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

68Q45 ; 68R15

... Lire [+]

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

Research schools;Computer Science;Logic and Foundations;Number Theory

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

68R15 ; 11B85 ; 68Q45 ; 03B25

... Lire [+]

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

Research talks;Computer Science;Logic and Foundations

Recall that normality is a elementary form of randomness: an infinite word is normal to a given alphabet if all blocks of symbols of the same length occur in the word with the same asymptotic frequency. We consider a notion of independence on pairs of infinite words formalising that two words are independent if no one helps to compress the other using one-to-one finite transducers with two inputs. As expected, the set of independent pairs has Lebesgue measure 1. We prove that not only the join of two normal words is normal, but, more generally, the shuffling with a finite transducer of two normal independent words is also a normal word. The converse of this theorem fails: we construct a normal word as the join of two normal words that are not independent. We construct a word x such that the symbol at position n is equal to the symbol at position 2n. Thus, x is the join of x itself and the subsequence of odd positions of x. We also show that selection by finite automata acting on pairs of independent words preserves normality. This is a counterpart version of Agafonov's theorem for finite automata with two input tapes.
This is joint work with Olivier Carton (Universitéé Paris Diderot) and Pablo Ariel Heiber (Universidad de Buenos Aires).
Recall that normality is a elementary form of randomness: an infinite word is normal to a given alphabet if all blocks of symbols of the same length occur in the word with the same asymptotic frequency. We consider a notion of independence on pairs of infinite words formalising that two words are independent if no one helps to compress the other using one-to-one finite transducers with two inputs. As expected, the set of independent pairs has ...

68R15 ; 11K16 ; 03D32

... Lire [+]

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

Research talks;Combinatorics;Computer Science

$k$-abelian singletons in connection with Gray codes for Necklaces. This work is based on [1]. We are interested in the equivalence classes induced by $k$-abelian equivalence, especially in the number of the classes containing only one element, $k$-abelian singletons. By characterizing $k$-abelian equivalence with $k$-switchings, a sort of rewriting operation, we are able to obtain a structural representation of $k$-abelian singletons. Analyzing this structural result leads, through rather technical considerations, to questions of certain properties of sets of vertex-disjoint cycles in the de Bruijn graph $dB_\Sigma(k-1)$ of order $k-1$. Some problems turn out to be equivalent to old open problems such as Gray codes for necklaces (or conjugacy classes). We shall formulate the problem in the following.
Let $\mathcal{C} = \lbrace V_1, . . . , V_n\rbrace$ be a cycle decomposition of $dB_\Sigma(n)$, that is, a partition of the vertex set $\Sigma^n$ into sets, each inducing a cycle or a loop in $dB_\Sigma(n)$. Let us then define the quotient graph $dB_\Sigma/\mathcal{C}$ as follows. The set of points are the sets in $\mathcal{C}$. For distinct sets $X, Y \in \mathcal{C}$, we have and edge from $X$ to $Y$ if and only if there exists $x{\in}X,y{\in}Y$ such that $(x,y){\in}dB_\Sigma(n)$. An old result shows that the size of a cycle decomposition of $dB_\Sigma(n)$ is at most the number of necklaces of length $n$ over $\Sigma$ (see [2]). We call a cycle decomposition maximal, if its size is maximal. In particular, the cycle decomposition given by necklaces is maximal.
Conjecture 1. For any $\Sigma$ and $n{\in}\mathbb{N}$, there exist a maximal cycle decomposition $\mathcal{C}$ of $dB_\Sigma(n)$ such that $dB_\Sigma(n)/\mathcal{C}$ contains a hamiltonian path.
A natural candidate to study here is the cycle decomposition given by necklaces. This has been studied in the literature in the connection of Gray codes for necklaces. Concerning this, there is an open problem since $1997$ $[3]$ : Let $\Sigma = \lbrace0, 1\rbrace$, $n$ odd, and $\mathcal{C}$ be the cycle decomposition given by necklaces of length $n$ over $\lbrace0,1\rbrace$. Does $dB(n)/\mathcal{C}$ contain a hamiltonian path ?
The answer to the above has been verified to be ”yes” for $n \le 15$ $([1]$). The case of $n \ge 4$ and $n$ even, the graph is bipartite with one partition larger than the other. On the other hand, we can find other maximal cycle decompositions of $dB_\Sigma(4)$, $dB_\Sigma(6)$, and $dB_\Sigma(8)$ for the binary alphabet which all admit hamiltonian quotient graphs.
We concluded in $[1]$ that Conjecture $1$ is equivalent to the following $\Theta$-estimation of the number of $k$-abelian singletons of length $n$.
Conjecture 2. The number of $k$-abelian singletons of length $n$ over alphabet $\Sigma$ is of order $\Theta(n^{N_{\Sigma}(k-1)-1})$, where $N_\Sigma(l)$ is the number of necklaces of length $l$ over $\Sigma$.
$k$-abelian singletons in connection with Gray codes for Necklaces. This work is based on [1]. We are interested in the equivalence classes induced by $k$-abelian equivalence, especially in the number of the classes containing only one element, $k$-abelian singletons. By characterizing $k$-abelian equivalence with $k$-switchings, a sort of rewriting operation, we are able to obtain a structural representation of $k$-abelian singletons. Analyzing ...

68R15 ; 94B25 ; 05Axx

... Lire [+]

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

Research talks;Combinatorics;Computer Science

68R15

... Lire [+]

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

Research talks;Combinatorics;Computer Science

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

68Q45 ; 68R15 ; 05A05

... Lire [+]

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

Research talks;Combinatorics;Computer Science

05A05 ; 68R15

... Lire [+]

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

Research talks;Combinatorics;Computer Science

68Q45 ; 68R15 ; 05A05

... Lire [+]

Z