[Solved]: Proving closure under complementation of languages accepted by min-heap automata

Problem Detail: 

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?

Asked By : Patrick87

Answered By : Raphael

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/393