8
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +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)? $\endgroup$ – Patrick87 Mar 15 '12 at 14:32
  • $\begingroup$ Wow, man, you are a cool dude. $\endgroup$ – Patrick87 Apr 24 '12 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.