# Determining capabilities of a min-heap (or other exotic) state machines

See the end of this post for some clarification on the definition(s) of min-heap automata.

One can imagine using a variety of data structures for storing information for use by state machines. For instance, push-down automata store information in a stack, and Turing machines use a tape. State machines using queues, and ones using two multiple stacks or tapes, have been shown to be equivalent in power to Turing machines.

Imagine a min-heap machine. It works exactly like a push-down automaton, with the following exceptions:

1. Instead of getting to look at the last thing you added to the heap, you only get to look at the smallest element (with the ordering defined on a per-machine basis) currently on the heap.
2. Instead of getting to remove the last thing you added to the heap, you only get to remove one of the smallest element (with the ordering defined on a per-machine basis) currently on the heap.
3. Instead of getting to add an element to the top of the heap, you can only add an element to the heap, with its position being determined according to the other elements in the heap (with the ordering defined on a per-machine basis).

This machine can accept all regular languages, simply by not using the heap. It can also accept the language $\displaystyle \{a^{n}b^{n} \in \{a, b\}^{*} \mid n \ge 0\}$ by adding $a$'s to the heap, and removing $a$'s from the heap when it reads $b$'s. It can accept a variety of other context-free languages. However, it cannot accept, for instance, $\displaystyle \{w \in \{a, b\}^{*} \mid w = w^{R}\}$ (stated without proof). EDIT: or can it? I don't think it can, but I've been surprised before, and I'm sure I'll keep being surprised when my assumptions to keep making of me an... well.

Can it accept any context-sensitive or Turing-complete languages?

More generally, what research, if any, has been pursued in this direction? What results are there, if any? I am also interested in other varieties of exotic state machines, possibly those using other data structures for storage or various kinds of restrictions on access (e.g., how LBAs are restricted TMs). References are appreciated. I apologize in advance if this question is demonstrating ignorance.

Formal Definition:

I provide some more detailed definitions of min-heap automata here in order to clarify further discussion in questions which reference this material.

We define a type-1 nondeterministic min-heap automaton as a 7-tuple $$(Q, q_0, A, \Sigma, \Gamma, Z_0, \delta)$$ where...

1. $Q$ is a finite, non-empty set of states;
2. $q_0 \in Q$ is the initial state;
3. $A \subseteq Q$ is the set of accepting states;
4. $\Sigma$ is a finite, non-empty input alphabet;
5. $\Gamma$ is a finite, non-empty input alphabet, where the weight of a symbol $\gamma \in \Gamma$, $w(\gamma) \in \mathbb{N}$, is such that $w(\gamma_1) = w(\gamma_2) \iff \gamma_1 = \gamma_2$;
6. $Z_0 \notin \Gamma$ is the special bottom-of-the-heap symbol;
7. $\delta : Q \times (\Sigma \cup \{\epsilon\}) \times (\Gamma \cup \{Z_0\}) \rightarrow \mathcal{P}({Q \times \Gamma^*})$ is the transition function.

The transition function works by assuming an initially empty heap consisting of only $Z_0$. The transition function may add to the heap an arbitrary collection (finite, but possibly empty or with repeats) of elements $\gamma_1, \gamma_2, ..., \gamma_k \in \Gamma$. Alternatively, the transition function may remove an instance of the element $\gamma$ with the lowest weight $w(\gamma)$ of all elements remaining on the heap (i.e., the element on top of the heap). The transition function may only use the top-most (i.e., of minimal weight) symbol instance in determining any given transition.

Further, define a type-1 deterministic min-heap automaton to be a type-1 nondeterministic min-heap automaton which satisfies the following property: for all strings $x{\sigma}y \in \Sigma$ such that $|x| = n$ and $\sigma \in \Sigma$, $|\delta^{n+1}(q_0, x{\sigma}y, Z_0)| \leq 1$.

Define also a type-2 nondeterministic min-heap automaton exactly the same as a type-1 nondeterministic min-heap automaton, except for the following changes:

1. $\Gamma$ is a finite, non-empty input alphabet, where the weight of a symbol $\gamma \in \Gamma$, $w(\gamma) \in \mathbb{N}$, is such that $w(\gamma_1) = w(\gamma_2)$ does not necessarily imply $\gamma_1 = \gamma_2$; in other words, different heap symbols can have the same weight.
2. When instances of distinct heap symbols with same weight are added to the heap, their relative order is preserved according to a last-in, first-out (LIFO) stack-like ordering.

Thanks to Raphael for pointing out this more natural definition, which captures (and extends) the context-free languages.

Some results demonstrated so far:

