# 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, 2014 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?!? May 5, 2014 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, 2014 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. May 5, 2014 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). May 11, 2014 at 13:40

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:

• 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

• Although it is not explicitly stated there, the proof of the main result of the following paper implies that the class of p-regular languages is not contained in monotone NC^1. H. Gruber and J. Johannsen: "Optimal Lower Bounds on Regular Expression Size using Communication Complexity", FoSSaCS 2008, LNCS 4962, pp. 273-286. hermann-gruber.com/data/fossacs08.pdf May 10, 2014 at 19:17
• addendum, ran across this Phd thesis 2010 Complexity classes of finite automata / Kralovic that defines something similar to what is asked for p11 re "small languages". it seems a comprehensive survey of this overall area & builds up a general theoretical framework/abstractions of related concepts. however dont see many theorems directly relating to the specific class of "P-size DFA families".
– vzn
May 11, 2014 at 23:34
• @vzn: The definition in p11 of Kralovic's thesis is a bit different because it's about language families, whereas in my question the various languages are words of fixed length taken from only one main language. I'm not sure either of the connection with the Gruber and Holzer paper you give, I don't see how in my question you could think of the automata being the result of regularity-preserving operations in general. As for Gawrychowski et al, I agree it might be tangentially related.
– a3nm
May 13, 2014 at 14:22
• the Gruber/Holzer ref seems to help with the idea of P-regular reductions wrt "P-regular closure" type properties. agreed your def seems different than anything else studied. in other words there are presumably reductions between some of these problems/classes & the refs go in those directions & one might look for reduction-like-operations that connect your def to previously studied/published classes (agreed your defn does not imply any particular reduction operations). maybe the strict answer to your question is "no your class has not been studied exactly"
– vzn
May 13, 2014 at 15:01