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

18

Рассмотрим язык different состоящий из всех строк k- букв над Σ, таких, что никакие две буквы не равны:L k - d i s t i n c tLkdistinctkΣ

L k - d i s t i n c t : = { w = σ 1 σ 2 . , , σ к | я [ к ] : σ яЕ  и  J я : σ Jσ я }  

Lkdistinct:={w=σ1σ2...σki[k]:σiΣ  and  ji:σjσi}

Этот язык конечен и поэтому регулярен. В частности, если | Σ | = n|Σ|=n , то,|Lkdistinct|=(nk)k!|Lkdistinct|=(nk)k!

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

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

  • Наименьший NFA, который я могу построить, имеет состояний.4k(1+o(1))polylog(n)4k(1+o(1))polylog(n)

  • Следующая лемма подразумевает нижнюю оценку состояний:2k2k

Пусть LΣLΣ регулярный язык. Предположим, что существует nn пар P={(xi,wi)1in}P={(xi,wi)1in} таких что xiwjLxiwjL тогда и только тогда, когда i=ji=j . Тогда любой NFA, принимающий L, имеет как минимум n состояний.

  • Другая (тривиальная) нижняя граница - это loglog(nk)(nk) , которая представляет собой журнал размера наименьшего DFA для языка.

Меня также интересуют NFA, которые принимают только фиксированную дробь ( 0<ϵ<10<ϵ<1 ) от LkdistinctLkdistinct , если размер автомата меньше, чем ϵ4k(1+o(1))polylog(n)ϵ4k(1+o(1))polylog(n) .


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

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

Edit2:

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

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

(т. е. L(1,k)distinct=LkdistinctL(1,k)distinct=Lkdistinct ).

Конструкция, аналогичная описанной в комментариях, дает автомат размером с для ,O(ek2klog(1+r)poly(n))O(ek2klog(1+r)poly(n))L(r,k)distinctL(r,k)distinct

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

RB
источник
2
Можете ли вы описать свой верхний предел NFA?
mjqxxxx
Я пока не могу написать об этом, так как мы все еще работаем над этим и не завершили доказательство. Вместо этого я опишу гораздо более простой автомат размера : возьмем -совершенное семейство хэшей , Каждый такой хеш является функцией . Это означает, что для каждого подмножества размера не более существует функция такая, что она отображает каждый элемент подмножества на другое число. После хеширования результирующий алфавит имеет букв, следовательно, автомат с размером может принимать язык . O((2e)k2O(log(k))log(n))O((2e)k2O(log(k))log(n))(n,k)(n,k)HHh:[n][k]h:[n][k][n][n]kkhHhHkk2k2kLkdistinctLkdistinct
РБ
4
Нижняя граница дает просто считая количество состояний, в которых NFA может находиться после ровно шагов. Я не думаю, что мне известен какой-либо метод доказательства, который дает значительно лучшие оценки для общего размера, чем тот, который можно получить, чем просто смотреть на то, что происходит после шагов, для некоторого . Но здесь для каждого существует NFA, который может находиться только в одном из состояний после ровно состояний. (2o(1))k(2o(1))kk/2k/2tttttt(2+o(1))k(2+o(1))ktt
Noam
3
Доказательство (моего предыдущего утверждения): самый сложный случай - это ; выберите различных случайных подмножеств (из символов алфавита) размером ровно каждый и создайте NFA, который имеет состояние для каждого с некоторым путем, ведущим к нему, если только первый символы различны, содержатся в и имеют принимающий путь от него, если все следующие символы различны и содержатся в дополнении к . Аргумент подсчета покажет, что whp (по случайному выборуt=k/2t=k/22kpoly(k,logn)2kpoly(k,logn)SiSinnttiittSiSiktktSiSiSiSis) этот NFA действительно примет все желаемый язык.
Noam
3
В предыдущей конструкции самый простой способ построения NFA будет иметь состояние для каждого возможного префикса длины и для каждого возможного суффикса длины . Вместо этого часть префикса и часть суффикса NFA могут быть построены рекурсивно с использованием той же рандомизированной конструкции (но теперь только внутри и ее дополнения, соответственно), и это даст общего размера. j<tj<tj>ktj>ktSiSi(4+o(1))k(4+o(1))k
Noam

