6
$\begingroup$

Consider a kind of automata similar to common DFAs or NFAs where it is possible to represent succinctly linear chains of states. In other words, an automaton like this:

DFA with a chain of states

could be represented in this way:

enter image description here

where the thick edge represent the chain of states, where each state is connected to the next by a single edge and all the edges are labeled in the same way, in this case by $a$.

So this is not really a counter or anything fancy, it is just a succinct representation of a very limited special case. By succinct, I mean that by representing the $k$ parameter in binary, the second automaton can be represented in logarithmically less space than the first. Let's call this kind of automata the "succinct automata", SA, so say DSA and NSA for short for the deterministic and nondeterministic variants.

Now, my question concerns the complexity of boolean operations over this kind of automata.

In details:

  1. Given two NSAs $\mathcal{A}$ and $\mathcal{B}$, is it possible to build the NSAs for $\mathcal{L}(\mathcal{A})\cup\mathcal{L}(\mathcal{B})$ and $\mathcal{L}(\mathcal{A})\cap\mathcal{L}(\mathcal{B})$, of size still polynomial in the size of $\mathcal{A}$ and $\mathcal{B}$ (i.e. without paying for the unrolling of the chains before computing the results)?

  2. Is it possible to compute those operations on DSAs (deterministic) guaranteeing that the resulting automata stay deterministic (and still polynomial size)?

  3. Is it possible to determinize an NSA with only a singly-exponential blowup (i.e. without paying for the unrolling of the chains before paying for the classic determinization)?

My feeling on all of these after having though about it a bit is that an exponential increase in size is needed in most of the cases, or that the results must be nondeterministic.

So the question is really: is anybody aware of a place where this kind of problems have been addressed? Has this variant of finite automata being studied before?

$\endgroup$
  • $\begingroup$ In your example, the succinct automaton seems to have a self loop, which would allow infinitely many words, whereas the original automaton only allows a single word. Thus, you should probably have the parameter on the transitions, and connect them between states (so in your example, instead of a loop just have a transition). $\endgroup$ – Shaull Oct 27 '16 at 15:24
  • $\begingroup$ I'm with @Shaull here: the definition does not seem entirely clear. Do you basically mean that transitions may be labeled by words? $\endgroup$ – Michaël Cadilhac Oct 27 '16 at 15:31
  • $\begingroup$ @MichaëlCadilhac - I think it's more than just words, because you're allowed to specify numbers in binary. That is, an automaton that accepts (only) the word $a^{k}$ would require $\log k$ size. But the definition should indeed be clearer. $\endgroup$ – Shaull Oct 27 '16 at 15:34
  • $\begingroup$ @Shaull you're right that the self loop was misleading. I've edited the question and the figures. To clarify, the special "syntax" here is just a way to compactly represent the chain. I don't need to support arbitrary words or anything complex. Just the repetition of the same labeling. Please let me know if I can clarify further. $\endgroup$ – gigabytes Oct 27 '16 at 15:38
  • $\begingroup$ @MichaëlCadilhac I've clarified the definition, I hope. $\endgroup$ – gigabytes Oct 27 '16 at 15:40
5
$\begingroup$

This is a very partial answer, but I have some ideas:

  1. Clearly the union of NSAs can be taken without any blowup - just use the nondeterministic union of the initial states.

  2. As for determinization, you'll have a double-exponential blowup. Consider the language $L_k=(a+b)^*a(a+b)^k$. That is, the $k$-th before last letter is $a$. You can easily construct an NSA of size $O(\log k)$ for it, but any DSA would need to "remember" the last $k-1$ letters (the same argument that works for DFAs would work here). So a DSA would need $2^{k-1}$ states, which is a double exponential blowup.

  3. As for union of DSAs, this is more of a conjecture: consider the language $L_p=(a^p)^*$ for a prime number $p$. This can be recognized by a DSA with 2 states and $p-1$ written on one of the transitions. Now, consider the union $L_p\cup L_q$ for $p\neq q$. It seems to me that you'll need a lot of states (i.e. $p\cdot q$) in order to recognize this with a DSA. But I haven't thought this through completely.

$\endgroup$
  • $\begingroup$ The second point assumes that you can represent succinctly $(a+b)^k$, but the definition of the model seems to allow only single letters to be iterated. $\endgroup$ – Denis Oct 27 '16 at 16:18
  • $\begingroup$ @Denis - right, I was thinking of regular expressions with binary exponent, essentially. Perhaps the OP can clarify if this is allowed, if not - I'll remove it. $\endgroup$ – Shaull Oct 27 '16 at 18:20
  • $\begingroup$ @Denis actually any label is allowed in the edges. The single letter was only a matter of the example. I'll edit. $\endgroup$ – gigabytes Oct 27 '16 at 18:28
  • $\begingroup$ @Shaull In the last sentence of point two you meant "So a DSA would need...", right? $\endgroup$ – gigabytes Oct 27 '16 at 18:29
  • $\begingroup$ @Shaull anyway you're right for point 2. Good point! $\endgroup$ – gigabytes Oct 27 '16 at 18:33
3
$\begingroup$

A model that seems somewhat relevant is capacitated automata: http://www.cs.huji.ac.il/~ornak/publications/fsttcs14b.pdf

$\endgroup$

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.