Rationality, irrationality, and Wilf equivalence in generalized factor order

Résumé : Soit $P$ un ensemble partiellement ordonné. Nous considérons le monoïde libre $P^{\ast}$ de tous les mots utilisant $P$ comme alphabet. Si $w,w' \in P^{\ast}$, on dit que $w'$ est un facteur de $w$ s'il y a des mots $u,v$ avec $w=uw'v$. Nous définissons l'ordre facteur généralisé sur $P^{\ast}$ par: $u \leq w$ s'il y a un facteur $w'$ de $w$ ayant la même longueur que $u$ tel que $u \leq w'$, où la comparaison de $u$ avec $w'$ est faite lettre par lettre utilisant l'ordre en $P$. On obtient l'ordre facteur usuel si on insiste que $u=w'$ ou, ce qui est la même chose, en prenant $P$ comme antichaîne. Pour n'importe quel $u \in P^{\ast}$, nous démontrons que le langage $\mathcal{F}(u)=\{w : w \geq u\}$ est accepté par un automaton avec un nombre fini d'états. Si $P$ est fini, ça implique que la fonction génératrice $F(u)=\sum_{w \geq u} w$ est rationnelle. Björner et Sagan ont démontré le théorème analogue pour l'ordre où, en la définition au-dessus, $w'$ est un sous-mot de $w$. Nous considérons aussi le cas $P=\mathbb{P}$, les entiers positifs avec l'ordre usuel, donc $P^{\ast}$ est l'ensemble des compositions. En ce cas on obtient une fonction génératrice pondéré $F(u;t,x)$ en remplaçant $tx^n$ chaque fois on trouve $n \in \mathbb{P}$ en $F(u)$. Nous démontrons que cette fonction génératrice est aussi rationnelle en utilisant la Méthode Matrice de Tranfert. On dit que let mots $u,v$ sont Wilf-équivalents si $F(u;t,x)=F(v;t,x)$. Nous pouvons démontré quelques équivalences dans une manière combinatoire. Björner a trouvé une formule récursive pour la fonction Möbius de l'ordre facteur usuel sur $P^{\ast}$. Cette formule implique qu'on a toujours $\mu (u,w)=0, \pm 1$. En utilisant le Lemme de Pompage, nous démontrons que la fonction génératrice $M(u)= \sum_{w \geq u} | \mu (u,w) | w$ peut être irrationnelle.
Type de document :
Communication dans un congrès
Krattenthaler, Christian and Strehl, Volker and Kauers, Manuel. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), pp.515-526, 2009, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185380
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 11:06:43
Dernière modification le : mercredi 18 octobre 2017 - 14:38:05
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:06:30

Fichier

dmAK0143.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185380, version 1

Collections

Citation

Sergey Kitaev, Jeffrey Liese, Jeffrey Remmel, Bruce Sagan. Rationality, irrationality, and Wilf equivalence in generalized factor order. Krattenthaler, Christian and Strehl, Volker and Kauers, Manuel. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), pp.515-526, 2009, DMTCS Proceedings. 〈hal-01185380〉

Partager

Métriques

Consultations de la notice

68

Téléchargements de fichiers

172