Computational power of nondeterministic type-1 min-heap automata with multiple heaps

Question

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.

This question concerns the power of type-1 min-heap automata, which represent my initial idea for how these machines would operate. The class of languages which can be accepted by such automata is incomparable (i.e., neither a proper subset nor a proper superset) of the set of context-free languages.

Push down automata, which possess a single stack for data storage, accept the set of context-free languages, in the same way that min-heap automata, which possess a single heap for data storage, accept the set $HAL_1$ of languages accepted by nondeterministic type-1 min-heap automata. Push-down automata with two stacks are equivalent to Turing machines in computational power; they can simulate Turing machines, and vice versa; which leads me to my question:

Does adding another heap to non-deterministic type-1 min-heap automata make them equivalent in terms of computing ability to Turing machines, in the sense that they are able to simulate Turing machines? If not, does it increase their computational power at all, in the sense that nondeterministic type-1 min-heap automata can accept a set of languages which is a proper subset of $HAL_1$? If so, does adding additional heaps increase computational power, i.e., can nondeterministic min-heap automata with $k+1$ heaps accept more languages than automata with $k$ heaps, for any $k$?

This is one of the last questions I plan to ask about these automata; if good answers can be had for these (and other) questions, my curiosity will be completely satisfied. Thanks in advance and for all the hard work so far.

Answer 1

Although the first answer has already been accepted, I understand that the power of the multiple heap automata described here have not been resolved.

With two heaps, and just a single heap symbol each (apart from the bottom-of-heap), it seems one can simulate a two-counter automaton. Such an automaton keeps two natural numbers, that can be incremented, decremented, and tested for zero. You can push and pop, and also test for bottom-of-stack, which is equivalent for zero test. Only two of these are sufficient to simulate a Turing Machine! The proof of this fact is in the first edition of the Hopcroft Ulmann book, Theorem 7.9, but seems originally from Minsky (1961). The many-counter automaton (with zero tests) is equivalent to the notion of register machine.

Thus, if I understand your definition well, the two min-heap version of your $\mathrm{ HAL}$ models are equivalent to $RE$.

Answer 2

Let $\mathrm{SDL}_k$ the shuffled Dyck language with $k$ types of parentheses, i.e.

$\qquad \displaystyle \mathrm{SDL}_k = \mathrm{DL}([_1,]_1) \, ш\, \dots \, ш\, \mathrm{DL}([_k,]_k)$

with $ш$ the shuffle of languages and $\mathrm{DL}(\_,\_)$ the Dyck language with matching parenthesis as specified. Intuitively, any word in $\mathrm{SDL}_k$ contains of $k$ properly nested words of parentheses interleaved arbitrarily; for instance, $[_3 [_1 [_1 [_3 [_2 ]_1 ]_3 ]_2 [_1 ]_1 [_2 ]_1 ]_3 ]_2\in \mathrm{SDL}_3$.

Fact 0: $\mathrm{HAL}_1^{(k)} \subseteq \mathrm{HAL}_1^{(k+1)}$ for $k\geq 1$

Claim 1: $\mathrm{SDL}_k \in \mathrm{HAL}_1^{(k)}$ for $k\geq 1$

Claim 2: $\mathrm{SDL}_{k+1} \notin \mathrm{HAL}_1^{(k)}$ for $k\geq 1$ (the claim is wrong; see below)

Together, fact and claims show that $\mathrm{HAL}_1^{(k)} \subset \mathrm{HAL}_1^{(k+1)}$ and $\mathrm{HAL}_1^{(k)} \subset \mathrm{RE}$ for for $k\geq 1$.

---

Ad Claim 1: It is clear that $\mathrm{DL}([,]) \in \mathrm{HAL}_1$; min-heaps can implement a counter that is increased by one on $[$ and decreased by one on $]$. A word is accepted if and only if the counter never becomes negative and is zero at the end.

The same principle is used for $\mathrm{SDL}_k$ on a $k$-heap automaton; we maintain one counter per parenthesis type on a dedicated heap each and accept if and only if no counter becomes negative and all counters are zero at the end.

Ad Claim 2: This is more a sketch. In order to accept $\mathrm{SDL}_{k+1}$ an automaton has to be able to check at any time wether $]_i$ is allowed next for any $i=1,\dots,k+1$. As nesting depth and "shuffle depth" are unbounded, finite control can not do this (not even for one parenthesis type). Since a $k$-heap automaton can only access $k$ bits of (heap) information at any time, it has no way of doing the necessary checks.

---

---

Claim 2 is in fact false. We have to be remember that type-1 heap automata can essentially store a finite amount of counters but can only access the top most. With two heaps, we can access all counters of the first heap: if we want to access counter $i$, move the symbols encoding counters $1,\dots,i-1$ to the second heap, access counter $i$ and move everything back. That leads us to the following claims:

Claim I: $\mathrm{HAL}_1 \subset \mathrm{HAL}_1^{(2)}$

Claim II: $\mathrm{HAL}_1^{(2)} = \mathrm{HAL}_1^{(3)} = \dots$

Claim I follows from above reasoning with $\mathrm{SDL}_2$. Claim II holds because $k$-heap automata can only manage finitely many counters, no matter the $k$, which can be simulated by a $2$-heap automata as outlined above.

This train of thought leads us to

Claim III: $\mathrm{HAL}_1^{(2)} \subset RE$

as Turing machines can handle unbounded numbers of counters, outclassing $2$-heap automata. As a concrete example, consider

$\qquad \displaystyle \mathrm{SDL} = \bigcup\limits_{k\geq 1} \mathrm{SDL}_k.$

Note that $\mathrm{SDL}$ can be expressed using a finite alphabet by encoding $[_i$ as e.g. $[\{\overline{i}\}$ with $\overline{i}$ the binary representation of $i$ and $]_i$ similarly.