# Power of nondeterministic type-1 min-heap automaton with both a heap and a stack

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.

• 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. – Yuval Filmus Apr 24 '12 at 20:45
• @YuvalFilmus Good observation: adding a stack means that the automata can accept at least $HAL \cup CFL$. Can they accept more, though? – Patrick87 Apr 24 '12 at 21:04
• 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. – Yuval Filmus Apr 26 '12 at 7:51

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