<p>Converted from comment: language inclusion is decidable for very simple deterministic pushdown automata ("<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1633" rel="nofollow">On the Inclusion Problem for Very Simple Deterministic Pushdown Automata (1999)</a>" by E. Makinen, 1999) 
and a restricted version of timed finite state machine ("<a href="http://dl.acm.org/citation.cfm?id=1018438.1021842" rel="nofollow">On the Language Inclusion Problem for Timed Automata: Closing a Decidability Gap</a>" by J. Ouaknine and J. Worrell, 2004).</p>

CC BY-SA 3.0
2012-03-21T20:20:31.330Z
thx; does anyone know for those classes above, "very simple DPDAs" vs "timed automata" whether one class includes the other class? or if they overlap or are disjoint?
vzn
CC BY-SA 3.0
2012-03-17T21:40:06.657Z
2012-03-17T21:40:06.657Z
Marzio De Biasi
<p>for a 1st cut answer to this question see p281 of hopcroft/ullman 1979. its a nice table of lots of properties/decision problems wrt basic known languages ie regular, DCFL, CFL, CSL, recursive, r.e. on the horizontal axis and basic questions like "w in L, L= $\oslash $, L=$\Sigma *$" etc on vertical axis.</p>

<p>now they do not explicitly state how the languages are given, but the assumption is they are using their characteristic form eg regular grammars or DFAs for regular languages, DCGs for DCFLs, CSGs for CSLs etc.; nor do they give reference for all the results in cells of the grid, that would be a big effort because of the large size of the table &amp; the diversity of results.</p>

<p>for $L_1 \subseteq L_2$ its decidable for regular sets but undecidable for DCFLs and higher (CFLs, CSLs, recursive, r.e.)</p>

<p>[I typed this question from old memory &amp; had forgotten this result, oops. namely, inclusion problem is decidable for regular sets but not for all standard well known larger language classes. however,still do wonder, could there be a language class "between" regular sets and DCFLs for which inclusion is decidable? or possibly some language class not contained in any of those standard classes?]</p>

<p>but the case for FSM transducers raised in the question may have a different answer.</p>

<p>&amp; I am still not clear on the table, because [as raised in comments] what is the characteristic form for a recursive set? [the r.e. sets are surely given by TMs]</p>

<p>sorry for any confusion in the way the original question was phrased, as always there might be a better way to phrase it.</p>

CC BY-SA 3.0
2012-03-17T20:11:43.583Z
2012-03-17T20:11:43.583Z
vzn
<p>am wondering what is the largest language class that is known for which set inclusion is decidable, ie a class such that if $A, B$ are in that class then $A \subset B$ is decidable.</p>

<p>am also interested in the same question for what were once called "GSMs", generalized sequential machines, or maybe more modernly, FSM "transducers", where if $f(x)$ is the transducer, $C \subset f(C)$, $C$ in the class.</p>

<p>(of course, the problem is also equivalent to determining whether the intersection of a complement is empty.)</p>

<p>[simply asking for the "largest known" language is a literature related question. however some kind of proof that there exists a "largest class" I believe is an open question. although, there might be a straightfwd argument of nonexistence via diagonalization...?]</p>

<p>unfortunately wikipedia does not have some of this basic info for major language classes. wonder if there is any table, paper, or reference esp online.</p>

<p>there is a nice table of decidability &amp; undecidability of basic language questions in [1] but its quite dated at this point.</p>

<p>[1] <a href="http://rads.stackoverflow.com/amzn/click/020102988X" rel="nofollow">Hopcroft/Ullman, Intro to Automata Theory, Languages &amp; Computation, 1979</a></p>

CC BY-SA 3.0
2012-03-16T23:48:20.367Z
The question is not well-defined.  Please think why.  Hint: Decidability is a property of a function.  What is the input to the function?
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-17T00:09:11.977Z
Language inclusion is decidable for very simple deterministic pushdown automata (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1633) and a restricted version of timed finite state machine (http://dl.acm.org/citation.cfm?id=1018438.1021842).
Marzio De Biasi
CC BY-SA 3.0
2012-03-17T01:40:05.840Z
@Tsuyoshi Ito -- decidability can also be a property of sets, by using, for example, the characteristic function.  Or, more directly, there can be formal models for sets other than function mechanisms, which have undecidability properties, for example, grammars of various kinds.
David Lewis
CC BY-SA 3.0
2012-03-17T02:16:58.090Z
@DavidLewis: Of course you can define decidability of a set by using the characteristic function, but that does not change the fact that this question is not well-defined.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-17T02:44:57.477Z
I agree it's not well-defined, and the questioner acknowledges that.  But there are ways to start approaching it -- choose a formal model (resource-limited TMs, AFLs, whatever), for example, and look for increasing sequences of languages and maximal languages with specific decidability properties. In fact, it may be a good area for research -- I have not run across anyone asking the question in this way. The idea to use finite-state transducers, for example, is closely related to AFL theory, and has been used quite a bit for increasing (and decreasing) sequences of languages.
David Lewis
CC BY-SA 3.0
2012-03-17T05:36:36.723Z
how are $A$ and $B$ given (since they can be infinite)? Without this information the question does not make sense. If they are given as TMs then your class cannot have more than one language. (The proof is similar to the proof of Rice's theorem).
Kaveh
CC BY-SA 3.0
2012-03-17T10:31:47.947Z
@DavidLewis: “I agree it's not well-defined, and the questioner acknowledges that.”  Where does the asker acknowledges that the question is not well-defined?  Note that “open question” does not mean an ill-defined question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-17T12:38:59.143Z
@Tsuyoshi Ito -- This is the relevant passage...simply asking for the "largest known" language is a literature related question. however some kind of proof that there exists a "largest class" I believe is an open question. although, there might be a straightfwd argument of nonexistence via diagonalization...?]... Back to me -- Remember, the set of models of computation for defining the class of RE or recursive languages/functions is ~extremely~ robust -- one of a zillion models will do.  That's, in effect, the Church-Rosser-Turing Thesis. There ~are~ ways to formalize and study this.
David Lewis
CC BY-SA 3.0
2012-03-17T12:41:50.387Z
@Kaveh -- does the analogy to Rice's Theorem hold when the TMs are resource limited in some way -- tape size, time, etc.? I don't think so, or at least not in a way that will collapse all hierarchies. Otherwise, we'd have nothing to study in sub-recursive computational complexity.
David Lewis
CC BY-SA 3.0
2012-03-17T13:52:11.567Z
@David Lewis: As I said, the asker has not acknowledged that the question is not well-defined.  As I said, “open question” does not mean an ill-defined question.  I will not repeat myself any more.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-17T14:20:36.737Z
I thought that the reference to a literature search being a way to answer, and putting "largest known" in quotes showed the questioner realized it may not be amenable to a strictly definable or provable answer.  As I said, I can actually see ways to cast some formal light on this by constructing upward hierarchies of languages/families with decidable inclusion.  If we can formalize and answer the question for specific families, no inherent reason we can't parametrize it. They will probably be fairly low level, however, as going up with inclusion/intersection quickly makes things non-recursive.
David Lewis
CC BY-SA 3.0
2012-03-17T16:48:49.297Z
@David, resource bounded TMs is a different way of giving inputs than general TMs. My comment is about general TMs. (but this might hold for resource bounded TMs also.)
Kaveh
CC BY-SA 3.0
2012-03-17T20:39:06.823Z
@vor thx you have the closest, if you answer I for one will upvote & accept if nothing else shows up
vzn
<reference-request><fl.formal-languages><computability><open-problem>
largest language class for which inclusion is decidable
vzn
# largest language class for which inclusion is decidable

(Asked by: username_0 on 2012-03-16)

am wondering what is the largest language class that is known for which set inclusion is decidable, ie a class such that if $A, B$ are in that class then $A \subset B$ is decidable.

am also interested in the same question for what were once called "GSMs", generalized sequential machines, or maybe more modernly, FSM "transducers", where if $f(x)$ is the transducer, $C \subset f(C)$, $C$ in the class.

(of course, the problem is also equivalent to determining whether the intersection of a complement is empty.)

[simply asking for the "largest known" language is a literature related question. however some kind of proof that there exists a "largest class" I believe is an open question. although, there might be a straightfwd argument of nonexistence via diagonalization...?]

unfortunately wikipedia does not have some of this basic info for major language classes. wonder if there is any table, paper, or reference esp online.

there is a nice table of decidability & undecidability of basic language questions in [1] but its quite dated at this point.

[1] [Hopcroft/Ullman, Intro to Automata Theory, Languages & Computation, 1979](http://rads.stackoverflow.com/amzn/click/020102988X)

**Tags:** reference-request, fl.formal-languages, computability, open-problem
> **Comments:**
> **username_1**: The question is not well-defined.  Please think why.  Hint: Decidability is a property of a function.  What is the input to the function?  
> **username_2**: Language inclusion is decidable for very simple deterministic pushdown automata (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1633) and a restricted version of timed finite state machine (http://dl.acm.org/citation.cfm?id=1018438.1021842).  
> **username_3**: @Tsuyoshi Ito -- decidability can also be a property of sets, by using, for example, the characteristic function.  Or, more directly, there can be formal models for sets other than function mechanisms, which have undecidability properties, for example, grammars of various kinds.  
> **username_1**: @DavidLewis: Of course you can define decidability of a set by using the characteristic function, but that does not change the fact that this question is not well-defined.  
> **username_3**: I agree it's not well-defined, and the questioner acknowledges that.  But there are ways to start approaching it -- choose a formal model (resource-limited TMs, AFLs, whatever), for example, and look for increasing sequences of languages and maximal languages with specific decidability properties. In fact, it may be a good area for research -- I have not run across anyone asking the question in this way. The idea to use finite-state transducers, for example, is closely related to AFL theory, and has been used quite a bit for increasing (and decreasing) sequences of languages.  
> **username_4**: how are $A$ and $B$ given (since they can be infinite)? Without this information the question does not make sense. If they are given as TMs then your class cannot have more than one language. (The proof is similar to the proof of Rice's theorem).  
> **username_1**: @DavidLewis: “I agree it's not well-defined, and the questioner acknowledges that.”  Where does the asker acknowledges that the question is not well-defined?  Note that “open question” does not mean an ill-defined question.  
> **username_3**: @Tsuyoshi Ito -- This is the relevant passage...simply asking for the "largest known" language is a literature related question. however some kind of proof that there exists a "largest class" I believe is an open question. although, there might be a straightfwd argument of nonexistence via diagonalization...?]... Back to me -- Remember, the set of models of computation for defining the class of RE or recursive languages/functions is ~extremely~ robust -- one of a zillion models will do.  That's, in effect, the Church-Rosser-Turing Thesis. There ~are~ ways to formalize and study this.  
> **username_3**: @Kaveh -- does the analogy to Rice's Theorem hold when the TMs are resource limited in some way -- tape size, time, etc.? I don't think so, or at least not in a way that will collapse all hierarchies. Otherwise, we'd have nothing to study in sub-recursive computational complexity.  
> **username_1**: @David Lewis: As I said, the asker has not acknowledged that the question is not well-defined.  As I said, “open question” does not mean an ill-defined question.  I will not repeat myself any more.  
> **username_3**: I thought that the reference to a literature search being a way to answer, and putting "largest known" in quotes showed the questioner realized it may not be amenable to a strictly definable or provable answer.  As I said, I can actually see ways to cast some formal light on this by constructing upward hierarchies of languages/families with decidable inclusion.  If we can formalize and answer the question for specific families, no inherent reason we can't parametrize it. They will probably be fairly low level, however, as going up with inclusion/intersection quickly makes things non-recursive.  
> **username_4**: @David, resource bounded TMs is a different way of giving inputs than general TMs. My comment is about general TMs. (but this might hold for resource bounded TMs also.)  
> **username_0**: @vor thx you have the closest, if you answer I for one will upvote & accept if nothing else shows up  

---

## 2 answers

### Answer by username_2 on 2012-03-17. Score: 4 | Accepted answer

Converted from comment: language inclusion is decidable for very simple deterministic pushdown automata ("[On the Inclusion Problem for Very Simple Deterministic Pushdown Automata (1999)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1633)" by E. Makinen, 1999)
and a restricted version of timed finite state machine ("[On the Language Inclusion Problem for Timed Automata: Closing a Decidability Gap](http://dl.acm.org/citation.cfm?id=1018438.1021842)" by J. Ouaknine and J. Worrell, 2004).

> **Comments:**
> **username_0**: thx; does anyone know for those classes above, "very simple DPDAs" vs "timed automata" whether one class includes the other class? or if they overlap or are disjoint?  

---

### Answer by username_0 on 2012-03-17. Score: -2

for a 1st cut answer to this question see p281 of hopcroft/ullman 1979. its a nice table of lots of properties/decision problems wrt basic known languages ie regular, DCFL, CFL, CSL, recursive, r.e. on the horizontal axis and basic questions like "w in L, L= $\oslash $, L=$\Sigma \*$" etc on vertical axis.

now they do not explicitly state how the languages are given, but the assumption is they are using their characteristic form eg regular grammars or DFAs for regular languages, DCGs for DCFLs, CSGs for CSLs etc.; nor do they give reference for all the results in cells of the grid, that would be a big effort because of the large size of the table & the diversity of results.

for $L\_1 \subseteq L\_2$ its decidable for regular sets but undecidable for DCFLs and higher (CFLs, CSLs, recursive, r.e.)

[I typed this question from old memory & had forgotten this result, oops. namely, inclusion problem is decidable for regular sets but not for all standard well known larger language classes. however,still do wonder, could there be a language class "between" regular sets and DCFLs for which inclusion is decidable? or possibly some language class not contained in any of those standard classes?]

but the case for FSM transducers raised in the question may have a different answer.

& I am still not clear on the table, because [as raised in comments] what is the characteristic form for a recursive set? [the r.e. sets are surely given by TMs]

sorry for any confusion in the way the original question was phrased, as always there might be a better way to phrase it.


---

