Limites no tamanho do menor NFA para L_k distinto

18

Considere o idioma L k - d i s t i n c tLkdistinct constituído por todas as cadeias de letras kk sobre Σ deΣ modo que não haja duas letras iguais:

L k - d i s t i n c t : = { w = σ 1 σ 2 . . . σ k | i [ k ] : σ iΣ  e  j i : σ jσ i }  

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

Essa linguagem é finita e, portanto, regular. Especificamente, se | Σ | = n|Σ|=n , então.| L k - d i s t i n c t | = ( nk ) k!|Lkdistinct|=(nk)k!

Qual é o menor autômato finito não determinístico que aceita essa linguagem?

Atualmente, tenho os seguintes limites superiores e inferiores soltos:

  • O menor NFA que eu posso construir possui estados.4 k ( 1 + S ( 1 ) )p o l y L o g ( n )4k(1+o(1))polylog(n)

  • O seguinte lema implica um limite inferior de 2 k2k estados:

Seja L ΣLΣ uma linguagem regular. Suponha que existem nn pares P = { ( x i , w i ) 1 i n }P={(xi,wi)1in} modo que xiwjLxiwjL se e somente se i=ji=j . Então, qualquer NFA que aceite L tem pelo menos n estados.

  • Outro limite inferior (trivial) é loglog(nk)(nk) , que é o log do tamanho do menor DFA para o idioma.

Também estou interessado em NFAs que aceitam apenas uma fração fixa ( 0<ϵ<10<ϵ<1 ) de LkdistinctLkdistinct , se o tamanho do autômato for menor que ϵ4k(1+o(1))polylog(n)ϵ4k(1+o(1))polylog(n) .


Edit: Acabei de iniciar uma recompensa que teve um erro no texto.

Eu quis dizer que podemos assumir k=polylog(n)k=polylog(n) enquanto escrevi k=O(log(n))k=O(log(n)) .

Edit2:

A recompensa terminará em breve; portanto, se alguém estiver interessado no que talvez seja uma maneira mais fácil de obtê-la, considere o seguinte idioma:

L(r,k)distinct:={w:wL(r,k)distinct:={w:w contém kk símbolos distintos e nenhum símbolo aparece mais que rr vezes }} .

(ou seja, L(1,k)distinct=LkdistinctL(1,k)distinct=Lkdistinct ).

Uma construção semelhante à dos comentários fornece o autômato do tamanho para .O(ek2klog(1+r)poly(n))O(ek2klog(1+r)poly(n))L(r,k)distinctL(r,k)distinct

Isso pode ser melhorado? Qual é o melhor limite inferior que podemos mostrar para esse idioma?

