Considere el lenguaje consiste en todas las cadenas -letter sobre modo que no haya dos letras iguales: k Σ
Este lenguaje es finito y, por lo tanto, regular. Específicamente, si , entonces \ left | L_ {k-distinct} \ right | = \ binom {n} {k} k! .| L k - d i s t i n c t | = ( n
¿Cuál es el autómata finito no determinista más pequeño que acepta este lenguaje?
Actualmente tengo los siguientes límites superiores e inferiores sueltos:
El NFA más pequeño que puedo construir tiene estados.
El siguiente lema implica un límite inferior de estados:
Deje que sea un lenguaje regular. Supongamos que hay pares modo que si y solo si . Entonces, cualquier NFA que acepte L tiene al menos n estados.
- Otro límite inferior (trivial) es , que es el registro del tamaño del DFA más pequeño para el idioma.
También estoy interesado en los NFA que aceptan solo una fracción fija ( ) de , si el tamaño del autómata es menor que .
Editar: Acabo de comenzar una recompensa que tuvo un error en el texto.
Quise decir que podemos asumir mientras escribía .
Edit2:
La recompensa terminará pronto, así que si alguien está interesado en lo que quizás sea una forma más fácil de ganarlo, considere el siguiente idioma:
contiene símbolos distintos y ningún símbolo aparece más de veces .
(es decir, ).
Una construcción similar a la de los comentarios proporciona un autómata de tamaño para .
¿Se puede mejorar esto? ¿Cuál es el mejor límite inferior que podemos mostrar para este idioma?
Respuestas:
Esta no es una respuesta, sino un método que creo que dejaría un límite inferior mejorado. Cortemos el problema después de cartas son leídas. Denotar la familia de elemento conjuntos de por y la familia de conjuntos de elementos de por . Denote los estados que se pueden alcanzar después de leer los elementos de (en cualquier orden) mediante y los estados desde los cuales se puede alcanzar un estado de aceptación después de leer los elementos de (en cualquier orden) mediante . Necesitamos que si y solo sia a [n] A b=k−a [n] B A SA B TB SA∩TB≠∅ A∩B=∅ . Esto ya da un límite inferior para el número requerido de estados y creo que podría dar algo no trivial.
Este problema esencialmente requiere un límite inferior en el número de vértices de una hipergrafía cuyo gráfico lineal es (parcialmente) conocido. Problemas similares fueron estudiados, por ejemplo, por Bollobas y existen varios métodos de prueba conocidos que pueden ser útiles.
Actualización 03/24/2014: De hecho si el hypergraph anterior se puede realizar en vértices, entonces nosotros también consigue un protocolo de comunicación complejidad no determinista de la longitud para el sistema de disyunción con entradas de conjuntos de tamaño y (de hecho los dos los problemas son equivalentes) El cuello de botella es, por supuesto, cuando , para esto solo pude encontrar lo siguiente en el libro de Eyal y Noam: demostrado por el argumento probabilístico estándar. Desafortunadamente, no pude (todavía) encontrar límites inferiores lo suficientemente buenos para este problema, pero suponiendo que lo anterior sea nítido, daría un límite inferiors logs a b a=b=k/2 N1(DISJa)≤log(2kloge(na)) Ω(2klogn) unificando los dos límites inferiores que ha mencionado.
fuente
Algunos trabajos en progreso:
Estoy tratando de demostrar un límite inferior de . Aquí hay una pregunta que estoy seguro de que daría un límite inferior: encontrar el mínimo tal que exista una función que conserva la desunión, es decir, que iff . Estoy bastante seguro de que un límite inferior de implicaría casi de inmediato un límite inferior de para nuestro problema. corresponde aproximadamente al conjunto de nodos a los que puede llegar el NFA después de leer los primeros símbolos de la entrada, cuando el conjunto de estos t f : { S ⊆ [ n ] , | S | = k / 2 } → { 0 , 1 } t S 1 ∩ S 2 = ∅ f ( S 1 ) ∩ f ( S 2 ) = ∅ t ≥ 2 k 2 2 k = 4 k f ( S )4k t f:{S⊆[n],|S|=k/2}→{0,1}t S1∩S2=∅ f(S1)∩f(S2)=∅ t≥2k 22k=4k f(S) k / 2 Sk/2 k/2 símbolos es .S
Creo que la solución a esta pregunta ya podría conocerse, ya sea en la literatura sobre la complejidad de la comunicación (especialmente en los documentos que tratan el problema de la desunión; tal vez algunos argumentos de rango de matriz ayudarán), o en la literatura sobre codificaciones (por ejemplo, como esta ).
fuente