Affordable Access

Une application élémentaire des grammaires génératives au dénombrement d'une certaine classe d'arbres

Authors
Publication Date
Disciplines
  • Biology
  • Mathematics

Abstract

Une application élémentaire des grammaires génératives au dénombrement d'une certaine classe d'arbres MATHÉMATIQUES ET SCIENCES HUMAINES M. EYTAN Une application élémentaire des grammaires génératives au dénombrement d’une certaine classe d’arbres Mathématiques et sciences humaines, tome 21 (1968), p. 11-16. <http://www.numdam.org/item?id=MSH_1968__21__11_0> © Centre d’analyse et de mathématiques sociales de l’EHESS, 1968, tous droits réservés. L’accès aux archives de la revue « Mathématiques et sciences humaines » (http://msh.revues. org/) implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal. php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ 11 UNE APPLICATION ÉLÉMENTAIRE DES GRAMMAIRES GÉNÉRATIVES AU DÉNOMBREMENT D’UNE CERTAINE CLASSE D’ARBRES par M. EYTAN 1 1. - LE PROBLÈME. Il s’agit de trouver le nombre A (p ; n) d’arbres biordonnés p - aires à pn + 1 n0153uds, i.e. à n noeuds non-terminaux. 2. - DÉFINITIONS. Par arbre biordon.né 2 (appelé désormais arbre tout court) nous entendons le triplet (A, £, $) d’un~ ensemble fini A, muni des deux ordres £ et $ (dits resp. « hiérarchique» et « séquentiel») vérifiant les axiomes suivants : 1) le £-prédécesseur immédiat de tout élément de A, s’il existe, est unique ; 2) $ est un ordre total sur A ; 3) pour tout couple (x, y) d’éléments de A, x£y entraîne x$y ; 4) quels que soient les éléments x, y, x’, y’ de A, x$y et x£x’ et y£y’ entraînent x’$y’ ; 5) il existe un élément unique de A sans £-prédécesseur. L’élément déterminé par l’axiome 5) sera dit racine de l’arbre A (comme d’habitude, on fait l’abus de langage assimilant le triplet (A, £, $) à l’ensemble sous-jacent A). Un n0153ud terminal de A sera un élément sa

There are no comments yet on this publication. Be the first to share your thoughts.