7
$\begingroup$

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

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

$\endgroup$
18
  • 1
    $\begingroup$ Exactly what is your input, and what is your model of computation? $\endgroup$ Aug 24, 2011 at 7:49
  • $\begingroup$ 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. $\endgroup$
    – Aryeh
    Aug 24, 2011 at 8:12
  • $\begingroup$ 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$). $\endgroup$
    – Kaveh
    Aug 24, 2011 at 8:42
  • 3
    $\begingroup$ 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.) $\endgroup$
    – Kaveh
    Aug 24, 2011 at 9:28
  • 1
    $\begingroup$ 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! $\endgroup$
    – Aryeh
    Aug 24, 2011 at 9:33

3 Answers 3

6
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Janoma
    Aug 24, 2011 at 14:48
  • $\begingroup$ @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. $\endgroup$
    – dhruvbird
    Nov 1, 2013 at 3:35
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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". $\endgroup$
    – Aryeh
    Aug 24, 2011 at 10:28
  • $\begingroup$ 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. $\endgroup$ Aug 24, 2011 at 10:56
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Aug 24, 2011 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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