# Languages recognized by polynomial-size DFAs

For a fixed finite alphabet $\Sigma$, a formal language $L$ over $\Sigma$ is regular if there exists a deterministic finite automaton (DFA) over $\Sigma$ which accepts exactly $L$.

I am interested in languages that are "almost" regular in the sense that they can be recognized by automata families of size that grows only polynomially with the word length.

Formally, let me say that a formal language $L$ is recognized by a DFA family $(A_n)$ if for every word $w \in \Sigma^*$, letting $n = |w|$, $w$ is in $L$ iff $A_n$ accepts $w$ (no matter if the other $A_i$ accept it or not), and let me define p-regular languages as languages recognized by a PTIME-computable DFA family $(A_n)$ of polynomial size, namely, there is a polynomial $P$ such that $|A_n| \leq P(n)$ for all $n$. (This name, "p-regular", is something I made up, my question is to know if another name already exists for this. Note that this is not the same as p-regular languages in the sense of permutation automata.)

This class of p-regular languages includes of course regular languages (just take $A_n = A$ for all $n$, where $A$ is some DFA recognizing the regular language); but it is a strict superset of it: for instance, it is well-known that $\{a^n b^n \mid n \in \mathbb{N}\}$ is context-free but not regular, but it is p-regular ($A_n$ just has to count $n$ occurrences of $a$ and $n$ occurrences of $b$). However, because I require the automata to be polynomial-sized DFAs, some formal languages (actually some context-free languages) are not p-regular: for instance, the language of palindromes is not p-regular, because, intuitively, when you have read the first half of a word, you need to have as many different states as there are possible words, because you will need to match exactly this first half with the second.

So the class of p-regular languages is a strict superset of regular languages that is incomparable with context-free languages. In fact, it seems that you can even get a hierarchy of languages by distinguishing p-regular languages based on the smallest degree of the polynomial $P$ for which they are $P$-regular. It is not too hard to construct examples to show that this hierarchy is strict; though I do not understand well yet the interaction between this, and an alternative definition of the hierarchy which would also restrict the complexity of computing the $A_n$.

My question is: has this class that I call p-regular, and the associated hierarchy, been studied before? If yes, where and under which name?

(A possible link is with the field or streaming, or online algorithms. In the terminology of Streaming algorithms for language recognition problems, I am interested in the class (or hierarchy) of languages that can have a deterministic, one-pass recognition algorithms, using a polynomial number of states (so a logarithmic memory size), but I found no definition of this class in this paper or related papers. Note, however, that in my phrasing of the problem the length of the word is known in advance, which is less natural in a streaming context: in streaming you could see this as an infinite automaton, a special "end-of-word" symbol, and a constraint that the number of reachable states after reading $n$ characters is polynomial in $n$. I think that this distinction makes a difference, possible example: language of binary words whose value is divisible by their length, which is easy for a fixed length but (I conjecture) cannot be represented by an infinite automaton in the previous sense because no identifications can be made if the length is not known in advance.)

(The motivation for this p-regular class is that some problems, such as the probability of language membership for probabilistic words, seem to be PTIME not only when the language is regular, but also when it is p-regular, and I am trying to characterize exactly in which circumstances those problems are tractable.)

• Argh, I had not given proper thought to the question of the computability of the $(A_n)$. Thanks for pointing this out. I just added the requirement that they are computable. Hopefully there are no bad situations of p-regular languages which need to employ computable but high-complexity $(A_n)$ families? – a3nm May 5 '14 at 14:07
• Ok, I deleted the "uncomputable" comment. But even with the computable constraint you can still get weird things like: pick $A_n = \{ 1^n \mid n \in B \}$ and $B$ is NEXP-complete ($A_n = \emptyset$ otherwise). Perhaps you can restrict it further adding the constraint that the $A_n$ must be polynomial time computable?!? – Marzio De Biasi May 5 '14 at 14:11
• Marzio: Argh, you are right. For my motivation, the right notion is that the $A_n$ are PTIME-computable, yes, so I changed to this... still, it bothers me a bit that the complexity of computing the $(A_n)$ has such an influence on the resulting class (because it means that this is an additional choice that must be made in the definition...). This also complicates the picture of the hierarchy I was thinking of. – a3nm May 5 '14 at 14:18
• I don't see what is wrong with uncomputability, what you define is a non-uniform language class, like many circuit classes. – domotorp May 5 '14 at 17:28
• If you strengthen the uniformity condition to logspace, then all such languages will be computable in logspace. Under the definition as given, all p-regular languages are in “P-uniform L” (recognizable by a P-uniform family of branching programs, or by a logspace TM with a ptime-computable advice). – Emil Jeřábek May 11 '14 at 13:40

as AS suggests there may be other more natural ways to study something like the question posed. here is another somewhat similar way to study growth of a regular language based on number of words of size $n$ which does have some loose relation to the question eg