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.

Two of my last questions seem to have been quickly dispatched; one completely, and the other mostly (I have edited it to make it more viable). In either event, I actually had one other question I meant to ask, and would be interested to lay this subject to rest for good and all. So here it is:

A two-stack PDA can simulate a Turing machine. A $k$-heap nondeterministic type-1 min-heap automaton cannot (it seems; see the linked question). What about a $k$-tape nondeterministic type-1 min-heap automaton augmented with a stack (similar to that of a PDA)? Can it simulate a Turing machine? If not, does an augmented $(k+1)$-heap nondeterministic type-1 min-heap automaton accept a class of languages which is a proper superset of languages accepted by augmented automata with only $k$ heaps?

Thanks, and I promise this is the last of these questions.

  • 1
    $\begingroup$ In the original question, it is shown that EPAL isn't recognizable using a single heap. Yet it is context-free, so it is certainly recognizable if you add a stack. $\endgroup$ Apr 24, 2012 at 20:45
  • $\begingroup$ @YuvalFilmus Good observation: adding a stack means that the automata can accept at least $HAL \cup CFL$. Can they accept more, though? $\endgroup$
    – Patrick87
    Apr 24, 2012 at 21:04
  • $\begingroup$ It can accept the language $\{ww^R : w \in (0+1)^*\} \cup \{a^nb^nc^n : n \geq 0\}$, which is neither in HAL nor in CFL. $\endgroup$ Apr 26, 2012 at 7:51

1 Answer 1


A heap and a stack can both be used to implement a counter. 2 counters suffice to recognize $RE$. (See also)


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.