21
$\begingroup$

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

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

Improve this question
$\endgroup$
2
  • $\begingroup$ are you interested in infinite words, or specifically finite words? $\endgroup$
    – Denis
    Jun 17, 2014 at 14:57
  • 2
    $\begingroup$ I'm not sure if infinte words would apply to my particular problem, but they're certainly in the scope of the question! $\endgroup$
    – Joey Eremondi
    Jun 17, 2014 at 16:16

5 Answers 5

Reset to default
16
+50
$\begingroup$

Visibly pushdown automata (or nested word automata, if you prefer working with nested words 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". Journal of the ACM 56(3): 1–43.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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! $\endgroup$
    – Joey Eremondi
    Jun 21, 2014 at 23:58
  • $\begingroup$ Thanks a lot. If you can make use of this model, please let us know at this place. $\endgroup$
    – Hermann Gruber
    Jun 28, 2014 at 10:48
14
$\begingroup$

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, Henzinger, Piterman, in CSL 2006

[2] Nondeterminism in the presence of a diverse or unknown future, Boker, Kuperberg, Kupferman, Skrzypczak, in ICALP 2013

[3] On Determinisation of Good-for-Games Automata, Kuperberg, Skrzypczak, in ICALP 2015

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Joey Eremondi
    Jun 17, 2014 at 16:16
  • 2
    $\begingroup$ 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. $\endgroup$
    – Denis
    Jun 17, 2014 at 16:21
  • $\begingroup$ Okay, I just wasn't sure if I was interpreting that right. Thanks! $\endgroup$
    – Joey Eremondi
    Jun 17, 2014 at 16:24
11
$\begingroup$

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 for NXA minimization, which can be used to answer whether $L(M_1)\subseteq L(M_2)$.

Improve this answer
$\endgroup$
7
$\begingroup$

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)

Improve this answer
$\endgroup$
1
$\begingroup$

Regular LL(k) grammars (i.e. grammars that are both LL(k) and regular) 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, Journal of Computer and System Sciences 19, 222-236 (1979)

Improve this answer
$\endgroup$

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.