This is a follow-up question of this one. In a previous question about exotic st

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?

Explanation / Answer

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?|x|=|y|?x?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 xi (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 yi and he PDA can check if xi?yi. (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 x1 and x2 that after reading them, the content of the heap is the same. Then consider the words x1$x1 and x2$x1. 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?

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.