7
$\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?

Improve this question
$\endgroup$
8
  • $\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
    Commented Oct 27, 2016 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
    Commented Oct 27, 2016 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
    Commented Oct 27, 2016 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$
    – Nicola Gigante
    Commented Oct 27, 2016 at 15:38
  • $\begingroup$ @MichaëlCadilhac I've clarified the definition, I hope. $\endgroup$
    – Nicola Gigante
    Commented Oct 27, 2016 at 15:40

2 Answers 2

Reset to default
6
$\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.

Improve this answer
$\endgroup$
8
  • $\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
    Commented Oct 27, 2016 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
    Commented Oct 27, 2016 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$
    – Nicola Gigante
    Commented Oct 27, 2016 at 18:28
  • $\begingroup$ @Shaull In the last sentence of point two you meant "So a DSA would need...", right? $\endgroup$
    – Nicola Gigante
    Commented Oct 27, 2016 at 18:29
  • $\begingroup$ @Shaull anyway you're right for point 2. Good point! $\endgroup$
    – Nicola Gigante
    Commented Oct 27, 2016 at 18:33
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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