Idiomas reconhecidos pelos DFAs de tamanho polinomial

Para um alfabeto finito fixo , uma linguagem formal sobre é regular, se existe um autômato finito determinístico (DFA) sobre que aceita exatamente .$\Sigma$$L$$\Sigma$$\Sigma$$L$

Estou interessado em idiomas "quase" regulares no sentido de que podem ser reconhecidos por famílias de tamanho de autômatos que crescem apenas polinomialmente com o comprimento da palavra.

Formalmente, deixe-me dizer que uma linguagem formal é reconhecida por uma família DFA se para cada palavra , deixando, está em se aceita (não importa se os outros aceitam ou não) e deixe-me definir idiomas regulares como idiomas reconhecidos por uma família DFA computável em PTIME de tamanho polinomial, ou seja, é um polinômio tal que para todos os$L$ $(A_n)$$w \in \Sigma^*$$n = |w|$$w$$L$$A_n$$w$$A_i$$(A_n)$$P$$|A_n| \leq P(n)$$n$. (Esse nome, "p-regular", é algo que eu inventei, minha pergunta é saber se já existe outro nome para isso. Observe que isso não é o mesmo que idiomas p-regulares no sentido de autômatos de permutação .)

Esta classe de idiomas regulares p inclui, obviamente, idiomas regulares (basta pegar para todos os , onde é um DFA que reconhece o idioma regular); mas é um superconjunto estrito: por exemplo, é sabido que é livre de contexto, mas não regular, mas é regulares ( apenas tem que contar ocorrências de e ocorrências de ). No entanto, como eu exijo que os autômatos sejam DFAs de tamanho polinomial , algumas linguagens formais (na verdade algumas linguagens sem contexto) não sãon 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 exemplo, o idioma dos palíndromos não é p-regular, porque, intuitivamente, quando você lê a primeira metade de uma palavra, você precisa ter o maior número possível de estados possíveis, porque você precisará para combinar exatamente esse primeiro tempo com o segundo.

Portanto, a classe de linguagens p-regulares é um superconjunto estrito de linguagens regulares que é incomparável com linguagens sem contexto. Na verdade, parece que você pode até obter uma hierarquia de línguas, distinguindo línguas p regular com base no menor grau do polinômio para o qual eles são P -Regular. Não é muito difícil construir exemplos para mostrar que essa hierarquia é estrita; embora ainda não compreenda bem a interação entre isso e uma definição alternativa da hierarquia que também restringiria a complexidade da computação do A n .$P$$P$$A_n$

Minha pergunta é: essa classe que chamo de p-regular e a hierarquia associada já foram estudadas antes? Se sim, onde e sob qual nome?

(Um possível link está com o campo, o fluxo ou os algoritmos on-line. Na terminologia dos algoritmos de fluxo para problemas de reconhecimento de idioma , estou interessado na classe (ou hierarquia) de idiomas que podem ter algoritmos determinísticos de reconhecimento de uma passagem, usando um número polinomial de estados (portanto, um tamanho de memória logarítmica), mas não encontrei nenhuma definição dessa classe neste artigo ou em artigos relacionados. Note, no entanto, que, ao descrever o problema, o comprimento da palavra é conhecido antecipadamente , o que é menos natural em um contexto de streaming: no streaming, você pode ver isso como um autômato infinito, um símbolo especial de "fim de palavra" e uma restrição de que o número de estados alcançáveis ​​após a leitura de caracteres seja polinomial em $n$$n$. Penso que essa distinção faz diferença, exemplo possível: linguagem de palavras binárias cujo valor é divisível por seu comprimento, o que é fácil por um comprimento fixo, mas (conjecturo) não pode ser representado por um autômato infinito no sentido anterior, porque nenhuma identificação pode ser feito se o comprimento não for conhecido antecipadamente.)

(A motivação para esta aula p-regular é que alguns problemas, como a probabilidade de pertencer ao idioma para palavras probabilísticas, parecem ser PTIME não apenas quando o idioma é regular, mas também quando é p-regular, e estou tentando caracterizar exatamente em que circunstâncias esses problemas são tratáveis.)

a questão parece não ter sido muito estudada (uma possibilidade é tentar encontrar um relacionamento com uma classe de complexidade "próxima", como P / poli etc); embora aqui haja pelo menos uma referência que toque nela:

• Operações de linguagem com expressões regulares de tamanho polinomial Gruber / Holzer

  Este trabalho trata de questões sobre até que ponto as operações de linguagem que preservam a regularidade afetam a complexidade descritiva das expressões regulares. São identificadas algumas operações de linguagem que são viáveis ​​para expressões regulares no sentido de que o resultado da operação pode ser representado como uma expressão regular de polinômio de tamanho no dos operandos. Provamos que a obtenção de quocientes de idioma, em particular o fechamento de prefixos e sufixos de um conjunto regular, pode incorrer no máximo em uma explosão quadrática no tamanho de expressão necessário. A operação de deslocamento circular pode causar apenas um aumento cúbico no tamanho e pelo menos um inchaço quadrático pode ser necessário no pior caso.

como o AS sugere, pode haver outras maneiras mais naturais de estudar algo como a pergunta colocada. aqui está outra maneira um pouco semelhante de estudar o crescimento de uma linguagem regular com base no número de palavras de tamanho que tem alguma relação frouxa com a pergunta$n$

• Encontrar a taxa de crescimento de uma linguagem regular ou sem contexto em tempo polinomial (Gawrychowski, Krieger, Rampersad, Shallit)

  Dada uma linguagem L sem contexto, podemos testar se é de crescimento polinomial ou exponencial no tempo polinomial. Além disso, se for de crescimento polinomial, também podemos encontrar a ordem exata desse polinômio no tempo polinomial.