Computational power of deterministic versus nondeterministic min-heap automata

Question

This is a follow-up question of this one.

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of the set of context-free languages. Given the successful resolution of and apparent interest in that question, I proceed to ask several follow-up questions.

It is known that deterministic and nondeterministic finite automata have equivalent computational capabilities, as do deterministic and nondeterministic Turing machines. However, the computational capabilities of deterministic push-down automata are less than those of nondeterministic push-down automata.

Are the computational capabilities of deterministic min-heap automata less than, or are they equal to, those of nondeterministic min-heap automata?

Answer 1

It seems that for this model, non-deterministic machines are not equivalent to deterministic ones, for basically the same reason that deterministic PDAs are not equivalent to non-deterministic ones.

Consider the language $$L =\\{ x\$y \mid |x|=|y| \wedge x\ne y\\}$$ (where $\$$ is a special sign not contained in $x$ and $y$).

I claim that a non-deterministic machine $N$-$HAL$ can decide this language: It performs the same as the PDA for $L$. The standard PDA solution uses the stack only to count offsets: it nondeterministically guesses an offset $i$, remembers the value of $x_i$ (adding a symbol to the stack at each step), then the PDA ignores the input until it find the $\$$, and then it pops symbols out of the stack until it is empty. At this stage we are exactly at $y_i$ and he PDA can check if $x_i \ne y_i$. (if anything goes wrong in the middle, the PDA "dies"). Since the stack alphabet is unary, it can be simulated with a min-heap machine. Actually: any $L$ that is is accepted by a PDA with a unary alphabet can be accepted by a min-heap machine. (I'm ignoring, maybe, another special sign added to identify an empty stack, but an equivalent sign can be added to the heap)

For the other direction, I don't have the formal proof, but here are my thoughts:

I claim that a deterministic machine $D$-$HAL$ is incapable of deciding this language. Intuitively, the content of the heap can not be correlated with $x$ (otherwise, permute $x$. the content of the heap remains the same..). This suggests that only thing that matters is the number of elements in the heap, but then, if $D$-$HAL$ can decide $L$, so can a deterministic-$PDA$.

Edit: more details about the "permute $x$" claim. Assuming Raphael's conjecture there exist $x_1$ and $x_2$ that after reading them, the content of the heap is the same. Then consider the words $x_1\$x_1$ and $x_2\$x_1$. The content of the heap is the same when the HAL gets to the dollar sign, thus it must either accept both or reject both. contradiction.

anyone sees an immediate proof for the conjecture?