A categorical model for 2-PDAs with states

Jürgen Koslowski

Abstract

Having recently established that deterministic push-down automata with two stacks (2PDAs) and a single state suffice to simulate Turing machines, we now turn to describing a categorical model for such machines, even those with states.

Recall that labeled transition systems (LTSs), which equipped with with initial and final states and under suitable finiteness constraints form the basis for finite automata, can be viewed either as graph morphisms into a fixed target graph Σ (usually a graph with just a single node, in case of formal language theory), or, alternatively, as a graph morphism from Σ into the 2-category rel of sets and relations.

In 1989, Bob Walters used morphisms of multigraphs into a specific target to categorify a certain variant of context-free grammars (sufficiently strong to capture all context-free languages).

By looking at a slightly larger class of context-free grammars and changing the point of view from multigraphs to co-multigraphs (cm-graphs, for short), a connection can be made between these context-free grammars (CFGs) and certain restricted push-down automata (PDAs). The latter may be viewed as CFGs with the additional constraint that rewriting can only happen at the end of the stack, the ``current position'', hence they are not very interesting for computer scientists.

However, when two stacks are involved, which we think of as being juxtaposed at their respective current positions, the possibility of moving this position is not only a very powerful extension to the capabilities of ordinary PDAs, but in addition has a very succinct categorical interpretation in terms of adjoints in cm-graphs. The previous observation that states and storage are orthogonal concepts for 2PDAs (not so for Turing machines!) then is reflected in the step from cm-graphs to fc-cm-graphs (a kind of double graphs analogous to fc-multicategories). Hence, from a rather different angle we arrive at a model with close connections to the tile model of Gadducci and Montanari.

It remains to be seen whether the alternative view of LTSs (as graph morphisms into rel) can be evolved in a similar fashion.