1. Type-1 min-heap automata recognize a set of languages which is neither a subset nor a superset of the context-free languages. [1,2]
2. Type-2 min-heap automata, by their definition, recognize a set of languages which is a proper superset of the context-free languages, as well as a proper superset of the languages accepted by type-1 min-heap automata.
3. Languages accepted by type-1 min-heap automata appear to be closed under union, concatenation, and Kleene star, but not under complementation [1], intersection, or difference;
4. Languages accepted by type-1 nondeterministic min-heap automata appear to be a proper superset of languages accepted by type-1 deterministic min-heap automata.

There may be a few other results I have missed. More results are (possibly) on the way.

Follow-up Questions

1. Closure under reversal? -- Open
2. Closure under complementation? -- No!
3. Does nondeterminism increase power? -- Yes?
4. Is $HAL \subsetneq CSL$ for type-2? -- Open
5. Does adding heaps increase power for type-1? -- $HAL^1 \subsetneq HAL^2 = HAL^k$ for $k > 2$ (?)
6. Does adding a stack increase power for type-1? -- Open
• Great question by the way. I am tempted to dig for a pumping lemma for these automata. – Raphael Mar 7 '12 at 23:21
• @Raphael: I think you can use my (updated) proof for such a lemma: any language for which you need to 'remember' more than a linear amount of information in some substring in order to match a subsequent substring correctly cannot be parsed by min-heap automata. I'm not sure if a true pumping-style lemma is possible - it might end up being a special case of my lemma as well. – Alex ten Brink Mar 8 '12 at 13:40
• @AlextenBrink As combinations of heap symbol numbers can be used to encode stuff, I am not sure a linear bound suffices. – Raphael Mar 8 '12 at 18:31

You can recognize the canonical non-context-free (but context-sensitive) language $\{ a^n b^n c^n\ |\ n \geq 1 \}$ with this type of state machine. The crux is that you add tokens to the heap for every $a$ character, and while parsing the $b$ characters, you add 'larger' tokens to the heap, so they only end up at the bottom of the heap when you have parsed all the $b$ characters.

Heap symbols are $a$ and $b$, where $a < b$. We consume all the $a$ symbols on the input and add $a$ symbols to the heap. If we encounter a $b$, we switch strategies: for every $b$ we encounter subsequently we remove an $a$ from the heap and add a $b$ to the heap. When we encounter a $c$ we should have run out of $a$s to remove, and then for every $c$ in the remaining input we remove a $b$ from the heap. If the heap is empty at the end, the string is in the language. Obviously, we reject if something goes wrong.

Update:

The language $EPAL = \{ ww^R | w \in \{a, b\}^* \}$ can not be recognized by min-heap automata. Suppose that we do have a min-heap automaton that can recognize $EPAL$. We look at the 'state' the automaton is in after reading $w$ (the first part of the input, so $w^R$ is next). The only state we have are the contents of the heap and the particular state of the automaton it is in. This means that after recognizing $w$, this 'state' needs to hold enough information to match $w^R$.

In particular, in order to do this, there must be $2^n$ possible different 'state's (where $n = |w|$), as there are $2^n$ possible words consisting of $a$ and $b$ characters. As there are only a finite number of states and only a finite number of heap characters, this implies that there exists some word $w$ for which the heap contains an exponential number of some heap character, say $x$.

We first prove the theorem for deterministic min-heap automata, and then extend this proof to non-deterministic min-heap automata. In particular, deterministic automata that recognize some language will not put themselves in an infinite loop, which is a useful property.

We shall prove that the heap can only contain at most a number of heap tokens that is linear in the number of characters read from the input. This immediately rules out that $x$ appears an exponential number of times on the heap, which completes the proof that $EPAL$ can not be recognized by min-heap automata.

Because we only have a finite number of states in our automaton and because a deterministic automaton will not put itself into an infinite loop, on reading an input signal it will add at most a constant number of heap characters onto the heap. Similarly, on consuming some heap symbol $y$, it can only add at most a constant number of heap characters that are strictly larger than $y$ and it can only decrease the number of $y$ symbols on the stack (otherwise we get an infinite loop).

Consuming heap symbols may therefore cause an (enormous) buildup of larger heap symbols, but as there are only a constant number of different types of heap symbols, this is only a constant number not dependent on $n$. This implies that the number of heap symbols is at most some (large) constant times the number of input symbols read so far. This completes the proof for the deterministic case.

