A categorical model for 2-PDAs with states
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.