<p>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:</p>

<ul>
<li><p><a href="http://dl.acm.org/citation.cfm?id=1570741" rel="nofollow">Language operations with regular expressions of polynomial size</a> Gruber/Holzer</p>

<blockquote>
  <p>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.</p>
</blockquote></li>
</ul>

<p>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</p>

<ul>
<li><p><a href="http://www.ii.uni.wroc.pl/~gawry/growth_slides.pdf" rel="nofollow">Finding the growth rate of a regular or context-free language in polynomial time</a>
(Gawrychowski, Krieger, Rampersad, Shallit)</p>

<blockquote>
  <p>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.</p>
</blockquote></li>
</ul>

CC BY-SA 3.0
2014-05-10T19:17:18.413Z
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.
http://www.hermann-gruber.com/data/fossacs08.pdf
Hermann Gruber
CC BY-SA 3.0
2014-05-11T23:34:20.790Z
addendum, ran across this Phd thesis 2010 [Complexity classes of finite automata](http://foja.dcs.fmph.uniba.sk/materialy/RK.pdf) / 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
CC BY-SA 3.0
2014-05-13T14:22:02.650Z
@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.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-13T15:01:49.643Z
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
CC BY-SA 3.0
2014-05-07T04:27:15.800Z
2014-05-07T04:27:15.800Z
vzn
<p>For a fixed finite alphabet $\Sigma$, a formal language $L$ over $\Sigma$ is <em>regular</em> if there exists a <a href="https://en.wikipedia.org/wiki/Deterministic_finite_automaton" rel="nofollow">deterministic finite automaton</a> (DFA) over $\Sigma$ which accepts exactly $L$.</p>

<p>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.</p>

<p>Formally, let me say that a formal language $L$ is <em>recognized</em> by a DFA <em>family</em> $(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 <em>p-regular</em> languages as languages recognized by a <em>PTIME-computable</em> 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 <em>not</em> the same as p-regular languages in the sense of <a href="https://en.wikipedia.org/wiki/Permutation_automaton" rel="nofollow" title="permutation automata">permutation automata</a>.)</p>

<p>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 <em>DFAs</em>, some formal languages (actually some context-free languages) are <em>not</em> 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.</p>

<p>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$.</p>

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

<p>(A possible link is with the field or streaming, or online algorithms. In the terminology of <em><a href="http://repository.ias.ac.in/89492/1/3-a.pdf" rel="nofollow">Streaming algorithms for language recognition problems</a></em>, 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 <em>in advance</em>, 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.)</p>

<p>(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.)</p>

CC BY-SA 3.0
2014-05-05T14:07:10.427Z
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?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-05T14:11:21.460Z
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
CC BY-SA 3.0
2014-05-05T14:18:27.250Z
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.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-05T17:28:57.430Z
I don't see what is wrong with uncomputability, what you define is a non-uniform language class, like many circuit classes.
domotorp
CC BY-SA 3.0
2014-05-05T19:41:05.967Z
@domotorp: I only added a comment to note that with uncomputable $A_n$ you can get uncomputable p-regular languages; after the OP's edit and comment ("Hopefully there are no bad situations of p-regular languages...") I added a comment to underline that a p-regular language can grab some power from NEXP. I agree with you that all versions represent an interesting question.
Marzio De Biasi
CC BY-SA 3.0
2014-05-05T20:46:04.687Z
@domotorp: Yes, I think all alternative definitions make sense. The current phrasing is (I think) the right question given my underlying motivation, but if you find related work for any of the possible definitions it would probably interest me.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-06T12:51:15.673Z
Some of my work deals with the state complexity of such language families, see http://eccc.hpi-web.de/report/2012/183/ for an early version.  I am not aware of any prior work on "p-regular" families; these are definitely interesting.  I think the concept is more naturally defined by using a parameter, not necessarily instance size, to partition the language into regular slices.  For instance, in streaming a natural parameter is the cardinality of the set of values from which input elements are built.  Relative to such a parameter the issue about knowing the length in advance becomes moot.
András Salamon
CC BY-SA 3.0
2014-05-06T21:41:36.873Z
@AndrásSalamon: Thanks! your work seems related, but different, as it seems you are interested in the specific case where the streamed word represents a graph and the language concerns a certain property of this graph. (It doesn't seem to me that you would expect such languages being regular, even outside of the streaming context.) As for your parameter, I don't understand what you are saying: the set of values from which input elements are built is the alphabet? but knowing the size of the alphabet in advance is not helping you to know the length in advance? Could you explain this point more?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2014-05-07T10:42:56.317Z
From a streaming perspective, the alphabet often has structure.  For $k$-variable SAT, $k$ is perhaps a more interesting parameter than the instance size.  For $n$-vertex graphs, $n$ is often more useful than the size of the stream of edges.
András Salamon
CC BY-SA 3.0
2014-05-11T13:40:27.373Z
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
CC BY-SA 3.0
2015-06-20T23:03:27.190Z
This sounds a lot like circuit complexity. The DFA $A_n$ recognizes the finite set of strings that are both in $L$ and of length $n$. And, we care about how large $A_n$ is asymptotically. I've had a good bit of correspondence with András and I think the following is a better concept: a language $L$ is $fpt$-regular if there exists a polytime computable parameterization of $L$ into $\bigcup_{n\in\mathbb{N}} L_n$ such that each $L_n$ is regular and the state complexity of $L_n$ is polynomial in $n$.  This appears to be different from circuit complexity because the $L_n$'s could be infinite.
Michael Wehar
CC BY-SA 3.0
2015-06-20T23:06:40.613Z
I'm very happy that you asked this question, and I think there is a lot of work to potentially be done on this topic. What about parametermizing problems into context-free languages. There's a lot of interesting variations and directions to go in. I'm just speaking off the top of my head so feel free to correct me. Also, you might want to take a look at the following which is somewhat related: http://link.springer.com/chapter/10.1007%2F978-3-642-31623-4_2
Michael Wehar
CC BY-SA 3.0
2015-06-21T02:48:38.870Z
Note: the parameterization should be polynomial time computable and each string of length n is assigned a parameter that is at most n (or at most polynomial in n).
Michael Wehar
<reference-request><fl.formal-languages><automata-theory><online-algorithms><dfa>
Languages recognized by polynomial-size DFAs
Antoine Amarilli 'a3nm'
# Languages recognized by polynomial-size DFAs

(Asked by: username_0 on 2014-05-05)

For a fixed finite alphabet $\Sigma$, a formal language $L$ over $\Sigma$ is *regular* if there exists a [deterministic finite automaton](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Permutation_automaton "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](http://repository.ias.ac.in/89492/1/3-a.pdf)*, 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.)

**Tags:** reference-request, fl.formal-languages, automata-theory, online-algorithms, dfa
> **Comments:**
> **username_0**: 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?  
> **username_1**: 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?!?  
> **username_0**: 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.  
> **username_2**: I don't see what is wrong with uncomputability, what you define is a non-uniform language class, like many circuit classes.  
> **username_1**: @domotorp: I only added a comment to note that with uncomputable $A_n$ you can get uncomputable p-regular languages; after the OP's edit and comment ("Hopefully there are no bad situations of p-regular languages...") I added a comment to underline that a p-regular language can grab some power from NEXP. I agree with you that all versions represent an interesting question.  
> **username_0**: @domotorp: Yes, I think all alternative definitions make sense. The current phrasing is (I think) the right question given my underlying motivation, but if you find related work for any of the possible definitions it would probably interest me.  
> **username_3**: Some of my work deals with the state complexity of such language families, see http://eccc.hpi-web.de/report/2012/183/ for an early version.  I am not aware of any prior work on "p-regular" families; these are definitely interesting.  I think the concept is more naturally defined by using a parameter, not necessarily instance size, to partition the language into regular slices.  For instance, in streaming a natural parameter is the cardinality of the set of values from which input elements are built.  Relative to such a parameter the issue about knowing the length in advance becomes moot.  
> **username_0**: @AndrásSalamon: Thanks! your work seems related, but different, as it seems you are interested in the specific case where the streamed word represents a graph and the language concerns a certain property of this graph. (It doesn't seem to me that you would expect such languages being regular, even outside of the streaming context.) As for your parameter, I don't understand what you are saying: the set of values from which input elements are built is the alphabet? but knowing the size of the alphabet in advance is not helping you to know the length in advance? Could you explain this point more?  
> **username_3**: From a streaming perspective, the alphabet often has structure.  For $k$-variable SAT, $k$ is perhaps a more interesting parameter than the instance size.  For $n$-vertex graphs, $n$ is often more useful than the size of the stream of edges.  
> **username_4**: 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).  
> **username_5**: This sounds a lot like circuit complexity. The DFA $A_n$ recognizes the finite set of strings that are both in $L$ and of length $n$. And, we care about how large $A_n$ is asymptotically. I've had a good bit of correspondence with András and I think the following is a better concept: a language $L$ is $fpt$-regular if there exists a polytime computable parameterization of $L$ into $\bigcup_{n\in\mathbb{N}} L_n$ such that each $L_n$ is regular and the state complexity of $L_n$ is polynomial in $n$.  This appears to be different from circuit complexity because the $L_n$'s could be infinite.  
> **username_5**: I'm very happy that you asked this question, and I think there is a lot of work to potentially be done on this topic. What about parametermizing problems into context-free languages. There's a lot of interesting variations and directions to go in. I'm just speaking off the top of my head so feel free to correct me. Also, you might want to take a look at the following which is somewhat related: http://link.springer.com/chapter/10.1007%2F978-3-642-31623-4_2  
> **username_5**: Note: the parameterization should be polynomial time computable and each string of length n is assigned a parameter that is at most n (or at most polynomial in n).  

---

## 1 answers

### Answer by username_6 on 2014-05-07. Score: 3

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](http://dl.acm.org/citation.cfm?id=1570741) 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](http://www.ii.uni.wroc.pl/~gawry/growth_slides.pdf)
  (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.

> **Comments:**
> **username_7**: 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. http://www.hermann-gruber.com/data/fossacs08.pdf  
> **username_6**: addendum, ran across this Phd thesis 2010 [Complexity classes of finite automata](http://foja.dcs.fmph.uniba.sk/materialy/RK.pdf) / 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".  
> **username_0**: @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.  
> **username_6**: 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"_  

---