Ответы:

2

Это не ответ, а метод, который, я считаю, оставил бы более низкую оценку. Разрежет проблему после букву читается. Обозначим семейство элемент множеств по и семейство элементов из множества с помощью . Обозначим состояния, которые могут быть достигнуты после считывания элементов (в любом порядке) с помощью и состояния, из которых можно достичь принимающего состояния после считывания элементов (в любом порядке) с помощью . Нам нужен этот тогда и только тогда, когдаaaaa[n][n]AAb=kab=ka[n][n]BBAASASABBTBTBSATBSATBAB=AB= . Это уже дает нижнюю границу для необходимого количества состояний, и я думаю, что это может дать что-то нетривиальное.

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

Обновление 2014.03.24: Фактически, если вышеупомянутый гиперграф может быть реализован на вершинах, то мы также получаем недетерминированный протокол сложности связи длины для множества несвязных с входными наборами размеров и (фактически два проблемы эквивалентны). Узким местом является, конечно, когда , для этого я мог найти только следующее в книге Эяля и Ноама: доказано стандартным вероятностным аргументом. К сожалению, я не смог (пока) найти достаточно хорошие нижние оценки для этой проблемы, но, предполагая, что вышеупомянутое является точным, это дало бы нижнюю оценкуsslogslogsaabba=b=k/2a=b=k/2N1(DISJa)log(2kloge(na))N1(DISJa)log(2kloge(na))Ω(2klogn)Ω(2klogn) объединяя две нижние границы, которые вы упомянули.

domotorp
источник
1
Спасибо @domotorp за ваш ответ. Это похоже на доказательство леммы, которую я использовал для нижней границы в исходном вопросе, но без указания фактических и и, следовательно, не счетной границы. Ваш комментарий на вопрос выше предполагает, что предел не может быть улучшен этим методом, как вы думаете, это могло бы быть лучше? xixiyiyi2k2k
РБ
3
Весь смысл моего комментария выше состоял в том, что эти методы не могут дать нижнюю границу выше . Это действительно то, что делает эту проблему интересной для меня. (2+o(1))k(2+o(1))k
Noam
@Noam: Пусть k = 2, a = b = 1. Уже тогда мы получаем нижнюю границу как каждый должен быть различным. lognlognSASA
domotorp
1
@domotorp: скрывает коэффициент : вот анализ для наихудшего случая, когда : начать с фиксированных и и выбрать случайным образом подмножество из букв тогда мы имеем . Теперь случайным образом выберем таких множеств, тогда вероятность того, что хотя бы для одного из них это произойдет, равна . Если мы выберем то получим, что это так для ВСЕХ непересекающихся множеств и (размераo(1)o(1)O(klogn)O(klogn)a=b=k/2a=b=k/2AABBSSnnPr[ASandBSc]=2kPr[ASandBSc]=2kr2kr2k1exp(r)1exp(r)r=O(log(nk))=O(klogn)r=O(log(nk))=O(klogn)AABBk/2k/2). Общее число таких «S в этой конструкции является . SSO(2kklogn)O(2kklogn)
Noam
2
@Noam: я извиняюсь, но я никогда не видел скрытого в , тем более что проблема также интересна imho для . Но вы правы, что РБ спросил о . lognlogno(1)o(1)k<<lognk<<lognk=polylognk=polylogn
domotorp
0

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

Я пытаюсь доказать нижнюю границу . Вот вопрос, который, я уверен, даст такую ​​нижнюю границу: найдите минимум такой, что существует функция который сохраняет дизъюнктность, т. Что если . Я почти уверен, что нижняя граница почти сразу подразумевает нижнюю границу для нашей задачи. примерно соответствует набору узлов, к которому NFA может добраться после считывания первых символов ввода, когда набор этих4k4kttf:{S[n],|S|=k/2}{0,1}tf:{S[n],|S|=k/2}{0,1}tS1S2=S1S2=f(S1)f(S2)=f(S1)f(S2)=t2kt2k22k=4k22k=4kf(S)f(S)k/2k/2k/2k/2символы .SS

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

пельмени мобиус
источник
2
Мои комментарии выше показывают, что этот подход не может победить(2+o(1))n
Noam