Czy istnieje zwykły język drzewa, w którym średnia wysokość drzewa o rozmiarze nie jest ani ani ?

Definiujemy zwykły język drzewa, tak jak w książce TATA : Jest to zestaw drzew akceptowany przez niedeterministyczny automat skończonego drzewa (rozdział 1) lub, równoważnie, zbiór drzew wygenerowany przez zwykłą gramatykę drzewa (rozdział 2). Oba formalizmy są bardzo podobne do znanych analogów strunowych.

Czy istnieje zwykły język drzewa, w którym średnia wysokość drzewa o rozmiarze nie jest ani ani ? $n$ $\Theta(n)$ $\Theta(\sqrt{n})$

Oczywiście istnieją języki drzewiaste, w których wysokość drzewa ma liniowy rozmiar; aw książce Analytic Combinatorics pokazano np., że drzewa binarne o wielkości mają średnią wysokość . Jeśli dobrze rozumiem Twierdzenie VII.16 (str. 537) wspomnianej książki, istnieje szeroki podzbiór zwykłych języków drzewa, które mają średnią wysokość , a mianowicie te, w których język drzewa to także prosta odmiana drzew spełniająca dodatkowe warunki. $n$ $2\sqrt{ \pi n}$ $\Theta(\sqrt{n})$

Zastanawiałem się więc, czy istnieje zwykły język drzewa pokazujący inną średnią wysokość, czy też istnieje prawdziwa dychotomia dla zwykłych języków drzewa.

Uwaga: To pytanie zadawano wcześniej w dziedzinie informatyki , ale nie było odpowiedzi od ponad trzech miesięcy. Chciałbym go tutaj ponownie opublikować, ponieważ pytanie jest za stare, aby je migrować, i ponieważ wciąż jest zainteresowanie tym pytaniem. Oto link do oryginalnego postu.

— john_leo
źródło

Pojedyncze drzewo o stałej głębokości jest oczywistą odpowiedzią: o (\ sqrt {n}), ale nie . Wierzę, że prawdopodobnie miałeś na myśli jakieś inne pytanie? Wymienić o może być?

Ω (\sqrt{n})

$\Omega(\sqrt{n})$

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

O (\sqrt{n})

$O(\sqrt{n})$

— Joseph Stack

Tak i nie. Myślę, że zwykły język drzewa o średniej głębokości (powiedzmy) również byłby bardzo interesujący. Ale masz rację, że powinniśmy wykluczyć takie zdegenerowane przypadki. Może powinniśmy wymagać, aby język drzewa zawierał nieskończenie wiele elementów?

O (n^{1 / 3})

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

— john_leo

Jakie drzewa masz na myśli? Drzewa rankingowe, nierankingowane drzewa rodzeństwa, nierankingowane drzewa nieuporządkowane; a przy okazji, jakie automaty drzewne masz na myśli, oddolne czy odgórne?

— fh

@JosephStack, jak wysokość zwykłego drzewa może być nieskończona? Drzewo z węzłami nie może mieć wysokości większej niż .

n

$n$

n

$n$

— john_leo

@ Rafael: Jeśli nie rozważysz , nie jest dla mnie jasne, jakie byłoby pytanie. Odpowiedź na "istnieje nieskończona język regularny drzewo takie, że średnia wysokość to funkcja ze i " jest oczywiście tak: upewnij się, że dla nieparzystych masz i parzyste . PS każda funkcja, jaką mogę sobie wyobrazić, należy do dla niektórych , więc nie jest to poprawna poprawka :)

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

Uważam, że odpowiedź jest taka, jak sugerujesz, że nie są możliwe żadne inne asymptotyki niż , i . Obiecującą drogą do udowodnienia tego może być zastosowanie technik z artykułu, który wyprowadza asymptotykę do drzewek uruchamianych w zwykłym języku. Zauważ, że drzewo jest akceptowane, jeśli istnieje drzewo uruchomieniowe, dlatego najpierw powinno być możliwe ustalenie (za pomocą loc.cit. ) Średniej wysokości losowo wygenerowanego drzewa uruchomieniowego i pobranie go stamtąd, tj. Pokazanie, że rzutowanie stanów powoduje nie zmieniać średniej wysokości. $\Theta(1)$ $\Theta(\sqrt{n})$ $\Theta(n)$ $\Theta(\sqrt{n})$

— Martin Hofmann
źródło

Myślę, że to komentarz, a nie odpowiedź, ponieważ nie jest jasne, czy ta próba się powiedzie.

— Danny