In the non-deterministic case, the proof is similar, but a bit trickier: instead of adding at most some constant number of heap tokens to the heap, it adds some arbitrary number of heap tokens to the heap. However, the crucial point is that this number does not depend on $n$. In particular, if we can non-deterministically get exactly the right heap symbols on the heap after recognizing $w$ (right for recognizing $w^R$), we can also non-deterministically choose the heap symbols that match some other word $w'$, and thereby recognize $w w'^R$, thus contradicting that the min-heap automaton recognizes exactly $EPAL$.

Update 3: I'll make the last argument (about non-determinism) rigorous. By the above argument, there must exist an infinite set of words $W \subseteq \{a,b\}^*$ such that for every $w \in W$, after recognizing $w$, the heap contains $\omega(|w|)$ elements (note that we can talk about $O(f(|w|))$ as we have an infinite set of words). As we cannot get that many elements on the heap through deterministic means, we must have had some form of a loop in which we first non-deterministically chose to add more elements to the heap (without consuming input), and later chose to exit this loop, and we must have traversed this loop $\omega(1)$ times.

Take the set of all such loops used by $W$. As there are only $O(1)$ states, the size of this set is $O(1)$, and the set of all its subsets is also $O(1)$. Now note that the 'deterministic' part of the execution paths can only contribute to $O(|w|)$ of the tokens, which means that a lot of the exponential number of different words must have execution paths whose 'deterministic' parts contribute the same tokens to the heap. In particular, the only way to get more tokens is to take the loops we identified above.

Combining these observations, this means that there must be two distinct words in $W$, $w_1$ and $w_2$ say, whose 'deterministic' part of the execution paths contribute the same tokens to the heap, and that are differentiated by taking some subset of the loops above a different number of times, but that use the same subset of loops (remember there are only $O(1)$ of these loops).

We can now show that $w_1 w_2$ can also be recognized by the min-heap automaton: we follow the execution path for $w_1$ as above, but we traverse the loops the same number of times the execution path for $w_2$ traverses them. This fills the min-heap with tokens such that $w_2$ is accepted as suffix, thus completing the proof.

Update 2:

It just occurred to me that the above means that we can simulate a deterministic min-heap automaton using only logarithmic space: we keep a counter for every type of character in the min-heap. As shown above, this counter will at most be $O(n)$, and hence can be stored using only $O(\log n)$ space (as there are only a constant number of these counters). This gives us:

$\mathrm{DHAL} \subset \mathrm{L}$

$\mathrm{HAL} \subset \mathrm{NL}$

where $\mathrm{DHAL}$ is the set of languages recognized by some deterministic min-heap automaton.

• +1 for excellent insight, seems you have understood my meaning completely. Am I right in my assessment that such machines can't recognize palindromes? Since order of symbols added isn't preserved, it doesn't seem possible. – Patrick87 Mar 7 '12 at 22:51
• @Patrick87: I'm thinking about that problem right now :) – Alex ten Brink Mar 7 '12 at 22:59
• @Raphael Very cool observation concerning Turing machines with logarithmic resource constraints, both of you guys have done a fantastic job of investigating these automata. You know, I sort of just threw the min-heap automaton out as a kind of example of the thing I was interested in, but it seems to have been well-received. What other questions can be answered about such automata? Is DHAL = HAL? What are HAL's closure properties? Are further explorations worthwhile, and if so, should they remain here, or be put into a new question? Thanks again for the excellent insights. – Patrick87 Mar 8 '12 at 14:27
• @Raphael: I've made that part completely rigorous. You are right that $n$ must be sufficiently large - I glossed over some details left and right. – Alex ten Brink Mar 8 '12 at 20:00
• @Raphael: Indeed, it does. $CSL = NLINSPACE$, so $DHAL \subset CSL$ by the space hierarchy theorem and some inclusions. – Alex ten Brink Mar 16 '12 at 18:21

Here is what we (believe to) know:

• $\mathrm{HAL} \setminus \mathrm{CFL} \neq \emptyset$ (type-1, type-2)
• $\mathrm{CFL} \setminus \mathrm{HAL} \neq \emptyset$ (type-1)
• $\mathrm{CFL} \subseteq \mathrm{HAL}$ (type-2, by definition)
• $\mathrm{CSL} \setminus \mathrm{HAL} \neq \emptyset$ (type-1, type-2)

See details and some other notes below.

### $\mathrm{HAL} \setminus \mathrm{CFL} \neq \emptyset$

This part of the answer relates to both type-1 and type-2.

A min-heap automaton (HA) with finite, totally ordered heap alphabet accepts $L = \{ a^nb^nc^n \mid n \in \mathbb{N} \} \in \mathrm{CSL} \setminus \mathrm{CFL}$.

