Gibt es eine reguläre Baumsprache, in der die durchschnittliche Höhe eines Baumes der Größe weder noch ?

Wir definieren eine reguläre Baumsprache wie im Buch TATA : Es ist die Menge von Bäumen, die von einem nicht deterministischen endlichen Baumautomaten akzeptiert wird (Kapitel 1), oder äquivalent die Menge von Bäumen, die von einer regulären Baumgrammatik erzeugt wird (Kapitel 2). Beide Formalismen haben große Ähnlichkeiten mit den bekannten String-Analoga.

Gibt es eine reguläre Baumsprache, in der die durchschnittliche Höhe eines Baumes der Größe weder noch ? $n$ $\Theta(n)$ $\Theta(\sqrt{n})$

Offensichtlich gibt es Baumsprachen, bei denen die Höhe eines Baumes in seiner Größe linear ist. und im Buch Analytic Combinatorics wird beispielsweise gezeigt, dass Binärbäume der Größe eine durchschnittliche Höhe von . Wenn ich Proposition VII.16 (S.537) des erwähnten Buches richtig verstehe, gibt es eine breite Untermenge von regulären Baumsprachen, die eine durchschnittliche Höhe von , nämlich diejenigen, in denen die Baumsprache vorkommt ist auch eine einfache Baumsorte, die einige zusätzliche Bedingungen erfüllt. $n$ $2\sqrt{ \pi n}$ $\Theta(\sqrt{n})$

Ich habe mich also gefragt, ob es eine reguläre Baumsprache gibt, die eine andere Durchschnittsgröße aufweist, oder ob es eine echte Dichotomie für reguläre Baumsprachen gibt.

Hinweis: Diese Frage wurde bereits zu Informatik gestellt , sie wurde jedoch seit mehr als drei Monaten nicht beantwortet. Ich möchte es hier erneut veröffentlichen, weil die Frage zu alt für eine Migration ist und weil immer noch Interesse an der Frage besteht. Hier ist ein Link zum Originalbeitrag.

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

Der einzelne Baum mit konstanter Tiefe ist eine offensichtliche Antwort: o (\ sqrt {n}), aber nicht . Ich glaube, Sie meinten wahrscheinlich eine andere Frage? Vielleicht durch ersetzen?

Ω (\sqrt{n})

$\Omega(\sqrt{n})$

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

O (\sqrt{n})

$O(\sqrt{n})$

Joseph Stack

Ja und nein. Ich denke, eine reguläre Baumsprache mit durchschnittlicher Tiefe (etwa) wäre auch sehr interessant. Aber Sie haben Recht, wir sollten solche entarteten Fälle ausschließen. Vielleicht sollten wir verlangen, dass die Baumsprache unendlich viele Elemente enthält?

O (n^{1 / 3})

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

john_leo

Welche Art von Bäumen haben Sie im Sinn? Gewertete Bäume, nicht gewertete Bäume, nicht gewertete, nicht gewertete Bäume; und welche Art von Baumautomaten meinen Sie übrigens, von unten nach oben oder von oben nach unten?

@JosephStack wie kann die Höhe eines regulären Baumes unendlich sein? Ein Baum mit Knoten kann nicht höher als .

n

$n$

n

$n$

john_leo

@Raphael: Wenn Sie nicht berücksichtigen , ist mir nicht klar, was die Frage wäre. Die Antwort auf "Gibt es eine unendliche reguläre Baumsprache, so dass die mittlere Höhe eine Funktion mit und " offensichtlich ja: Stellen Sie sicher , dass für ungerade Sie haben und auch solche . PS jede Funktion, die ich mir vorstellen kann, gehört zu für einige , es ist also keine korrekte Lösung :)

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

Ich glaube, die Antwort lautet, Sie schlagen vor, dass keine anderen Asymptoten als , und möglich sind. Ein vielversprechender Weg, um dies zu beweisen, könnte darin bestehen, die Techniken aus dem Papier, das die Asymptotika ableitet, auf die der regulären Sprache anzuwenden . Beachten Sie, dass ein Baum akzeptiert wird, wenn es einen Laufbaum gibt. Daher sollte es möglich sein, zuerst (mit loc.cit. ) Die durchschnittliche Höhe eines zufällig generierten Laufbaums abzuleiten und von dort zu übernehmen, dh zu zeigen, dass das Wegprojektieren der Zustände funktioniert die durchschnittliche Höhe nicht ändern. $\Theta(1)$ $\Theta(\sqrt{n})$ $\Theta(n)$ $\Theta(\sqrt{n})$

Martin Hofmann
quelle

Ich denke, dies ist ein Kommentar und keine Antwort, da es alles andere als klar ist, ob dieser Versuch funktioniert.

Danny

Gibt es eine reguläre Baumsprache, in der die durchschnittliche Höhe eines Baumes der Größe weder noch ?

Antworten: