Границы по размеру наименьшего NFA для L_k-отчетливых

Рассмотрим язык different состоящий из всех строк букв над таких, что никакие две буквы не равны: $L_{k-distinct}$ $k$ $\Sigma$

L k - d i s t i n c t : = {w = σ 1 σ 2 . . . σ k ∣ \forall i \in [k] : σ i \in Σ and \forall j \neq i : σ j \neq σ i}

$L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]: \sigma_i\in\Sigma ~\text{ and }~ \forall j\ne i: \sigma_j\ne\sigma_i \}$

Этот язык конечен и поэтому регулярен. В частности, если $\left|\Sigma\right|=n$ , то, $\left|L_{k-distinct}\right| = \binom{n}{k} k!$

Какой самый маленький недетерминированный конечный автомат принимает этот язык?

В настоящее время у меня есть следующие свободные верхние и нижние границы:

Наименьший NFA, который я могу построить, имеет состояний. $4^{k(1+o(1))}\cdot polylog(n)$
Следующая лемма подразумевает нижнюю оценку состояний: $2^k$

Пусть $L ⊆ Σ^*$ регулярный язык. Предположим, что существует $n$ пар $P = \{ (x_i, w_i) \mid 1 ≤ i ≤ n \}$ таких что $x_i\cdot w_j \in L$ тогда и только тогда, когда $i=j$ . Тогда любой NFA, принимающий L, имеет как минимум n состояний.

Другая (тривиальная) нижняя граница - это $log$ $n\choose k$ , которая представляет собой журнал размера наименьшего DFA для языка.

Меня также интересуют NFA, которые принимают только фиксированную дробь ( $0<\epsilon<1$ ) от $L_{k-distinct}$ , если размер автомата меньше, чем $\epsilon\cdot 4^{k(1+o(1))}\cdot polylog (n)$ .

Редактировать: я только что начал щедрость с ошибкой в тексте.

Я имел в виду, что мы можем предположить, что $k=polylog(n)$ а я написал $k=O(log(n))$ .

Edit2:

Награда скоро закончится, поэтому, если кто-то заинтересован в том, что, возможно, является более простым способом заработка, рассмотрите следующий язык:

$L_{(r,k)-distinct} :=\{w : w$ содержит $k$ различных символов, и ни один символ не появляется более $r$ раз $\}$ .

(т. е. $L_{(1,k)-distinct} = L_{k-distinct}$ ).

Конструкция, аналогичная описанной в комментариях, дает автомат размером с для , $O(e^k\cdot 2^{k\cdot log(1+r)}\cdot poly(n))$ $L_{(r,k)-distinct}$

Можно ли это улучшить? Какую лучшую нижнюю границу мы можем показать для этого языка?

automata-theory lower-bounds regular-language communication-complexity streaming RB
источник

Можете ли вы описать свой верхний предел NFA?

mjqxxxx

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

O((2e)k∗2O(log(k))∗log(n)) $O((2e)^k * 2^{O(log(k))} * log(n))$

(n,k) $(n,k)$

H $H$

h:[n]→[k] $h: [n] \to [k]$

[n] $[n]$

k $k$

h∈H $h\in H$

k $k$

2k $2^k$

Lk−distinct $L_{k-distinct}$

РБ

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

(2−o(1))k $(2-o(1))^k$

k/2 $k/2$

t $t$

(2+o(1))k $(2+o(1))^k$

t $t$

Noam

Доказательство (моего предыдущего утверждения): самый сложный случай - это ; выберите различных случайных подмножеств (из символов алфавита) размером ровно каждый и создайте NFA, который имеет состояние для каждого с некоторым путем, ведущим к нему, если только первый символы различны, содержатся в и имеют принимающий путь от него, если все следующие символы различны и содержатся в дополнении к . Аргумент подсчета покажет, что whp (по случайному выбору

t=k/2 $t=k/2$

2k⋅poly(k,logn) $2^k \cdot poly(k, \log n)$

Si $S_i$

n $n$

t $t$

i $i$

t $t$

Si $S_i$

k−t $k-t$

Si $S_i$

Si $S_i$ s) этот NFA действительно примет все желаемый язык.

Noam

В предыдущей конструкции самый простой способ построения NFA будет иметь состояние для каждого возможного префикса длины и для каждого возможного суффикса длины . Вместо этого часть префикса и часть суффикса NFA могут быть построены рекурсивно с использованием той же рандомизированной конструкции (но теперь только внутри и ее дополнения, соответственно), и это даст общего размера.

j<t $j < t$

j>k−t $j > k-t$

Si $S_i$

(4+o(1))k $(4+o(1))^k$

Noam

Ответы:

Это не ответ, а метод, который, я считаю, оставил бы более низкую оценку. Разрежет проблему после букву читается. Обозначим семейство элемент множеств по и семейство элементов из множества с помощью . Обозначим состояния, которые могут быть достигнуты после считывания элементов (в любом порядке) с помощью и состояния, из которых можно достичь принимающего состояния после считывания элементов (в любом порядке) с помощью . Нам нужен этот тогда и только тогда, когда $a$ $a$ $[n]$ $\mathcal A$ $b=k-a$ $[n]$ $\mathcal B$ $A$ $S_A$ $B$ $T_B$ $S_A\cap T_B\ne \emptyset$ $A\cap B=\emptyset$ . Это уже дает нижнюю границу для необходимого количества состояний, и я думаю, что это может дать что-то нетривиальное.

Эта проблема, по существу, требует нижней границы числа вершин гиперграфа, линейный граф которого (частично) известен. Подобные проблемы были изучены, например, Боллобасом, и есть несколько известных методов доказательства, которые могут быть полезны.

Обновление 2014.03.24: Фактически, если вышеупомянутый гиперграф может быть реализован на вершинах, то мы также получаем недетерминированный протокол сложности связи длины для множества несвязных с входными наборами размеров и (фактически два проблемы эквивалентны). Узким местом является, конечно, когда , для этого я мог найти только следующее в книге Эяля и Ноама: доказано стандартным вероятностным аргументом. К сожалению, я не смог (пока) найти достаточно хорошие нижние оценки для этой проблемы, но, предполагая, что вышеупомянутое является точным, это дало бы нижнюю оценку $s$ $\log s$ $a$ $b$ $a=b=k/2$ $N^1(DISJ_a)\le \log \big(2^k \log_e {n\choose a}\big)$ $\Omega(2^k\log n)$ объединяя две нижние границы, которые вы упомянули.

domotorp
источник

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

xi $x_i$

yi $y_i$

2k $2^k$

РБ

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

(2+o(1))k $(2+o(1))^k$

Noam

@Noam: Пусть k = 2, a = b = 1. Уже тогда мы получаем нижнюю границу как каждый должен быть различным.

logn $\log n$

SA $S_A$

domotorp

@domotorp: скрывает коэффициент : вот анализ для наихудшего случая, когда : начать с фиксированных и и выбрать случайным образом подмножество из букв тогда мы имеем . Теперь случайным образом выберем таких множеств, тогда вероятность того, что хотя бы для одного из них это произойдет, равна . Если мы выберем то получим, что это так для ВСЕХ непересекающихся множеств и (размера

o(1) $o(1)$

O(klogn) $O(k\log n)$

a=b=k/2 $a=b=k/2$

A $A$

B $B$

S $S$

n $n$

Pr[A⊆SandB⊆Sc]=2−k $Pr[A \subseteq S \:and\: B \subseteq S^c]=2^{-k}$

r2k $r2^k$

1−exp(−r) $1-exp(-r)$

r=O(log(nk))=O(klogn) $r = O(\log {n \choose k}) = O(k \log n)$

A $A$

B $B$

k/2 $k/2$ ). Общее число таких «S в этой конструкции является .

S $S$

O(2kklogn) $O(2^k k \log n)$

Noam

@Noam: я извиняюсь, но я никогда не видел скрытого в , тем более что проблема также интересна imho для . Но вы правы, что РБ спросил о .

logn $\log n$

o(1) $o(1)$

k<<logn $k<<\log n$

k=polylogn $k=polylog n$

domotorp

Некоторая работа в процессе:

Я пытаюсь доказать нижнюю границу . Вот вопрос, который, я уверен, даст такую нижнюю границу: найдите минимум такой, что существует функция который сохраняет дизъюнктность, т. Что если . Я почти уверен, что нижняя граница почти сразу подразумевает нижнюю границу для нашей задачи. примерно соответствует набору узлов, к которому NFA может добраться после считывания первых символов ввода, когда набор этих $4^k$ $t$ $f:\{S \subseteq [n], |S|=k/2 \} \rightarrow \{0,1\}^t$ $S_1 \cap S_2 = \emptyset$ $f(S_1) \cap f(S_2) = \emptyset$ $t \ge 2k$ $2^{2k}=4k$ $f(S)$ $k/2$ $k/2$ символы . $S$

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

пельмени мобиус
источник

Мои комментарии выше показывают, что этот подход не может победить

$(2+o(1))^n$

Noam