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

The art of computer programming.
Vol.4, fascicle 4: generating all trees. History of combinatorial generation
Knuth, Donald E. | Addison Wesley 2006

Ouvrage

y

- vi; 120 p.
ISBN 978-0-321-33570-8

Localisation : Ouvrage RdC (KNUT)

génération d'objets combinatoires # algorithme combinatoire # fonction Booléenne # partition d'un entier # partition d'un ensemble # diagramme de décision binaire

68R05 ; 68-02 ; 05-02 ; 05A05 ; 05A17 ; 05A18 ; 05C05 ; 05C30 ; 68Q25 ; 68R15 ; 68W05

... Lire [+]

Filtrer

Type
Domaine
Codes MSC

Ressources Electroniques

Books & Print journals

Recherche avancée


0
Z
p>

Signaler une erreur

1

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

Dimension groups and recurrence for tree subshifts Berthé, Valérie | CIRM H

Multi angle

y

Research talks

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.

Avoiding $k$-abelian powers in words Rao, Michaël | CIRM H

Multi angle

y

Research talks

68R15

... Lire [+]

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

$k$-abelian singletons and Gray codes for Necklaces Whiteland, Markus | CIRM H

Multi angle

y

Research talks

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

$k$-abelian equivalence: an equivalence relation in between the equality and the abelian equivalence Karhumäki, Juhani | CIRM H

Multi angle

y

Research talks

68Q45 ; 68R15 ; 05A05

... Lire [+]

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

$k$-abelian complexity and fluctuation Saarela, Aleksi | CIRM H

Multi angle

y

Research talks

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 [+]