Convergence and Diversity in the Control Hierarchy
Alexandra Butoi Ryan Cotterell David Chiang
Weir has defined a hierarchy of language classes whose second member
($\mathcal{L}_2$) is generated by tree-adjoining grammars (TAG), linear indexed
grammars (LIG), combinatory categorial grammars, and head grammars. The
hierarchy is obtained using the mechanism of control, and $\mathcal{L}_2$ is
obtained using a context-free grammar (CFG) whose derivations are controlled by
another CFG. We adapt Weir's definition of a controllable CFG to give a
definition of controllable pushdown automata (PDAs). This yields three new
characterizations of $\mathcal{L}_2$ as the class of languages generated by
PDAs controlling PDAs, PDAs controlling CFGs, and CFGs controlling PDAs. We
show that these four formalisms are not only weakly equivalent but equivalent
in a stricter sense that we call d-weak equivalence. Furthermore, using an even
stricter notion of equivalence called d-strong equivalence, we make precise the
intuition that a CFG controlling a CFG is a TAG, a PDA controlling a PDA is an
embedded PDA, and a PDA controlling a CFG is a LIG. The fourth member of this
family, a CFG controlling a PDA, does not correspond to any formalism we know
of, so we invent one and call it a Pushdown Adjoining Automaton.