15
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ While I think your are basically right, it is not as easy as saying "otherwise, permute $x$. the content [...] remains the same.". A HA (or PDA) can take patterns of constant length into account. $\endgroup$ – Raphael Mar 15 '12 at 10:16
  • $\begingroup$ Which definition of min-heaps are you using: my original one, or the more natural one suggested by Raphael? In either case, can you be more clear about how a nondeterministic machine would accept the language you give... what does it put onto and take off of the heap, and when? $\endgroup$ – Patrick87 Mar 15 '12 at 13:06
  • $\begingroup$ Doesn't Raphael's conjecture directly follow from a counting argument? While there are exponentially many strings of length $n$, the number of possible configurations (heap + state) is only polynomial in $n$, since the total number of symbols in the heap is linear and the number of different symbols is constant. $\endgroup$ – Yuval Filmus Apr 24 '12 at 20:43

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.