Existe-t-il un langage d'arbre régulier dans lequel la hauteur moyenne d'un arbre de taille

Nous définissons un langage d'arbre régulier comme dans le livre TATA : c'est l'ensemble d'arbres accepté par un automate d'arbre fini non déterministe (chapitre 1) ou, de manière équivalente, l'ensemble d'arbres généré par une grammaire d'arbre régulière (chapitre 2). Les deux formalismes ont des ressemblances étroites avec les analogues de cordes bien connus.

Existe-t-il un langage d'arbre régulier dans lequel la hauteur moyenne d'un arbre de taille $n$ n'est ni $\Theta(n)$ ni $\Theta(\sqrt{n})$ ?

Évidemment, il existe des langages d'arbres tels que la hauteur d'un arbre est linéaire dans sa taille; et dans le livre Analytic Combinatorics, il est montré par exemple que les arbres binaires de taille $n$ ont une hauteur moyenne $2\sqrt{ \pi n}$ . Si je comprends bien la proposition VII.16 (p.537) du livre mentionné, alors il existe un large sous-ensemble de langages d'arbres réguliers qui ont une hauteur moyenne de $\Theta(\sqrt{n})$ , à savoir ceux dans lesquels la langue des arbres est également unesimple variété d'arbresremplissant certaines conditions supplémentaires.

Je me demandais donc s'il y avait une langue d'arbre régulière montrant une hauteur moyenne différente ou s'il y avait une vraie dichotomie pour les langues d'arbre régulières.

Remarque: Cette question a été posée auparavant en informatique , mais elle est restée sans réponse pendant plus de trois mois. Je voudrais le republier ici parce que la question est trop ancienne pour migrer et parce qu'il y a toujours un intérêt pour la question. Voici un lien vers le message d'origine.

co.combinatorics fl.formal-languages tree regular-language john_leo
la source

L'arbre unique à profondeur constante est une réponse évidente: o (\ sqrt {n}) mais pas

. Je crois que vous vouliez probablement une autre question? Remplacer

Ω (\sqrt{n})

$\Omega(\sqrt{n})$

avec

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

peut-être?

O (\sqrt{n})

$O(\sqrt{n})$

Joseph Stack

Oui et non. Je pense qu'un langage d'arbres régulier avec la profondeur moyenne

( par exemple) serait également très intéressant. Mais vous avez raison en ce que nous devrions exclure ces cas dégénérés. Peut-être devrions-nous exiger que le langage arborescent contienne une infinité d'éléments?

O (n^{1 / 3})

$O(n^{1/3})$

john_leo

Quel genre d'arbres avez-vous en tête? Arbres classés, arbres classés par les frères non classés, arbres non classés non classés; et, à propos, quel genre d'automates d'arbre voulez-vous dire, de bas en haut ou de haut en bas?

@JosephStack comment la hauteur d'un arbre régulier peut-elle être infinie? Un arbre à

nœuds ne peut pas avoir une hauteur supérieure à

n

$n$

n

$n$

john_leo

@Raphael: Si vous ne considérez pas

, il n'est pas clair pour moi quelle serait la question. La réponse à "existe-t-il un langage d'arbre régulier infini tel que la hauteur moyenne est une fonction

avec et " est évidemment oui: assurez-vous que pour impair, vous avez et même . PS chaque fonction que je peux imaginer appartient à pour certains , donc ce n'est pas une solution correcte :)

lim sup

$\lim\sup$

f

$f$

f (n) \notin Θ (\sqrt{n})

$f(n)\notin \Theta(\sqrt{n})$

f (n) \notin Θ (n)

$f(n)\notin\Theta(n)$

n

$n$

Θ (n)

$\Theta(n)$

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

Θ (g)

$\Theta(g)$

g \notin {\sqrt{n}, n}

$g\notin\{\sqrt{n},n\}$

Joseph Stack

Je pense que la réponse est que vous suggérez qu'aucune autre asymptotique que , et n'est possible. Une voie prometteuse pour le prouver pourrait être d'appliquer les techniques de l'article qui dérivent l' asymptotique aux arbres d'exécution du langage régulier. Notez qu'un arbre est accepté s'il existe un arbre d'exécution, il devrait donc être possible de dériver d'abord (en utilisant loc.cit. ) La hauteur moyenne d'un arbre d'exécution généré de manière aléatoire et de le prendre à partir de là, c'est-à-dire montrer que projeter les états ne pas changer la hauteur moyenne. $\Theta(1)$ $\Theta(\sqrt{n})$ $\Theta(n)$ $\Theta(\sqrt{n})$

Martin Hofmann
la source

Je pense que c'est un commentaire et non une réponse car il est loin d'être clair si cette tentative fonctionne.

Danny

Existe-t-il un langage d'arbre régulier dans lequel la hauteur moyenne d'un arbre de taille

Réponses: