<p>Edited to add: I don't think this answer is on point, but I will leave it up.  Now community wiki so I don't get any more reputation for this.</p>

<p>The lower bound is not correct. Intuitively, this is because, to decide membership in $L$, I need to know the <em>description</em> of the DFA, but I may not need to run the DFA on the input if I am a Turing machine.</p>

<p>More formally, there is a Kolmogorov Complexity Characterization Theorem for Regular Languages. It states in part that the following are equivalent:</p>

<ol>
<li><p>$L$ is regular.</p></li>
<li><p>$C(\chi_1 \ldots \chi_n) \leq \log n + c_L$.</p></li>
</ol>

<p>Here, C is "simple" Kolmogorov Complexity, $\chi$ is the characteristic sequence of $L$, and $c_L$ is a constant depending only on $L$. Intuitively, this constant is the number of bits required to describe the minimal DFA for $L$, plus some overhead.</p>

<p>Finding such a minimum Turing program for $L$ might be hard.......</p>

<p>This is discussed in detail in Section 6.8 of Li and Vitanyi's book on Kolmogorov Complexity.</p>

CC BY-SA 3.0
2011-08-24T10:28:31.227Z
Thanks for the pointer, I'll read the book. But I still have a feeling we're arguing more about definitions than about essence. I've added edit2 to try to capture this "essence".
Aryeh
CC BY-SA 3.0
2011-08-24T10:56:48.297Z
Eh, I was about to delete this answer. I shouldn't post when I am just waking up. I will leave it up since you seemed to appreciate the pointer. I don't like my answer because it deals with program length, not runtime.
Aaron Sterling
CC BY-SA 3.0
2011-08-24T09:58:21.603Z
2011-08-24T15:44:38.020Z
2011-08-24T15:44:38.020Z
Aaron Sterling
<p>I am not 100% sure if this satisfies your condition for non-trivial, but here is a partial counter-example.</p>

<p>Take a decision problem $P$ which has a uniform circuit-complexity that is $O(n^{1 - \epsilon})$. For each $n$ consider the $L&#39;_n$ that accepts only those strings that are in $P$ and have length $n$. This $L&#39;_n$ probably has exponential size (if you pick $P$ carefully), however this is a language that accepts based on finite prefix; thus needs to be modified to achieve condition (c). Define $L_n = (L&#39;_n)^*$ (i.e map the initial state an accepting one, and map each accepting state to the initial state).</p>

<p>Given an input $(n,x)$ build the circuit $C_n$ run it on $n$-bit chunks of $x$.</p>

CC BY-SA 3.0
2011-08-24T14:43:15.500Z
whoops, I see another answer came in while I was writing this. I have to run right now, but will remove my answer when I get back if it is redundant.
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-24T14:42:20.443Z
2011-08-24T14:42:20.443Z
Artem Kaznatcheev
<p>I'll answer my own question -- the conjectured lower bound is false. Consider 
$L_n=\Sigma^* 0 \Sigma^n$ (that is, the collection of all strings with a $0$ in the $n$th location from the end). It's easy to see that there is an $O(n)$ size NFA for $L_n$, but the minimal DFA for $L_n$ is exponential. Here is a TM that decides membership in $L_n$ in time $O(|x|+n)$: scan $x$ to the end (time $|x|$) and read $n$ steps back to see if that letter is $0$.</p>

CC BY-SA 3.0
2011-08-24T14:48:56.650Z
Yep. The classical (counter)example to show that going from NFA to DFA cannot always be efficient. But, to use your words, I would say that running this Turing machine is indeed the same as running the DFA _implicitly_, but not the same as _running the DFA_.
Janoma
CC BY-SA 3.0
2013-11-01T03:35:19.723Z
@Aryeh I didn't quite get your answer. Please could you elaborate? I thought you mentioned in the question that "Suppose I know that the minimal DFA for L has N states.", hence I am assuming that small n (n) and capital n (N) are distinct.
dhruvbird
CC BY-SA 3.0
2011-08-24T14:41:13.610Z
2011-08-24T14:41:13.610Z
Aryeh
<p>Suppose I have a regular language $L$, and I would like to lower-bound the complexity of deciding membership in $L$. Suppose I know that the minimal DFA for $L$ has $N$ states.</p>

<p>I would like to claim that determining the membership of a string of length $n$ in $L$ requires time $\Omega(n\log N)$. The dependence on $n$ is obvious -- I have to read the whole string, in general, to know if it belongs to a language. The $\log N$ factor is because to know what state I am in I need to write it down, and this takes time $\log N$.</p>

<p>This requires arguing that there is no faster way to determine membership in $L$ than to run its minimal DFA (implicitly or explicitly). I think such an argument can be formalized (via equivalence classes, for example), but perhaps I am being naive.</p>

<p>Question: Is the $\Omega(n\log N)$ lower bound correct?</p>

<p>Edit: let me make this more formal. Is there an infinite family of distinct minimal DFAs $A_1, A_2,..$ such that some algorithm simulating the $\{A_i\}$ on a deterministic RAM machine can determine membership of $x$ in $L(A_i)$ in time $o(|x|\log|A_i|)$, where $|x|$ is string length and $|A_i|$ is the number of states?</p>

<p>Edit2: Kaveh's and Aaron's answers seem to indicate that my lower bound is false. But I would love to see a non-trivial counter example. Suppose:
(a) I have a family of regular languages $\{L_n\}$
(b) each $L_n$ has a compact description (say, as an NFA) of size $poly(n)$, but the minimal DFA for $L_n$ has size $2^n$
(c) for each $n$, there is no fixed-length prefix that determines membership in $L_n$ (this rules out Kaveh's examples -- you really do need to read the whole string)</p>

<p>Can somebody give an example of a family $L_n$ satisfying (a,b,c) for which there is a TM taking $n$ and $x\in\Sigma^*$ as inputs and deciding $x\in?L_n$ in time $o(n|x|)$?
[Note that we've switched from RAM to TM as the computational model; $n$ is given in binary.]</p>

CC BY-SA 3.0
2011-08-24T07:49:30.130Z
Exactly what is your input, and what is your model of computation?
Jukka Suomela
CC BY-SA 3.0
2011-08-24T08:12:21.433Z
The input is a string (sequence of letters), and model of computation is a RAM machine. Of course, in degenerate cases (such as when membership in $L$ is determined by the 1st letter), we don't need to read the whole string -- but in general, we obviously do. I'll edit the question to make it more formal.
Aryeh
CC BY-SA 3.0
2011-08-24T08:42:54.193Z
I think you are not expressing what you have in mind correctly, take $A_i$s to be one state machine that accepts everything, membership in $L(A_i)$ is decidable in constant time. You want a sequence of atuomata which is hard not easy so you should say it is not decidable in $O(|x|\log |A_i|)$. Also you need to use uniform version (i.e. the automaton should be part of the input), otherwise you will ran into problems with non-uniformity (let $A_i$ accepts 0 iff $i\in K$).
Kaveh
CC BY-SA 3.0
2011-08-24T08:47:46.073Z
So I think what you want to ask is: Is there a machine that given a pair $(x,A)$ decides membership of $x$ in $L(A)$ in time $o(|x|\log |A|)$? The answer is no, since you need to read $A$.
Kaveh
CC BY-SA 3.0
2011-08-24T08:51:08.377Z
Kaveh, I meant for the $A_i$'s to be distinct, so your example of taking them all to be the same trivial automaton doesn't work.
Aryeh
CC BY-SA 3.0
2011-08-24T08:53:18.607Z
I think requiring the DFAs to be distinct also gets around the problem of non-uniformity you raise.
Aryeh
CC BY-SA 3.0
2011-08-24T09:00:40.263Z
No, it doesn't. You can add dummy states (and if you forbid them I will found some other way, the problem is more fundamental).
Kaveh
CC BY-SA 3.0
2011-08-24T09:09:17.237Z
I specifically stipulated that the automata be minimal, which precludes adding dummy states. Please elaborate.
Aryeh
CC BY-SA 3.0
2011-08-24T09:28:15.053Z
Let $A_i$ only accept $0^{i}$. The minimal DFA has size $i$, the problem can be solved in $O(\min\{|x|,\log i\})$. (ps: I personally don't see what you are trying to do, may be you should explain it a little bit more in the question.)
Kaveh
CC BY-SA 3.0
2011-08-24T09:32:50.913Z
OK, you have me there. What if I required each language $L(A_i)$ not to be finite or co-finite?
Aryeh
CC BY-SA 3.0
2011-08-24T09:33:19.913Z
The point is that I have a *specific* family of DFAs in mind and would like to argue a lower bound on the decision problem!
Aryeh
CC BY-SA 3.0
2011-08-24T09:34:34.200Z
That won't solve the problem, since you can use $0^i\Sigma^*$ in place of $0^i$. I see two problems with your question: 1. you are asking for existence of an easy sequence, that won't help with proving difficulty of your case even if no one comes up with some sequence that would satisfy the conditions, whatever they are. 2. You should give the minimal DFA $A$ to the machine somehow. On the other hand, if the sequence of DFAs you are interested in is easy to state that might be the way to go, i.e. include that in the question ask that given $x$ and $i$ decide membership $x$ in $A_i$.
Kaveh
CC BY-SA 3.0
2011-08-24T09:46:40.750Z
So your $0^i$ example exploits the $O(1)$ complexity of bit addition on RAM machines. What if I changed the computational model from RAM machines to TMs?
Aryeh
CC BY-SA 3.0
2011-08-24T09:53:03.687Z
I think my confusion arises from a loose definition of RAM machines. Suppose my sequence of minimial DFAs, $A_i$ is such that $|A_i|=2^i$, but I can encode $A_i$ as input of length $poly(i)$. Can a RAM/Turing machine decide membership in $L(A_i)$ in time $o(|x|i)$?
Aryeh
CC BY-SA 3.0
2011-08-24T10:47:19.590Z
Are you looking for a *uniform* procedure for all regular languages? In any case, you should fix you model of computation; TM and RM are *not* equivalent wrt runtimes.
Raphael
CC BY-SA 3.0
2011-08-24T11:44:10.073Z
As the edited question states, I am interested in a specific family with the stated properties (and yes, I've switched from RM to TM)
Aryeh
CC BY-SA 3.0
2011-08-24T13:20:26.517Z
You're misunderstanding, since $n$ is now a part of the input.
Aryeh
CC BY-SA 3.0
2011-08-24T20:06:22.143Z
You can also use *succinct* inputs for $A_i$  if they are large but easy to describe. Alternatively you can give the description of $A_i$ as an oracle.
Kaveh
<fl.formal-languages><automata-theory><time-complexity><regular-language><dfa>
Complexity lower bound for regular languages
Aryeh
# Complexity lower bound for regular languages

(Asked by: username_0 on 2011-08-24)

Suppose I have a regular language $L$, and I would like to lower-bound the complexity of deciding membership in $L$. Suppose I know that the minimal DFA for $L$ has $N$ states.

I would like to claim that determining the membership of a string of length $n$ in $L$ requires time $\Omega(n\log N)$. The dependence on $n$ is obvious -- I have to read the whole string, in general, to know if it belongs to a language. The $\log N$ factor is because to know what state I am in I need to write it down, and this takes time $\log N$.

This requires arguing that there is no faster way to determine membership in $L$ than to run its minimal DFA (implicitly or explicitly). I think such an argument can be formalized (via equivalence classes, for example), but perhaps I am being naive.

Question: Is the $\Omega(n\log N)$ lower bound correct?

Edit: let me make this more formal. Is there an infinite family of distinct minimal DFAs $A\_1, A\_2,..$ such that some algorithm simulating the $\{A\_i\}$ on a deterministic RAM machine can determine membership of $x$ in $L(A\_i)$ in time $o(|x|\log|A\_i|)$, where $|x|$ is string length and $|A\_i|$ is the number of states?

Edit2: username_2's and Aaron's answers seem to indicate that my lower bound is false. But I would love to see a non-trivial counter example. Suppose:
(a) I have a family of regular languages $\{L\_n\}$
(b) each $L\_n$ has a compact description (say, as an NFA) of size $poly(n)$, but the minimal DFA for $L\_n$ has size $2^n$
(c) for each $n$, there is no fixed-length prefix that determines membership in $L\_n$ (this rules out username_2's examples -- you really do need to read the whole string)

Can somebody give an example of a family $L\_n$ satisfying (a,b,c) for which there is a TM taking $n$ and $x\in\Sigma^\*$ as inputs and deciding $x\in?L\_n$ in time $o(n|x|)$?
[Note that we've switched from RAM to TM as the computational model; $n$ is given in binary.]

**Tags:** fl.formal-languages, automata-theory, time-complexity, regular-language, dfa

> **Comments:**
> **username_1**: Exactly what is your input, and what is your model of computation?  
> **username_0**: The input is a string (sequence of letters), and model of computation is a RAM machine. Of course, in degenerate cases (such as when membership in $L$ is determined by the 1st letter), we don't need to read the whole string -- but in general, we obviously do. I'll edit the question to make it more formal.  
> **username_2**: I think you are not expressing what you have in mind correctly, take $A_i$s to be one state machine that accepts everything, membership in $L(A_i)$ is decidable in constant time. You want a sequence of atuomata which is hard not easy so you should say it is not decidable in $O(|x|\log |A_i|)$. Also you need to use uniform version (i.e. the automaton should be part of the input), otherwise you will ran into problems with non-uniformity (let $A_i$ accepts 0 iff $i\in K$).  
> **username_2**: So I think what you want to ask is: Is there a machine that given a pair $(x,A)$ decides membership of $x$ in $L(A)$ in time $o(|x|\log |A|)$? The answer is no, since you need to read $A$.  
> **username_0**: username_2, I meant for the $A_i$'s to be distinct, so your example of taking them all to be the same trivial automaton doesn't work.  
> **username_0**: I think requiring the DFAs to be distinct also gets around the problem of non-uniformity you raise.  
> **username_2**: No, it doesn't. You can add dummy states (and if you forbid them I will found some other way, the problem is more fundamental).  
> **username_0**: I specifically stipulated that the automata be minimal, which precludes adding dummy states. Please elaborate.  
> **username_2**: Let $A_i$ only accept $0^{i}$. The minimal DFA has size $i$, the problem can be solved in $O(\min\{|x|,\log i\})$. (ps: I personally don't see what you are trying to do, may be you should explain it a little bit more in the question.)  
> **username_0**: OK, you have me there. What if I required each language $L(A_i)$ not to be finite or co-finite?  
> **username_0**: The point is that I have a *specific* family of DFAs in mind and would like to argue a lower bound on the decision problem!  
> **username_2**: That won't solve the problem, since you can use $0^i\Sigma^*$ in place of $0^i$. I see two problems with your question: 1. you are asking for existence of an easy sequence, that won't help with proving difficulty of your case even if no one comes up with some sequence that would satisfy the conditions, whatever they are. 2. You should give the minimal DFA $A$ to the machine somehow. On the other hand, if the sequence of DFAs you are interested in is easy to state that might be the way to go, i.e. include that in the question ask that given $x$ and $i$ decide membership $x$ in $A_i$.  
> **username_0**: So your $0^i$ example exploits the $O(1)$ complexity of bit addition on RAM machines. What if I changed the computational model from RAM machines to TMs?  
> **username_0**: I think my confusion arises from a loose definition of RAM machines. Suppose my sequence of minimial DFAs, $A_i$ is such that $|A_i|=2^i$, but I can encode $A_i$ as input of length $poly(i)$. Can a RAM/Turing machine decide membership in $L(A_i)$ in time $o(|x|i)$?  
> **username_3**: Are you looking for a *uniform* procedure for all regular languages? In any case, you should fix you model of computation; TM and RM are *not* equivalent wrt runtimes.  
> **username_0**: As the edited question states, I am interested in a specific family with the stated properties (and yes, I've switched from RM to TM)  
> **username_0**: You're misunderstanding, since $n$ is now a part of the input.  
> **username_2**: You can also use *succinct* inputs for $A_i$  if they are large but easy to describe. Alternatively you can give the description of $A_i$ as an oracle.  

---

## 3 answers

### Answer by username_0 on 2011-08-24. Score: 6 | Accepted answer

I'll answer my own question -- the conjectured lower bound is false. Consider
$L\_n=\Sigma^\* 0 \Sigma^n$ (that is, the collection of all strings with a $0$ in the $n$th location from the end). It's easy to see that there is an $O(n)$ size NFA for $L\_n$, but the minimal DFA for $L\_n$ is exponential. Here is a TM that decides membership in $L\_n$ in time $O(|x|+n)$: scan $x$ to the end (time $|x|$) and read $n$ steps back to see if that letter is $0$.

> **Comments:**
> **username_6**: Yep. The classical (counter)example to show that going from NFA to DFA cannot always be efficient. But, to use your words, I would say that running this Turing machine is indeed the same as running the DFA _implicitly_, but not the same as _running the DFA_.  
> **username_7**: @username_0 I didn't quite get your answer. Please could you elaborate? I thought you mentioned in the question that "Suppose I know that the minimal DFA for L has N states.", hence I am assuming that small n (n) and capital n (N) are distinct.  

---

### Answer by username_4 on 2011-08-24. Score: 4

Edited to add: I don't think this answer is on point, but I will leave it up. Now community wiki so I don't get any more reputation for this.

The lower bound is not correct. Intuitively, this is because, to decide membership in $L$, I need to know the *description* of the DFA, but I may not need to run the DFA on the input if I am a Turing machine.

More formally, there is a Kolmogorov Complexity Characterization Theorem for Regular Languages. It states in part that the following are equivalent:

1. $L$ is regular.
2. $C(\chi\_1 \ldots \chi\_n) \leq \log n + c\_L$.

Here, C is "simple" Kolmogorov Complexity, $\chi$ is the characteristic sequence of $L$, and $c\_L$ is a constant depending only on $L$. Intuitively, this constant is the number of bits required to describe the minimal DFA for $L$, plus some overhead.

Finding such a minimum Turing program for $L$ might be hard.......

This is discussed in detail in Section 6.8 of Li and Vitanyi's book on Kolmogorov Complexity.

> **Comments:**
> **username_0**: Thanks for the pointer, I'll read the book. But I still have a feeling we're arguing more about definitions than about essence. I've added edit2 to try to capture this "essence".  
> **username_4**: Eh, I was about to delete this answer. I shouldn't post when I am just waking up. I will leave it up since you seemed to appreciate the pointer. I don't like my answer because it deals with program length, not runtime.  

---

### Answer by username_5 on 2011-08-24. Score: 0

I am not 100% sure if this satisfies your condition for non-trivial, but here is a partial counter-example.

Take a decision problem $P$ which has a uniform circuit-complexity that is $O(n^{1 - \epsilon})$. For each $n$ consider the $L'\_n$ that accepts only those strings that are in $P$ and have length $n$. This $L'\_n$ probably has exponential size (if you pick $P$ carefully), however this is a language that accepts based on finite prefix; thus needs to be modified to achieve condition (c). Define $L\_n = (L'\_n)^\*$ (i.e map the initial state an accepting one, and map each accepting state to the initial state).

Given an input $(n,x)$ build the circuit $C\_n$ run it on $n$-bit chunks of $x$.

> **Comments:**
> **username_5**: whoops, I see another answer came in while I was writing this. I have to run right now, but will remove my answer when I get back if it is redundant.  

---