Assumptions: Similar to PDA, our transition function consumes the top most heap symbol and writes back an arbitrary number of heap symbols. The heap initially contains a distinguished symbol $\$$which is larger than all other heap symbols. Let A = (Q,\Sigma_I, \Sigma_H, \rightarrow, q_0, Q_F) a min-heap automaton with • Q = \{q_0, q_1, q_2, q_f\} the set of states • \Sigma_I = \{a,b,c\} the input alphabet. • \Sigma_H = {a,b,\} the heap alphabet with ordering a \lt b \lt \$$. •$Q_F = \{q_f\}$•$\rightarrow\ \subseteq (Q \times \Sigma_I \times \Sigma_H) \times (Q \times \Sigma_H^*)$with •$(q_0,a,\sigma) \rightarrow (q_0, a\sigma)$for all$\sigma \in \Sigma_H$•$(q_0,b,a) \rightarrow (q_1,b)$•$(q_1,b,a) \rightarrow (q_1,b)$•$(q_1,c,b) \rightarrow (q_2,\varepsilon)$•$(q_2,c,b) \rightarrow (q_2, \varepsilon)$•$(q_2,c,\$) \rightarrow (q_f, \varepsilon)$

The automaton writes one $a$ to the heap for every $a$ in the input. When a $b$ occurs, it consumes as many $b$ as there have been $a$, writing a $b$ to the heap for every found $b$. This does not disturb counting because the heap conveniently keeps $a$ on the top. Only after all $a$ are taken from the heap are $c$ accepted; only after as many $c$ as $b$ (and therewith as $a$) are found, does $A$ accept with empty heap and final state.

Therefore, $\cal{L}(A) = L$.

### $\mathrm{CFL} \setminus \mathrm{HAL} \neq \emptyset$

This part of the answer relates only to type-1.

Consider $\mathrm{EPAL} = \{ww^R \mid w \in \{a,b\}\}$ the set of even palindromes and assume there is HA $A$ with $\cal{L}(A) = L$.

Conjecture: we find $w_1, w_2 \in \{a,b\}^*$ with $w_1 \neq w_2$ and $|w_1| = |w_2|$ such that $A$ is in the same state and has the same heap content after reading $w_1$ and $w_2$, respectively. As $A$ accepts both $w_1w_1^R$ and $w_2w_2^R$, it therefore also accepts $w_1w_2^R \notin \mathrm{EPAL}$ (and $w_2w_1^R$), which is a contradiction to $\cal{L}(A) = \mathrm{EPAL}$.

### $\mathrm{CSL} \setminus \mathrm{HAL} \neq \emptyset$

This part of the answer relates to both type-1 and type-2.

The same reasoning we used on $\mathrm{EPAL}$ (for type-1) can be used to show that the context-sensitive language $\{ww \mid w \in \{a,b\}^*\}$ is not in $\mathrm{HAL}$.

### $\mathrm{HAL} \overset{?}{\subseteq} \mathrm{CSL}$

This is still open for both type-1 and type-2.

### Further Factoids

HA seem to be orthogonal to a subset of the mildly context-senstive languages accepted by Embedded Pushdown Automata: While HA can simulate a bounded number of stacked stacks, they can not simulate arbitrarily many (as EPA can). However, HA can access the top symbols of stacks currently not on the top (which EPA can not).

• +1, excellent response. Essentially equivalent to Brink's method, right? Still, the rigor and precision are outstanding. Have you given any thought to whether such machines can accept all CFLs? It seems impossible, since order information is lost by the heap... – Patrick87 Mar 7 '12 at 23:13
• It is the same idea Alex had, yes. Glad you can get something from it nonetheless. I added an idea for the other direction but there is a (huge?) gap. Need to think about it with a clear head tomorrow and maybe snipe some colleagues. – Raphael Mar 7 '12 at 23:16
• I feel like I should have included a proof of correctness in order to earn extra credits for rigor. ;) It should not be too hard by induction over $n$, I guess. – Raphael Mar 7 '12 at 23:18
• The proof outline you label as a conjecture is what I had in mind, and I find it pretty convincing... also, and this is a minor technical point, I think you're using the language of even-length palindromes, not all palindromes... though the proof certainly works either way (note that it also works for simple palindromes, so HAL is not even as strong as DPDAs, another result). – Patrick87 Mar 8 '12 at 0:28
• @Patrick87 The problem is that there may be more possible configurations a given HA can be in after reading $n$ symbols than there are words, in particular if we allow $\varepsilon$-transitions that put symbols on the heap. – Raphael Mar 8 '12 at 6:05