Convergence and Diversity in the Control Hierarchy

Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 7597–7616 July 9-14, 2023 ©2023 Association for Computational Linguistics Convergence and Diversity in the Control Hierarchy Alexandra Butoi1 Ryan Cotterell1 David Chiang2 1ETH Zürich 2University of Notre Dame {alexandra.butoi, ryan.cotterell}@inf.ethz.ch dchiang@nd.edu Abstract Weir has defined a hierarchy of language classes whose second member (L2) is gener- ated by tree-adjoining grammars (TAG), linear indexed grammars (LIG), combinatory catego- rial grammars, and head grammars. The hi- erarchy is obtained using the mechanism of control, and L2 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 characteriza- tions of L2 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 embed- ded 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. 1 Introduction Weir (1992) defined a hierarchy of formal lan- guages whose first level (L1) is the class of context- free languages, and whose second level (L2) is the class generated by several existing formalisms: tree-adjoining grammars (Joshi et al., 1975), lin- ear indexed grammars (Gazdar, 1988), combina- tory categorial grammars (Steedman, 1987) and head grammars (Pollard, 1984), which were proven weakly equivalent in a classic paper (Joshi et al., 1991; Vijay-Shanker and Weir, 1994), and embed- ded pushdown automaton (EPDA) as well (Vijay- Shanker, 1987). Weir’s hierarchy is obtained using the mecha- nism of control, and L2 is obtained by using a CFG ⊲ CFG CFG ⊲ PDA PDA ⊲ CFG PDA ⊲ PDA spinal TAG LIG EPDA spinal PAA Figure 1: Overview of results. “푋 ⊲ 푌” means “푋 controlling 푌.” Thin lines indicate d-weak equivalence, while thick lines indicate d-strong equivalence. context-free grammar (CFG) to control another modified CFG, called a labeled distinguished CFG or LD-CFG. Here, we define a controllable push- down automaton (PDA), called a labeled distin- guished PDA (LD-PDA), and show that PDAs can also be used as controllers. By combining a con- troller CFG or PDA with a controlled LD-CFG or LD-PDA, we obtain a total of four formalisms that characterize L2. We show that these four formalisms are not only weakly equivalent but equivalent in a stricter sense that we call d-weak equivalence. Furthermore, us- ing an even stricter notion of equivalence called d-strong equivalence, we make precise the intuition that a CFG controlling a CFG is …

Content truncated to 500 words