23
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – a3nm May 5 '14 at 14:07
  • 1
    $\begingroup$ 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?!? $\endgroup$ – Marzio De Biasi May 5 '14 at 14:11
  • 1
    $\begingroup$ 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. $\endgroup$ – a3nm May 5 '14 at 14:18
  • 2
    $\begingroup$ I don't see what is wrong with uncomputability, what you define is a non-uniform language class, like many circuit classes. $\endgroup$ – domotorp May 5 '14 at 17:28
  • 3
    $\begingroup$ 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). $\endgroup$ – Emil Jeřábek May 11 '14 at 13:40
3
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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 $\endgroup$ – Hermann Gruber May 10 '14 at 19:17
  • 1
    $\begingroup$ 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". $\endgroup$ – vzn May 11 '14 at 23:34
  • 1
    $\begingroup$ @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. $\endgroup$ – a3nm May 13 '14 at 14:22
  • 2
    $\begingroup$ 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" $\endgroup$ – vzn May 13 '14 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.