Existe uma linguagem de árvore comum em que a altura média de uma árvore de tamanho

Definimos uma linguagem de árvore regular como no livro TATA : É o conjunto de árvores aceito por um autômato finito de árvore não determinístico (Capítulo 1) ou, equivalentemente, o conjunto de árvores geradas por uma gramática regular de árvores (Capítulo 2). Ambos os formalismos têm grandes semelhanças com os conhecidos análogos de cordas.

Existe uma linguagem de árvore comum em que a altura média de uma árvore de tamanho não seja nem ? $n$ $\Theta(n)$ $\Theta(\sqrt{n})$

Obviamente, existem linguagens de árvore de modo que a altura de uma árvore é linear em seu tamanho; e no livro Analytic Combinatorics , é mostrado, por exemplo, que árvores binárias de tamanho têm altura média . Se eu entendi a Proposição VII.16 (p.537) do livro mencionado corretamente, existe um amplo subconjunto de linguagens de árvore regulares que têm altura média de , ou seja, aquelas em que o idioma da árvore também é uma variedade simples de árvores que preenchem algumas condições extras. $n$ $2\sqrt{ \pi n}$ $\Theta(\sqrt{n})$

Então, eu queria saber se existe uma linguagem de árvore regular mostrando uma altura média diferente ou se existe uma dicotomia verdadeira para linguagens de árvore regulares.

Nota: Esta pergunta já foi feita antes em Ciência da Computação , mas não foi respondida por mais de três meses. Gostaria de republicá-lo aqui, porque a pergunta é muito antiga para migrar e porque ainda há interesse na questão. Aqui está um link para a postagem original.

co.combinatorics fl.formal-languages tree regular-language john_leo
fonte

A única árvore com profundidade constante é uma resposta óbvia: o (\ sqrt {n}), mas não . Eu acredito que você provavelmente quis dizer alguma outra pergunta? Substitua por talvez?

Ω (\sqrt{n})

$\Omega(\sqrt{n})$

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

O (\sqrt{n})

$O(\sqrt{n})$

Joseph Stack

Sim e não. Eu acho que uma linguagem comum de árvore com profundidade média (digamos) também seria muito interessante. Mas você tem razão em que devemos excluir casos degenerados. Talvez devêssemos exigir que a linguagem da árvore contenha infinitos elementos?

O (n^{1 / 3})

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

john_leo

Que tipo de árvores você tem em mente? Árvores classificadas, árvores ordenadas por irmãos não ordenadas, árvores não ordenadas não ordenadas; e, a propósito, que tipo de autômato de árvore você quer dizer, de baixo para cima ou de cima para baixo?

@JosephStack como a altura de uma árvore regular pode ser infinita? Uma árvore com

nós não pode ter uma altura maior que

n

$n$

n

$n$

john_leo

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\}$

Acredito que a resposta é como você sugere que não são possíveis outros assintóticos além de , e . Uma rota promissora para provar isso pode ser a aplicação das técnicas do artigo que deriva os assintóticos às árvores de execução da linguagem comum. Observe que uma árvore é aceita se existir uma árvore de execução, portanto, é possível derivar primeiro (usando loc.cit. ) A altura média de uma árvore de execução gerada aleatoriamente e levá-la a partir daí, ou seja, mostrar que projetar os estados não mude a altura média. $\Theta(1)$ $\Theta(\sqrt{n})$ $\Theta(n)$ $\Theta(\sqrt{n})$

Martin Hofmann
fonte

Acho que isso é um comentário e não uma resposta, pois está longe de ser claro se essa tentativa dá certo.

Danny

Existe uma linguagem de árvore comum em que a altura média de uma árvore de tamanho

Respostas: