0
$\begingroup$

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

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ The question is not well-defined. Please think why. Hint: Decidability is a property of a function. What is the input to the function? $\endgroup$
    – Tsuyoshi Ito
    Commented Mar 16, 2012 at 23:48
  • 3
    $\begingroup$ Language inclusion is decidable for very simple deterministic pushdown automata (citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1633) and a restricted version of timed finite state machine (dl.acm.org/citation.cfm?id=1018438.1021842). $\endgroup$
    – Marzio De Biasi
    Commented Mar 17, 2012 at 0:09
  • 2
    $\begingroup$ @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. $\endgroup$
    – David Lewis
    Commented Mar 17, 2012 at 1:40
  • 1
    $\begingroup$ 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). $\endgroup$
    – Kaveh
    Commented Mar 17, 2012 at 5:36
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Commented Mar 17, 2012 at 10:31

2 Answers 2

Reset to default
4
$\begingroup$

Converted from comment: language inclusion is decidable for very simple deterministic pushdown automata ("On the Inclusion Problem for Very Simple Deterministic Pushdown Automata (1999)" 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" by J. Ouaknine and J. Worrell, 2004).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$
    – vzn
    Commented Mar 21, 2012 at 20:20
-2
$\begingroup$

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.

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.