Существует ли обычный древовидный язык, в котором средняя высота дерева размера

Мы определяем язык регулярного дерева, как в книге TATA : это множество деревьев, принятых недетерминированным автоматом конечного дерева (глава 1) или, что эквивалентно, множество деревьев, порожденных грамматикой регулярного дерева (глава 2). Оба формализма очень похожи на хорошо известные аналоги струн.

Существует ли обычный древовидный язык, в котором средняя высота дерева размера равна ни ни ? $n$ $\Theta(n)$ $\Theta(\sqrt{n})$

Очевидно, что существуют древовидные языки, высота дерева линейна по размеру; а в книге « Аналитическая комбинаторика» показано, например, что двоичные деревья размером имеют среднюю высоту . Если я правильно понимаю предложение VII.16 (стр.537) упомянутой книги, то существует большое подмножество регулярных древовидных языков со средней высотой , а именно те, в которых древовидный язык также является простым разнообразием деревьев, удовлетворяющих некоторым дополнительным условиям. $n$ $2\sqrt{ \pi n}$ $\Theta(\sqrt{n})$

Поэтому мне было интересно, существует ли обычный древовидный язык, показывающий другую среднюю высоту, или существует ли истинная дихотомия для обычных древовидных языков.

Примечание. Этот вопрос уже задавался ранее в области компьютерных наук , но на него не давали ответа более трех месяцев. Я хотел бы опубликовать его здесь, потому что вопрос слишком старый, чтобы его перенести, и потому что этот вопрос все еще интересен. Вот ссылка на оригинальный пост.

co.combinatorics fl.formal-languages tree regular-language john_leo
источник

Одно дерево с постоянной глубиной - очевидный ответ: o (\ sqrt {n}), но не . Я полагаю, вы, вероятно, имели в виду какой-то другой вопрос? Заменить на может быть?

Ω (\sqrt{n})

$\Omega(\sqrt{n})$

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

O (\sqrt{n})

$O(\sqrt{n})$

Джозеф Стэк

Да и нет. Я думаю, что обычный древовидный язык со средней глубиной (скажем) также будет очень интересным. Но вы правы в том, что мы должны исключить такие вырожденные случаи. Может быть, нам следует требовать, чтобы древовидный язык содержал бесконечно много элементов?

O (n^{1 / 3})

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

john_leo

Какие деревья ты имеешь в виду? Ранжированные деревья, не классифицированные деревья с порядковыми номерами, не классифицированные неупорядоченные деревья; и, кстати, что за древовидные автоматы вы имеете в виду, снизу вверх или сверху вниз?

ФХ

@JosephStack, как высота регулярного дерева может быть бесконечной? Дерево с узлами не может иметь высоту больше .

n

$n$

n

$n$

john_leo

@ Рафаэль: Если вы не считаете , мне не ясно, каким будет вопрос. Ответ на вопрос «существует ли бесконечный регулярный древовидный язык такой, что средняя высота является функцией с и ", очевидно, да: убедитесь, что для нечетных вас есть и четные . PS каждая функция, которую я могу себе представить, принадлежит для некоторого , так что это не правильное исправление :)

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

Джозеф Стек

Я полагаю, что ответ таков, как вы предполагаете, что никакие другие асимптотики, кроме , и , невозможны. Многообещающим способом доказать это может быть применение методов из статьи, которая выводит асимптотику к деревьям прогонов обычного языка. Обратите внимание, что дерево принимается, если существует дерево выполнения, поэтому должна быть возможность сначала получить (используя loc.cit. ) Среднюю высоту случайно сгенерированного дерева выполнения и извлечь ее оттуда, т.е. показать, что проецирование состояний делает не изменить среднюю высоту. $\Theta(1)$ $\Theta(\sqrt{n})$ $\Theta(n)$ $\Theta(\sqrt{n})$

Мартин Хофманн
источник

Я думаю, что это комментарий, а не ответ, поскольку эта попытка далека от ясности.

Дэнни

Существует ли обычный древовидный язык, в котором средняя высота дерева размера

Ответы: