<p>If infinite words are in your scope, you can generalize DFA (with parity condition) to the so-called Good-for-Games automata (GFG), that still have polynomial containment.</p>

<p>A NFA is GFG if there is a strategy $\sigma:A^*\times Q\times A\to \Delta$, that given the prefix read so far and the current state and letter, chooses a transition to go to the next state. The strategy $\sigma$ has to ensure that for every $w$ in the language of the automaton, the run yielded by $\sigma$ on $w$ is accepting.</p>

<p>The containment for these automata is in <strong>P</strong> for any fixed parity condition (by reducing to parity games), and in <strong>Quasi-P</strong> if the parity index is part of the input. They can be exponentially smaller than any equivalent DFA [3].</p>

<p>On finite words however, they are just DFAs with possible useless additional transitions, so they don't really bring anything new.</p>

<p>Here are some references: </p>

<p>[1] <a href="http://link.springer.com/chapter/10.1007/11874683_26#page-1" rel="nofollow noreferrer">Solving games without determinization</a>, Henzinger, Piterman, in CSL 2006</p>

<p>[2] <a href="http://perso.ens-lyon.fr/denis.kuperberg/papers/ICALP13long.pdf" rel="nofollow noreferrer">Nondeterminism in the presence of a diverse or unknown future</a>, Boker, Kuperberg, Kupferman, Skrzypczak, in ICALP 2013</p>

<p>[3] <a href="http://perso.ens-lyon.fr/denis.kuperberg/papers/GFGlong.pdf" rel="nofollow noreferrer">On Determinisation of Good-for-Games Automata</a>, Kuperberg, Skrzypczak, in ICALP 2015</p>

CC BY-SA 3.0
2014-06-17T16:16:52.680Z
So, can the GFG's only be smaller than an equivalent DFA for infinite input? i.e. is there any efficiency gain for finite input?
Joey Eremondi
CC BY-SA 3.0
2014-06-17T16:21:05.217Z
it is already written in the answer, any GFG on finite words is actually a DFA with additional useless transitions, so there is no efficiency gain for finite words.
Denis
CC BY-SA 3.0
2014-06-17T16:24:17.853Z
Okay, I just wasn't sure if I was interpreting that right. Thanks!
Joey Eremondi
CC BY-SA 3.0
2014-06-17T15:07:27.183Z
2017-03-15T08:46:06.107Z
2017-03-15T08:46:06.107Z
Denis
<p>A <em>Non deterministic XOR automaton</em> (NXA) fits your question.</p>

<p>A NXA $M$ is essentially an NFA, but a word $w\in \Sigma^*$ is said to be in $L(M)$ if it is accepted by an odd number of paths (Xor relation) instead of being accepted if there exists an accepting path for it (Or relation).</p>

<p>NXAs are used for creating small representations of regular languages as well as some parametrized algorithms.</p>

<p>In a result from 2009, Vuillemin and Gama <a href="http://hal.inria.fr/docs/00/48/70/31/PDF/MXA.pdf" rel="noreferrer">gave an efficient, $O(|Q|^3$) algorithm</a> for NXA minimization, which can be used to answer whether $L(M_1)\subseteq L(M_2)$.</p>

CC BY-SA 3.0
2014-06-19T07:49:19.113Z
2014-06-20T09:00:40.497Z
2014-06-20T09:00:40.497Z
R B
<p>Let me first mention that your problem is not symmetric and that if $M_1$ is an NFA and $M_2$ a DFA, then the inclusion problem is polynomial (simply because it amounts to test whether the complement of $L(M_2)$ intersects $L(M_1)$ ).</p>

<p>There is an important and non-trivial generalisation of this result: when $M_2$ is <strong>non-ambiguous</strong> (over any input, there is at most one accepting run). This result is proved in [SH85], but it also has an interesting connections to Schützenberger's work [S61], and as a consequence with NXA as mentionned in an answer above. (let me thank Jacques Sakarovitch for showing it to me).</p>

<p>Let me sketch a proof of this result.</p>

<hr>

<p><strong>Theorem</strong> Consider non-deterministic automata $M_1$, $M_2$, $M_2$ being non-ambiguous. One can decide $L(M_1)\subseteq L(M_2)$ in polynomial time.</p>

<p><em>Proof.</em><br>
<strong>Step 1:</strong> This reduces to universality of unambiguous automata.</p>

<p>Substep 1: we can assume $M_1$ to be deterministic (for this, it is sufficient to reformulate the problem over the alphabet consisting of the transitions of $M_1$).</p>

<p>Substep 2: then $L(M_1)\subseteq L(M_2)$ is equivalent to the universality of $L(M_2)\cup L(M_1)^c$, which is represented by a non-ambiguous automaton of polynomial size.</p>

<p><strong>Step 2:</strong> It happens that unambiguous automata can be seen as NXA automata (Non-deterministic XOR automata in the previous post by RB) without there evaluation to be changed (indeed, a disjunction over all accpeting runs is equivalent to a xor over all accepting runs since there is at most one such run). For these automata, universality is known to be polynomial (QED).</p>

<p>Let me not that this polynomial universality result was known well before 2009. 
Indeed, NXA automata are classically known as weighted automata over the field $Z/2Z$.
Such automata were introduced by Schützenberger in [S61]. He proves in this paper that the equivalence (and consequently universality) is decidable (using minimization) for all effective fields [S61]. The polynomial complexity some years after.</p>

<hr>

<p>[SH85] Richard E. Stearns and Harry B. Hunt III. On the equivalence and containment prob-
lems for unambiguous regular expressions, regular grammars and finite automata.
SIAM J. Comput., 14(3):598–611, 1985.</p>

<p>[S61] Schützenberger, M.P.: On the definition of a family of automata. Information and
Control 4, 245–270 (1961)</p>

CC BY-SA 3.0
2014-08-08T21:01:51.827Z
2014-08-08T21:01:51.827Z
Thomas Colcombet
<p>Regular LL(k) grammars (i.e. grammars that are both <a href="https://doi.org/10.1016/S0019-9958(70)90446-8" rel="nofollow noreferrer">LL(k)</a> and <a href="https://en.wikipedia.org/wiki/Regular_grammar" rel="nofollow noreferrer">regular</a>) can be converted in polynomial time into equivalent deterministic finite automata, and thus language containment and equivalence can be solved in PTIME. See Theorem 4.2 in the following paper (and the results afterwards for an application of this observation to program schemes).</p>

<p>Harry B. Hunt III: <a href="https://doi.org/10.1016/0022-0000(79)90002-3" rel="nofollow noreferrer">Observations on the Complexity of Regular Expression Problems</a>, Journal of Computer and System Sciences 19, 222-236 (1979)</p>

CC BY-SA 4.0
2018-12-29T22:19:55.187Z
2018-12-29T22:19:55.187Z
Hermann Gruber
<p><em>Visibly pushdown automata</em> (or <em>nested word automata</em>, if you prefer working with <a href="http://en.wikipedia.org/wiki/Nested_word">nested words</a> instead of finite words) extend the expressive power of deterministic finite automata: the class of regular languages is strictly contained within the class of visibly pushdown languages. For deterministic visibly pushdown automata, the language inclusion problem can be solved in polynomial time. For more details, see the paper by Alur and Madhusudan, especially Chapter 6.</p>

<p>By the way, the nondeterministic variant of visibly pushdown automata is exponentially more succinct than the deterministic variant, but there the language inclusion problem is EXPTIME-complete and thus intractable. </p>

<p>Alur, R.; Madhusudan, P. (2009). "<a href="http://www.cis.upenn.edu/~alur/Jacm09.pdf">Adding nesting structure to words</a>". Journal of the ACM <strong>56</strong>(3): 1–43.</p>

CC BY-SA 3.0
2014-06-21T23:58:58.157Z
Bonus points for finding a model more powerful than the regular languages! I'd heard of these but I didn't know things were polynomial for the deterministic version!
Joey Eremondi
CC BY-SA 3.0
2014-06-28T10:48:41.593Z
Thanks a lot. If you can make use of this model, please let us know at this place.
Hermann Gruber
CC BY-SA 3.0
2014-06-21T21:27:24.023Z
2014-06-21T21:27:24.023Z
Hermann Gruber
<p>I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if you have machines $M_1, M_2$ you can test if $L(M_1) \subseteq L(M_2)$ efficiently.</p>

<p>The obvious ones that come to mind are DFAs and reversal-bounded counter machines where the number of counters is fixed (see <a href="http://www.sciencedirect.com/science/article/pii/0022000081900283">this paper</a>).</p>

<p>What other notable classes can be added to this list?</p>

<p>The more powerful the automata, the better. For example, DFA's aren't enough to solve my problem, and the counter machines can't do it with a fixed number of counters. (Naturally, if you get too powerful, then containment is either intractible, like for NFA's, or undecidable, for CFG's).</p>

CC BY-SA 3.0
2014-06-17T14:57:51.577Z
are you interested in infinite words, or specifically finite words?
Denis
CC BY-SA 3.0
2014-06-17T16:16:03.850Z
I'm not sure if infinte words would apply to my particular problem, but they're certainly in the scope of the question!
Joey Eremondi
<fl.formal-languages><automata-theory><time-complexity><polynomial-time><decidability>
What notable automaton models have polynomially-decidable containment?
Joey Eremondi
# What notable automaton models have polynomially-decidable containment?

(Asked by: username_0 on 2014-06-16)

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if you have machines $M\_1, M\_2$ you can test if $L(M\_1) \subseteq L(M\_2)$ efficiently.

The obvious ones that come to mind are DFAs and reversal-bounded counter machines where the number of counters is fixed (see [this paper](http://www.sciencedirect.com/science/article/pii/0022000081900283)).

What other notable classes can be added to this list?

The more powerful the automata, the better. For example, DFA's aren't enough to solve my problem, and the counter machines can't do it with a fixed number of counters. (Naturally, if you get too powerful, then containment is either intractible, like for NFA's, or undecidable, for CFG's).

**Tags:** fl.formal-languages, automata-theory, time-complexity, polynomial-time, decidability

> **Comments:**
> **username_1**: are you interested in infinite words, or specifically finite words?  
> **username_0**: I'm not sure if infinte words would apply to my particular problem, but they're certainly in the scope of the question!  

---

## 5 answers

### Answer by username_4 on 2014-06-21. Score: 16 | Accepted answer

*Visibly pushdown automata* (or *nested word automata*, if you prefer working with [nested words](http://en.wikipedia.org/wiki/Nested_word) instead of finite words) extend the expressive power of deterministic finite automata: the class of regular languages is strictly contained within the class of visibly pushdown languages. For deterministic visibly pushdown automata, the language inclusion problem can be solved in polynomial time. For more details, see the paper by Alur and Madhusudan, especially Chapter 6.

By the way, the nondeterministic variant of visibly pushdown automata is exponentially more succinct than the deterministic variant, but there the language inclusion problem is EXPTIME-complete and thus intractable.

Alur, R.; Madhusudan, P. (2009). "[Adding nesting structure to words](http://www.cis.upenn.edu/~alur/Jacm09.pdf)". Journal of the ACM **56**(3): 1–43.

> **Comments:**
> **username_0**: Bonus points for finding a model more powerful than the regular languages! I'd heard of these but I didn't know things were polynomial for the deterministic version!  
> **username_4**: Thanks a lot. If you can make use of this model, please let us know at this place.  

---

### Answer by username_1 on 2014-06-17. Score: 14

If infinite words are in your scope, you can generalize DFA (with parity condition) to the so-called Good-for-Games automata (GFG), that still have polynomial containment.

A NFA is GFG if there is a strategy $\sigma:A^\*\times Q\times A\to \Delta$, that given the prefix read so far and the current state and letter, chooses a transition to go to the next state. The strategy $\sigma$ has to ensure that for every $w$ in the language of the automaton, the run yielded by $\sigma$ on $w$ is accepting.

The containment for these automata is in **P** for any fixed parity condition (by reducing to parity games), and in **Quasi-P** if the parity index is part of the input. They can be exponentially smaller than any equivalent DFA [3].

On finite words however, they are just DFAs with possible useless additional transitions, so they don't really bring anything new.

Here are some references:

[1] [Solving games without determinization](http://link.springer.com/chapter/10.1007/11874683_26#page-1), Henzinger, Piterman, in CSL 2006

[2] [Nondeterminism in the presence of a diverse or unknown future](http://perso.ens-lyon.fr/denis.kuperberg/papers/ICALP13long.pdf), Boker, Kuperberg, Kupferman, Skrzypczak, in ICALP 2013

[3] [On Determinisation of Good-for-Games Automata](http://perso.ens-lyon.fr/denis.kuperberg/papers/GFGlong.pdf), Kuperberg, Skrzypczak, in ICALP 2015

> **Comments:**
> **username_0**: So, can the GFG's only be smaller than an equivalent DFA for infinite input? i.e. is there any efficiency gain for finite input?  
> **username_1**: it is already written in the answer, any GFG on finite words is actually a DFA with additional useless transitions, so there is no efficiency gain for finite words.  
> **username_0**: Okay, I just wasn't sure if I was interpreting that right. Thanks!  

---

### Answer by username_2 on 2014-06-19. Score: 11

A *Non deterministic XOR automaton* (NXA) fits your question.

A NXA $M$ is essentially an NFA, but a word $w\in \Sigma^\*$ is said to be in $L(M)$ if it is accepted by an odd number of paths (Xor relation) instead of being accepted if there exists an accepting path for it (Or relation).

NXAs are used for creating small representations of regular languages as well as some parametrized algorithms.

In a result from 2009, Vuillemin and Gama [gave an efficient, $O(|Q|^3$) algorithm](http://hal.inria.fr/docs/00/48/70/31/PDF/MXA.pdf) for NXA minimization, which can be used to answer whether $L(M\_1)\subseteq L(M\_2)$.


---

### Answer by username_3 on 2014-08-08. Score: 7

Let me first mention that your problem is not symmetric and that if $M\_1$ is an NFA and $M\_2$ a DFA, then the inclusion problem is polynomial (simply because it amounts to test whether the complement of $L(M\_2)$ intersects $L(M\_1)$ ).

There is an important and non-trivial generalisation of this result: when $M\_2$ is **non-ambiguous** (over any input, there is at most one accepting run). This result is proved in [SH85], but it also has an interesting connections to Schützenberger's work [S61], and as a consequence with NXA as mentionned in an answer above. (let me thank Jacques Sakarovitch for showing it to me).

Let me sketch a proof of this result.

---

**Theorem** Consider non-deterministic automata $M\_1$, $M\_2$, $M\_2$ being non-ambiguous. One can decide $L(M\_1)\subseteq L(M\_2)$ in polynomial time.

*Proof.*  
**Step 1:** This reduces to universality of unambiguous automata.

Substep 1: we can assume $M\_1$ to be deterministic (for this, it is sufficient to reformulate the problem over the alphabet consisting of the transitions of $M\_1$).

Substep 2: then $L(M\_1)\subseteq L(M\_2)$ is equivalent to the universality of $L(M\_2)\cup L(M\_1)^c$, which is represented by a non-ambiguous automaton of polynomial size.

**Step 2:** It happens that unambiguous automata can be seen as NXA automata (Non-deterministic XOR automata in the previous post by RB) without there evaluation to be changed (indeed, a disjunction over all accpeting runs is equivalent to a xor over all accepting runs since there is at most one such run). For these automata, universality is known to be polynomial (QED).

Let me not that this polynomial universality result was known well before 2009.
Indeed, NXA automata are classically known as weighted automata over the field $Z/2Z$.
Such automata were introduced by Schützenberger in [S61]. He proves in this paper that the equivalence (and consequently universality) is decidable (using minimization) for all effective fields [S61]. The polynomial complexity some years after.

---

[SH85] Richard E. Stearns and Harry B. Hunt III. On the equivalence and containment prob-
lems for unambiguous regular expressions, regular grammars and finite automata.
SIAM J. Comput., 14(3):598–611, 1985.

[S61] Schützenberger, M.P.: On the definition of a family of automata. Information and
Control 4, 245–270 (1961)


---

### Answer by username_4 on 2018-12-29. Score: 1

Regular LL(k) grammars (i.e. grammars that are both [LL(k)](https://doi.org/10.1016/S0019-9958(70)90446-8) and [regular](https://en.wikipedia.org/wiki/Regular_grammar)) can be converted in polynomial time into equivalent deterministic finite automata, and thus language containment and equivalence can be solved in PTIME. See Theorem 4.2 in the following paper (and the results afterwards for an application of this observation to program schemes).

Harry B. Hunt III: [Observations on the Complexity of Regular Expression Problems](https://doi.org/10.1016/0022-0000(79)90002-3), Journal of Computer and System Sciences 19, 222-236 (1979)


---