RB
fonte
2
Você pode descrever seu NFA com limite superior?
Mjqxxxx
Ainda não posso escrever sobre isso, pois ainda estamos trabalhando e ainda não concluímos a prova. Em vez disso, descreverei um autômato muito mais simples do tamanho : Faça uma família de hash perfeita . Todo esse hash é uma função . Isso significa que para cada subconjunto de no máximo , , existe uma função , de forma que ele mapeia todos os itens do subconjunto para um número diferente. Após o hash, o alfabeto resultante possui letras; portanto, um autumaton de tamanho pode aceitar o idioma . 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
RB
4
O limite inferior fornece ( 2 - o ( 1 ) ) k(2o(1))k apenas contando o número de estados em que o NFA pode estar após exatamente k / 2k/2 passos. Acho que não conheço nenhum método de prova que ofereça limites significativamente melhores para o tamanho total do que o que pode ser obtido do que apenas observando o que acontece após tt etapas, para alguns tt . Mas aqui, para cada t,t existe um NFA que pode estar em apenas um dos ( 2 + o ( 1 ) ) k(2+o(1))k estados após exatamente tt estados.
Noam
3
Prova (da minha reivindicação anterior): O caso mais difícil é t = k / 2 ; escolha 2 kp o l y ( k , log n ) subconjuntos aleatórios diferentes S i (dos n símbolos do alfabeto) de tamanho exatamente t cada e construa um NFA que tenha um estado para cada i com algum caminho que o conduz se primeiros t símbolos são todos diferentes e estão contidos no S i , e tem um caminho de aceitar que sse o seguinte k - tt=k/22kpoly(k,logn)SintitSiktsímbolos são todos diferentes e estão contidos no complemento de S i . Um argumento contagem irá mostrar que whp (sobre a escolha aleatória da S i 's) este NFA vai realmente aceitar tudo o idioma desejado. SiSi
Noam
3
Na construção anterior, a maneira mais simples de construir o NFA terá um estado para cada prefixo possível de comprimento j < te para cada sufixo possível de comprimento j > k - t . Em vez disso, a parte do prefixo e a parte do sufixo da NFA podem ser construídas recursivamente usando a mesma construção aleatória (mas agora apenas dentro de S i e seu complemento, respectivamente) e isso daria um tamanho total ( 4 + o ( 1 ) ) k . j<tj>ktSi(4+o(1))k
Noam

Respostas:

2

Esta não é uma resposta, mas um método que acredito que deixaria um limite inferior aprimorado. Vamos cortar o problema depois de cartas são lidas. Denotar a família de um elemento conjuntos de [ n ] por A e a família de b = k - um elemento conjuntos de [ n ] por B . Indique os estados que podem ser alcançados após a leitura dos elementos de A (em qualquer ordem) por S A e os estados a partir dos quais um estado de aceitação pode ser alcançado após a leitura dos elementos de B (em qualquer ordem) por T Baa[n]Ab=ka[n]BASABTB. Precisamos que S AT B se e somente se A B = . Isso já dá um limite mais baixo para o número necessário de estados e acho que poderia dar algo não trivial.SATBAB=

Esse problema exige essencialmente um limite inferior no número de vértices de um hipergrafo cujo gráfico de linhas é (parcialmente) conhecido. Problemas semelhantes foram estudados, por exemplo, por Bollobas e existem vários métodos de prova conhecidos que podem ser úteis.

Atualização 2014/03/24: Na verdade, se o hipergrafo acima pode ser realizado em s vértices, então nós também obter um protocolo de comunicação complexidade não-determinista do comprimento de registro s para o conjunto de disjunção com entradas conjuntos de tamanho de um e b (na verdade, os dois problemas são equivalentes). Obviamente, o gargalo é quando a = b = k / 2 ; para isso, só consegui encontrar o seguinte no livro de Eyal e Noam: N 1 ( D I S J a ) log ( 2 k log e (slogsaba=b=k/2na ) )comprovada pelo argumento probabilístico padrão. Infelizmente, ainda não consegui encontrar limites inferiores suficientemente bons para esse problema, mas, assumindo que o exposto acima é nítido, daria um limite inferiorΩ(2klogn)unificando os dois limites inferiores mencionados.N1(DISJa)log(2kloge(na))Ω(2klogn)

domotorp
fonte
1
Obrigado @domotorp pela sua resposta. Isso parece muito como a prova do lema que eu usei para o limite inferior na pergunta original, mas sem especificar o real x i 's e y i ' s, e, portanto, não um limite contáveis. Seu comentário sobre a pergunta acima sugere que o limite de 2 k não pode ser melhorado por esse método, você acha que isso poderia melhorar? xiyi2k
RB
3
O ponto principal do meu comentário acima foi que essas técnicas não podem fornecer um limite inferior acima ( 2 + o ( 1 ) ) k . Isso é realmente o que torna esse problema interessante para mim. (2+o(1))k
Noam
@Noam: Seja k = 2, a = b = 1. Já temos um log n limite inferior, pois todo S A deve ser diferente. lognSA
23414 Domotorp
1
@domotorp: O O ( 1 ) esconde um S ( k log N ) fator: Aqui é a análise para o pior caso em que um = b = k / 2 : Iniciar com um fixo Um e B e escolher aleatoriamente um subconjunto S de as n letras então temos P r [ A So(1)O(klogn)a=b=k/2ABSnum n dB S c ] = 2 - k . Agora escolha r 2 k de tais conjuntos aleatoriamente, então a probabilidade de que para pelo menos um deles aconteça é 1 - e x p ( - r ) . Se escolhermos r = O ( log ( nPr[ASandBSc]=2kr2k1exp(r)k ) )=O(klogn), entendemos que whp é assim para TODOS os conjuntos disjuntosAeB(do tamanhok/2). O número total de taisS'nesta construção éO(2kklogn). r=O(log(nk))=O(klogn)ABk/2
Noam
2
@Noam: I am sorry but I have never seen a logn hidden in an o(1), especially as the problem is also interesting imho for k<<logn. But you are right that R B asked about k=polylogn.
domotorp
0

Some work in progress:

I'm trying to prove a lower bound of 4k. Here is a question that I'm pretty sure would give such a lower bound: find the minimum t such that there exists a function f:{S[n],|S|=k/2}{0,1}t that preserves disjointness, i.e. that S1S2= iff f(S1)f(S2)=. I'm pretty sure a lower bound of t2k would almost immediately imply a lower bound of 22k=4k for our problem. f(S) roughly corresponds to the set of nodes the NFA can get to after reading the first k/2 symbols of the input, when the set of these k/2 symbols is S.

I think the solution to this question might already be known, either in the communication complexity literature (especially in papers dealing with the disjointness problem; maybe some matrix rank arguments will help), or in literature about encodings (e.g. like this).

mobius dumpling
fonte
2
My comments above show that this approach cannot beat (2+o(1))n
Noam