Langues reconnues par les DFA de taille polynomiale

Pour un alphabet fini fixe , un langage formel sur est régulier s'il existe un automate fini déterministe (DFA) sur qui accepte exactement .L $\Sigma$$L$$\Sigma$$\Sigma$$L$

Je m'intéresse aux langues qui sont "presque" régulières dans le sens où elles peuvent être reconnues par des familles d'automates de taille qui ne croissent que de façon polynomiale avec la longueur du mot.

Formellement, permettez-moi de dire qu'un langage formel est reconnu par une famille DFA si pour chaque mot , laissant, est dans si accepte (peu importe si les autres acceptent ou non), et permettez-moi de définir les langues p-régulières comme des langues reconnues par une famille DFA calculable de taille polynomiale, à savoir, là est un polynôme tel que pour tout$L$ w ∈ Σ ∗ n = | w | w L A n w A $(A_n)$$w \in \Sigma^*$$n = |w|$$w$$L$$A_n$$w$$A_i$P | A n | ≤ P ( n ) $(A_n)$$P$$|A_n| \leq P(n)$$n$. (Ce nom, "p-regular", est quelque chose que j'ai inventé, ma question est de savoir si un autre nom existe déjà pour cela. Notez que ce n'est pas la même chose que les langages p-regular au sens d' automates de permutation .)

Cette classe de langues p-régulières comprend bien sûr les langues régulières (il suffit de prendre pour tout , où est un DFA reconnaissant la langue régulière); mais c'est un sur-ensemble strict: par exemple, il est bien connu que est hors contexte mais pas régulier, mais c'est p- régulier ( doit juste compter occurrences de et occurrences de ). Cependant, comme j'exige que les automates soient des DFA de taille polynomiale , certains langages formels (en fait certains langages sans contexte) ne sont pasn 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: par exemple, la langue des palindromes n'est pas p-regular, car, intuitivement, lorsque vous avez lu la première moitié d'un mot, vous devez avoir autant d'états différents qu'il y a de mots possibles, car vous aurez besoin pour correspondre exactement à cette première moitié avec la seconde.

Ainsi, la classe des langues p-régulières est un sur-ensemble strict de langues régulières qui est incomparable avec les langues sans contexte. En fait, il semble que l'on puisse même obtenir une hiérarchie de langues en distinguant les langues p-régulières en fonction du plus petit degré du polynôme pour lequel elles sont régulières. Il n'est pas trop difficile de construire des exemples pour montrer que cette hiérarchie est stricte; bien que je ne comprenne pas encore bien l'interaction entre cela, et une définition alternative de la hiérarchie qui limiterait également la complexité du calcul de l' .P A $P$$P$$A_n$

Ma question est: cette classe que j'appelle p-regular, et la hiérarchie associée, a-t-elle été étudiée auparavant? Si oui, où et sous quel nom?

(Un lien possible est avec le champ ou le streaming, ou les algorithmes en ligne. Dans la terminologie des algorithmes de streaming pour les problèmes de reconnaissance de langue , je suis intéressé par la classe (ou la hiérarchie) des langues qui peuvent avoir des algorithmes de reconnaissance déterministes en une passe, en utilisant un nombre polynomial d'états (donc une taille de mémoire logarithmique), mais je n'ai trouvé aucune définition de cette classe dans cet article ou dans des articles connexes. Notez, cependant, que dans ma formulation du problème, la longueur du mot est connue à l'avance , ce qui est moins naturel dans un contexte de streaming: en streaming, vous pouvez voir cela comme un automate infini, un symbole spécial de "fin de mot" et une contrainte que le nombre d'états accessibles après la lecture de caractères est polynomial en$n$$n$. Je pense que cette distinction fait une différence, exemple possible: langage de mots binaires dont la valeur est divisible par leur longueur, ce qui est facile pour une longueur fixe mais (je suppose) ne peut pas être représenté par un automate infini dans le sens précédent car pas d'identifications peut être faite si la longueur n'est pas connue à l'avance.)

(La motivation de cette classe p-régulière est que certains problèmes, tels que la probabilité d'appartenance à une langue pour les mots probabilistes, semblent être PTIME non seulement lorsque la langue est régulière, mais aussi quand elle est p-régulière, et j'essaie pour caractériser exactement dans quelles circonstances ces problèmes sont traitables.)

la question ne semble pas avoir été beaucoup étudiée (une possibilité est d'essayer de trouver une relation avec une classe de complexité "proche" disons P / poly, etc.); bien que voici au moins une référence qui la touche:

• Opérations langagières avec expressions régulières de taille polynomiale Gruber / Holzer

  Ce travail traite des questions concernant la mesure dans laquelle les opérations de langage préservant la régularité affectent la complexité descriptive des expressions régulières. Certaines opérations de langage sont identifiées qui sont réalisables pour les expressions régulières dans le sens où le résultat de l'opération peut être représenté comme une expression régulière de polynôme de taille dans celle des opérandes. Nous prouvons que la prise de quotients de langue, en particulier les fermetures de préfixe et de suffixe, d'un ensemble régulier peut entraîner au maximum une explosion quadratique sur la taille d'expression requise. L'opération de décalage circulaire ne peut entraîner qu'une augmentation cubique de la taille et au moins un ballonnement quadratique peut être nécessaire dans le pire des cas.

comme AS le suggère, il peut y avoir d'autres façons plus naturelles d'étudier quelque chose comme la question posée. voici une autre façon quelque peu similaire d'étudier la croissance d'une langue régulière basée sur le nombre de mots de taille qui a une certaine relation lâche avec la question par exemple$n$

• Trouver le taux de croissance d'une langue régulière ou sans contexte en temps polynomial (Gawrychowski, Krieger, Rampersad, Shallit)

  Étant donné un langage sans contexte L, nous pouvons tester s'il s'agit d'une croissance polynomiale ou exponentielle en temps polynomial. De plus, s'il s'agit d'une croissance polynomiale, nous pouvons également trouver l'ordre exact de ce polynôme en temps polynomial.