<p>A model that seems somewhat relevant is capacitated automata:
<a href="http://www.cs.huji.ac.il/~ornak/publications/fsttcs14b.pdf" rel="nofollow">http://www.cs.huji.ac.il/~ornak/publications/fsttcs14b.pdf</a></p>

CC BY-SA 3.0
2016-10-27T19:15:55.813Z
2016-10-27T19:15:55.813Z
Guy
<p>This is a very partial answer, but I have some ideas:</p>

<ol>
<li><p>Clearly the <strong>union of NSAs</strong> can be taken without any blowup - just use the nondeterministic union of the initial states.</p></li>
<li><p>As for <strong>determinization</strong>, 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.</p></li>
<li><p>As for <strong>union of DSAs</strong>, 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.</p></li>
</ol>

CC BY-SA 3.0
2016-10-27T16:18:56.677Z
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.
Denis
CC BY-SA 3.0
2016-10-27T18:20:11.760Z
@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.
Shaull
CC BY-SA 3.0
2016-10-27T18:28:35.427Z
@Denis actually any label is allowed in the edges. The single letter was only a matter of the example. I'll edit.
Nicola Gigante
CC BY-SA 3.0
2016-10-27T18:29:16.847Z
@Shaull In the last sentence of point two you meant "So a *DSA* would need...", right?
Nicola Gigante
CC BY-SA 3.0
2016-10-27T18:33:04.700Z
@Shaull anyway you're right for point 2. Good point!
Nicola Gigante
CC BY-SA 3.0
2016-10-27T18:43:11.713Z
@gigabytes - of course, DSA. I edited the answer.
Shaull
CC BY-SA 3.0
2016-10-28T08:18:36.617Z
It took me a while to realize that your 2 is the 3rd question, and your 3 is the 2nd question, maybe you should mention this.
domotorp
CC BY-SA 3.0
2016-10-28T08:22:30.347Z
@domotorp - I emphasized the property of each article.
Shaull
CC BY-SA 3.0
2016-10-27T15:56:31.440Z
2016-10-28T08:21:45.020Z
2016-10-28T08:21:45.020Z
Shaull
<p>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:</p>

<p><a href="https://i.sstatic.net/pnZ0l.png" rel="noreferrer"><img src="https://i.sstatic.net/pnZ0l.png" alt="DFA with a chain of states"></a></p>

<p>could be represented in this way:</p>

<p><a href="https://i.sstatic.net/QZ1om.png" rel="noreferrer"><img src="https://i.sstatic.net/QZ1om.png" alt="enter image description here"></a></p>

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

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

<p>Now, my question concerns the complexity of boolean operations over this kind of automata. </p>

<p>In details:</p>

<ol>
<li><p>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 <strong>polynomial</strong> in the size of $\mathcal{A}$ and $\mathcal{B}$ (i.e. without paying for the unrolling of the chains before computing the results)?</p></li>
<li><p>Is it possible to compute those operations on DSAs (deterministic) guaranteeing that the resulting automata stay <strong>deterministic</strong> (and still polynomial size)?</p></li>
<li><p>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)?</p></li>
</ol>

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

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

CC BY-SA 3.0
2016-10-27T15:24:59.203Z
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).
Shaull
CC BY-SA 3.0
2016-10-27T15:31:45.940Z
I'm with @Shaull here: the definition does not seem entirely clear.  Do you basically mean that transitions may be labeled by words?
Michaël Cadilhac
CC BY-SA 3.0
2016-10-27T15:34:49.143Z
@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.
Shaull
CC BY-SA 3.0
2016-10-27T15:38:44.597Z
@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.
Nicola Gigante
CC BY-SA 3.0
2016-10-27T15:40:56.763Z
@MichaëlCadilhac I've clarified the definition, I hope.
Nicola Gigante
CC BY-SA 3.0
2016-10-27T15:55:39.770Z
Thanks.  For your question 1, union is trivial, since you can just branch out on $\mathcal{A}$ and $\mathcal{B}$, right?  For question 2, it certainly is possible to compute a deterministic automaton, the challenge really is to keep the size tame.  For question 3, did you try making a variant of the usual NFA that explodes? Like, "the word has a string of $k$ letters $a$ that are $n$ letters before the end"?
Michaël Cadilhac
CC BY-SA 3.0
2016-10-27T18:26:07.787Z
@MichaëlCadilhac yes, you're right. Question 1 is just a warmup to state question 2 that is the real problem. Obtaining determinism *or* succinctness is easy, whereas how to obtain both is not so obvious to me.
Nicola Gigante
CC BY-SA 3.0
2016-10-28T08:28:39.080Z
Can the hidden states be accepting? If yes, then the size of DSA's stays the same under complement, if not, then $\{a^n \mid n\equiv 0 (mod m)\}$ shows they might have an exponential growth.
domotorp
<reference-request><automata-theory><dfa><nfa>
Finite Automata with succinct representation of chains of states
Nicola Gigante
# Finite Automata with succinct representation of chains of states

(Asked by: username_0 on 2016-10-27)

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](https://i.sstatic.net/pnZ0l.png)](https://i.sstatic.net/pnZ0l.png)

could be represented in this way:

[![enter image description here](https://i.sstatic.net/QZ1om.png)](https://i.sstatic.net/QZ1om.png)

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?

**Tags:** reference-request, automata-theory, dfa, nfa

> **Comments:**
> **username_1**: 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).  
> **username_2**: I'm with @username_1 here: the definition does not seem entirely clear.  Do you basically mean that transitions may be labeled by words?  
> **username_1**: @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.  
> **username_0**: @username_1 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.  
> **username_0**: @MichaëlCadilhac I've clarified the definition, I hope.  
> **username_2**: Thanks.  For your question 1, union is trivial, since you can just branch out on $\mathcal{A}$ and $\mathcal{B}$, right?  For question 2, it certainly is possible to compute a deterministic automaton, the challenge really is to keep the size tame.  For question 3, did you try making a variant of the usual NFA that explodes? Like, "the word has a string of $k$ letters $a$ that are $n$ letters before the end"?  
> **username_0**: @MichaëlCadilhac yes, you're right. Question 1 is just a warmup to state question 2 that is the real problem. Obtaining determinism *or* succinctness is easy, whereas how to obtain both is not so obvious to me.  
> **username_3**: Can the hidden states be accepting? If yes, then the size of DSA's stays the same under complement, if not, then $\{a^n \mid n\equiv 0 (mod m)\}$ shows they might have an exponential growth.  

---

## 2 answers

### Answer by username_1 on 2016-10-27. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_5**: 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.  
> **username_1**: @username_5 - 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.  
> **username_0**: @username_5 actually any label is allowed in the edges. The single letter was only a matter of the example. I'll edit.  
> **username_0**: @username_1 In the last sentence of point two you meant "So a *DSA* would need...", right?  
> **username_0**: @username_1 anyway you're right for point 2. Good point!  
> **username_1**: @gigabytes - of course, DSA. I edited the answer.  
> **username_3**: It took me a while to realize that your 2 is the 3rd question, and your 3 is the 2nd question, maybe you should mention this.  
> **username_1**: @username_3 - I emphasized the property of each article.  

---

### Answer by username_4 on 2016-10-27. Score: 3

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


---

