10
$\begingroup$

In the context of our investigation of heap automata, I would like to prove that a particular variant can not accept non-context-sensitive languages. As we have no equivalent grammar model, I need a proof that uses only automata; therefore, I have to show that heap automata can be simulated by LBAs (or an equivalent model).

I expect the proof to work similarly to showing that pushdown automata accept a subset the context-sensitive languages. However, all proofs I know work by

  • using grammars -- here the fact is obvious by definition -- or
  • are unconvinvingly vague (e.g. here).

My problem is that a PDA (resp. HA) can contain cycles of $\varepsilon$-transitions that may write symbols to the stack (resp. heap). An LBA can not simulate arbitrary iterations of such loops. From the Chomsky hierarchy obtained with grammars, we know that

  1. every context-free language has an $\varepsilon$-cycle-free PDA or
  2. the simulating LBA can prevent iterating $\varepsilon$-cycles too often.

Intuitively, this is clear: such cycles write symbols independently of the input, therefore the stack (heap) content does only hold an amount of information linear in the length of the cycle (disregarding overlapping cycles for now). Also, you don't have a way to get rid of the stuff again (if you need to) other than using another $\varepsilon$-cycle. In essence, such cycles do not contribute to dealing with the input if iterated multiple times, so they are not necessary.

How can this argument be put rigorously/formally, especially considering overlapping $\varepsilon$-cycles?

$\endgroup$
  • $\begingroup$ I don't know why you state that $\epsilon$-cycles have bounded length, for non-deterministic PDAs it is certainly possible to have an infinite cycle, of which the automaton can break out. Or am I misunderstanding something fundamental? $\endgroup$ – vonbrand Jan 29 '13 at 1:23
  • $\begingroup$ It is clear that they can have them, but by the inclusion of CFL in CSL they can not be "necessary". $\endgroup$ – Raphael Jan 29 '13 at 14:09
  • $\begingroup$ the problem is that the proof outline states they don't exist. $\endgroup$ – vonbrand Feb 8 '13 at 23:35
  • 1
    $\begingroup$ Ran's answer over here seems relevant; he directly shows that a PDA without $\varepsilon$-transitions exists. However, he needs grammars after all, so the technique does not carry over to heap automata. $\endgroup$ – Raphael Apr 15 '13 at 7:28
  • $\begingroup$ This is only a vague idea at the moment, but can't you use a nondeterministic LBA, and use the nondeterminism to break the cycle at the right step (in the same way a PDA does)? $\endgroup$ – Luke Mathieson Jun 3 '15 at 11:24
3
$\begingroup$

The removal of $\varepsilon$-transitions has been studied for the more general model of valence automata by Zetzsche [1]. Valence automata are essentially finite automata with a monoid for storage.

Among other things, Zetzsche shows that for monoids $M$ from a rich class $\mathcal{C}$ of monoids (which contains (partially) blind counters, stacks, and combinations thereof), $\varepsilon$-free $M$-automata accept the same class of languages as $M$-automata.

Since PDAs with a $k$-symbol stack alphabet correspond to valence automata over monoid $\mathbb{B}^{(k)} \in \mathcal{C}$ ($\mathbb{B}$ is the bicyclic monoid), the result from Theorem 1 (resp. 7.1 in the preprint) applies here.

The proof is long and technical; the proofs of lemmas 8 and 10 (resp. 7.6 and 7.9) contain the relevant constructions. Note that while they do not use grammar models (as required in the question) they do use valence transducers.


  1. Silent Transitions in Automata with Storage by G. Zetzsche (2013) [more elaborate preprint on arXiv]
$\endgroup$
  • $\begingroup$ FWIW, these results do not seem to carry over to heap automata as their storage mechanism does not correspond to a monoid, at least not of the forms Zetzsche studied. $\endgroup$ – Raphael Mar 10 '16 at 21:21

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.