Idiomas reconocidos por DFA de tamaño polinómico

Para un alfabeto finito fijo , un lenguaje formal sobre es normal si existe un autómata finito determinista (DFA) sobre que acepta exactamente .L Σ Σ $\Sigma$$L$$\Sigma$$\Sigma$$L$

Me interesan los idiomas que son "casi" regulares en el sentido de que pueden ser reconocidos por las familias de autómatas de tamaño que crece solo polinómicamente con la longitud de la palabra.

Formalmente, permítanme decir que un lenguaje formal es reconocido por una familia DFA si por cada palabra , dejando, está en si acepta (no importa si el otro acepta o no), y permítame definir los lenguajes p-regulares como idiomas reconocidos por una familia DFA computable PTIME de tamaño polinómico, es decir, allí es un polinomio tal que para todo( A n ) w ∈ Σ ∗ n = | w | w L A n w A i ( A n ) P | A n | ≤ P ( n ) $L$ $(A_n)$$w \in \Sigma^*$$n = |w|$$w$$L$$A_n$$w$$A_i$$(A_n)$$P$$|A_n| \leq P(n)$$n$. (Este nombre, "p-regular", es algo que inventé, mi pregunta es saber si ya existe otro nombre para esto. Tenga en cuenta que esto no es lo mismo que los lenguajes p-regulares en el sentido de autómatas de permutación ).

Esta clase de lenguajes p-regulares incluye, por supuesto, los idiomas regulares (solo tome para todo , donde es un poco de DFA que reconoce el lenguaje regular); pero es un superconjunto estricto: por ejemplo, es bien sabido que tiene contexto pero no es regular, pero es p- regular ( sólo tiene que contar ocurrencias de y ocurrencias de ). Sin embargo, debido a que requiero que los autómatas sean DFA de tamaño polinómico , algunos lenguajes formales (en realidad, algunos lenguajes libres de contexto) no sonn A { a n b n ∣ n ∈ N } A n n a n $A_n = A$$n$$A$$\{a^n b^n \mid n \in \mathbb{N}\}$$A_n$$n$$a$$n$$b$p-regular: por ejemplo, el lenguaje de los palíndromos no es p-regular, porque, intuitivamente, cuando has leído la primera mitad de una palabra, necesitas tener tantos estados diferentes como posibles palabras, porque necesitarás para que coincida exactamente esta primera mitad con la segunda.

Entonces, la clase de lenguajes p-regulares es un superconjunto estricto de lenguajes regulares que es incomparable con los lenguajes libres de contexto. De hecho, parece que incluso puede obtener una jerarquía de idiomas al distinguir los lenguajes p-regulares en función del grado más pequeño del polinomio para el que son -regulares . No es demasiado difícil construir ejemplos para demostrar que esta jerarquía es estricta; aunque no entiendo bien la interacción entre esto y una definición alternativa de la jerarquía que también restringiría la complejidad de calcular el .P A $P$$P$$A_n$

Mi pregunta es: ¿ esta clase que llamo p-regular, y la jerarquía asociada, ha sido estudiada anteriormente? En caso afirmativo, ¿dónde y con qué nombre?

(Un posible vínculo es con el campo o la transmisión, o los algoritmos en línea. En la terminología de los algoritmos de transmisión para problemas de reconocimiento de idioma , estoy interesado en la clase (o jerarquía) de idiomas que pueden tener algoritmos de reconocimiento deterministas de un solo paso, usando un número polinómico de estados (por lo tanto, un tamaño de memoria logarítmica), pero no encontré ninguna definición de esta clase en este documento o documentos relacionados. Sin embargo, tenga en cuenta que en mi formulación del problema se conoce de antemano la longitud de la palabra , lo cual es menos natural en un contexto de transmisión: en la transmisión se puede ver esto como un autómata infinito, un símbolo especial de "fin de palabra" y una restricción de que el número de estados alcanzables después de leer caracteres es polinómico en $n$$n$. Creo que esta distinción marca la diferencia, posible ejemplo: lenguaje de palabras binarias cuyo valor es divisible por su longitud, que es fácil para una longitud fija pero (supongo) no puede ser representado por un autómata infinito en el sentido anterior porque no hay identificaciones se puede hacer si la longitud no se conoce de antemano)

(La motivación para esta clase p-regular es que algunos problemas, como la probabilidad de membresía en el lenguaje para palabras probabilísticas, parecen ser PTIME no solo cuando el idioma es regular, sino también cuando es p-regular, y estoy intentando para caracterizar exactamente en qué circunstancias esos problemas son manejables).

la pregunta no parece haberse estudiado mucho (una posibilidad es intentar encontrar una relación con una clase de complejidad "cercana", por ejemplo, P / poli, etc.); aunque aquí hay al menos un árbitro que lo toca:

• Operaciones de lenguaje con expresiones regulares de tamaño polinómico Gruber / Holzer

  Este trabajo aborda preguntas sobre hasta qué punto las operaciones del lenguaje que preservan la regularidad afectan la complejidad descriptiva de las expresiones regulares. Se identifican algunas operaciones de lenguaje que son factibles para expresiones regulares en el sentido de que el resultado de la operación se puede representar como una expresión regular de polinomio de tamaño en el de los operandos. Demostramos que tomar cocientes de lenguaje, en particular los cierres de prefijos y sufijos, de un conjunto regular puede generar como máximo una explosión cuadrática en el tamaño de expresión requerido. La operación de desplazamiento circular puede causar solo un aumento cúbico de tamaño y al menos una hinchazón cuadrática puede ser necesaria en el peor de los casos.

$n$

• Encontrar la tasa de crecimiento de un lenguaje regular o sin contexto en tiempo polinomial (Gawrychowski, Krieger, Rampersad, Shallit)

  Dado un lenguaje L sin contexto, podemos probar si es de crecimiento polinómico o exponencial en el tiempo polinómico. Además, si es de crecimiento polinómico, también podemos encontrar el orden exacto de este polinomio en el tiempo polinómico.