Languages recognized by polynomial-size DFAs

Question

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.)

Answer 1

the question does not seem to have been studied much (one possibility is attempting to find a relationship with a "nearby" complexity class say P/poly etc); although here is at least one ref that touches on it:

• Language operations with regular expressions of polynomial size Gruber/Holzer

  This work deals with questions regarding to what extent regularity-preserving language operations affect the descriptional complexity of regular expressions. Some language operations are identified which are feasible for regular expressions in the sense that the result of the operation can be represented as a regular expression of size polynomial in that of the operands. We prove that taking language quotients, in particular the prefix and suffix closures, of a regular set can incur at most a quadratic blow-up on the required expression size. The circular shift operation can cause only a cubic increase in size and at least a quadratic bloat can be necessary in the worst case.

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

• Finding the growth rate of a regular or context-free language in polynomial time (Gawrychowski, Krieger, Rampersad, Shallit)

  Given a context-free language L, we can test whether it is of polynomial or exponential growth in polynomial time. Moreover, if it is of polynomial growth we can also find the exact order of this polynomial in polynomial time.