# Proving closure under complementation of languages accepted by min-heap automata

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 the regular languages are closed under a variety of operations (we may limit ourselves to basic operations such as union, intersection, complement, difference, concatenation, Kleene star, and reversal), whereas the context-free languages have different closure properties (these are closed under union, concatenation, Kleene star, and reversal).

Is HAL closed under complementation?

Claim: $\mathrm{HAL}$ is not closed against complement.

Proof Idea: We have agreed that $\mathrm{EPAL}$ (the language of even palindromes over a non-unary alphabet) is not in $\mathrm{HAL}$. We show that $\overline{\mathrm{EPAL}} \in \mathrm{HAL}$.
This works for type-1 only (as type-2 can accept $\mathrm{EPAL}$); the proof can be adapted to suit type-2 though, see below.

Proof: Note that

\qquad \displaystyle \begin{align*} \overline{\mathrm{EPAL}} &= \{vw : |v|=|w|, v\neq w^R\} \\ &\cup\ \,\{w : |w| \in 2\mathbb{N}\!+\!1\} \end{align*}

We construct a min-heap automaton with two heap symbols $b < a$ that works like this:

• In the starting state, decide nondeterministically wether the input's length is even.
• On the uneven path, use finite control to accept the input if and only if its length is odd.
• On the even path, proceed like this: $$\underbrace{v_1\ \dots\ \mathbf{v_{i}}}_{+a}\ \underbrace{v_{i+1}\ \dots\ v_n}_{+b}\ \underbrace{w_n\ \dots\ w_{i+1}}_{-b}\ \underbrace{\mathbf{w_i}\ \dots\ w_1}_{-a}$$
• Start by adding one $a$ to heap for every read symbol.
• At a nondeterministically determined position, store the current symbol in finite control and start adding one $b$ (and no $a$) to heap for every read symbol.
• At a nondeterministically determined position, stop adding symbols and consume one $b$ per input symbol.
• When all $b$ are consumed, compare the current symbol with the one stored in control. If they are unequal, continue; else reject the input.
• Consume one $a$ per input symbol. If the heap is empty at the same time the input ends, accept the word; reject otherwise.

The described min-heap automaton accepts $\overline{\mathrm{EPAL}}$. As its complement, $\mathrm{EPAL}$, is not in $\mathrm{HAL}$, we have proven the claim.

Note: The proof can be performed in the same way with $\{ww \mid w \in \{a,b\}^*\}$ (which is in $\mathrm{CSL} \setminus \mathrm{HAL}$) and its complement. This extends above result to type-2.

• +1 Very good answer, for the type-1 (original definition) min-heap automata. With this, given the relatively simple argument which I think shows that languages accepted by type-1 min-heap automata are closed w.r.t. union, we also know that the set of languages accepted by type-1 min-heap automata is not closed under intersection or difference, from similarly simple arguments. I will give this a day or so and then accept, just to give other people a chance to visit and, possibly, provide other answers... Also, what about type-2 min-heap automata (i.e., the more natural version you suggested)? – Patrick87 Mar 15 '12 at 14:32
• Wow, man, you are a cool dude. – Patrick87 Apr 24 '12 at 21:02