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$ – Yuval Filmus Apr 24 '12 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 '12 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$ – 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)


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.