I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here.

This question concerns the computational power of type-2 min-heap automata, which were suggested by Raphael as a more natural kind of computing device. The class of languages which can be accepted by such automata is a proper superset of the set of context-free languages; which leads me to my question.

Is $HAL_2$ (the set of languages accepted by nondeterministic type-2 min-heap automata) a proper subset of $CSL$ (the set of context-sensitive languages), or not? Note that it is already known (shown by Raphael in the linked question) that there are $CSL$ languages not in in $HAL_2$.

This is one of the last questions I intend to ask about these automata. If a good answer can be found to these (and other) questions, my curiosity will be completely satisfied. Thanks in advance and for all the hard work so far.

  • $\begingroup$ We already know $\mathrm{HAL}_2 \not\supseteq\mathrm{CSL}$. $\endgroup$
    – Raphael
    Apr 1, 2012 at 7:40
  • $\begingroup$ @Raphael Oops. Is that in the original question? I forgot anybody showing this. Will delete ASAP. $\endgroup$
    – Patrick87
    Apr 1, 2012 at 13:36
  • $\begingroup$ @Raphael Found where you addressed this, and tried to change the question to make it meaningful. Now the question is simply whether these automata are strictly less powerful than LBAs. $\endgroup$
    – Patrick87
    Apr 1, 2012 at 13:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.