Convergence and Diversity in the Control Hierarchy (2023)

Abstract: Weir has defined a hierarchy of language classes whose second member (L2) 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 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 (called a labeled distinguished CFG) to give a definition of controllable pushdown automata (PDAs), called labeled distinguished PDAs. This yields three new characterizations 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 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 kind of automaton we know of, so we invent one and call it a Pushdown Adjoining Automaton (PAA).

## preliminaries let [ ] denote the set of integers {1, . . . , }, and let [ : ] denote the set of integers { , . . . , }. for any sets x and y, we write @xmath0, @xmath1. ## equivalence of formalisms we think of grammars and automata generically as "formal systems" that have derivation trees yielding strings. by equipping formal systems with derivation trees, we can define a notion of equivalence that is stricter than weak equivalence, and another notion that is more precise than strong equivalence. definition 4. a formal system f over alphabet σ is a set of derivation trees together with a yield function : example 1. consider two cfgs g fin and g inf : these grammars are weakly equivalent, but not dweakly equivalent, because g fin has just one derivation of a, but g inf has infinitely many, so there is no bijection between their derivation sets. although there is a standard method to remove unary productions @xmath2, on weighted grammars this method requires the semiring of weights to be complete; it will not work with general semirings. d-weak equivalence captures this distinction. strong equivalence is traditionally understood to mean that two formal systems generate the same sets of structural descriptions, but this notion cannot be made precise without defining what structural descriptions are. for our purposes, it will suffice to use derivation trees, thought of as unlabeled, unordered trees. definition 6. two formal systems f and f are d-strongly equivalent if there is a bijection between the derivation trees of f and f such that for any derivation tree of f, and ( ) are isomorphic as unlabeled, unordered trees, and and in general, cfg and pda are d-weakly equivalent (app. d, prop. 7), but not d-strongly equivalent. ## control after a number of formalisms were proven to be equivalent characterizations of a language class l 2 that is slightly more powerful than context-free languages (cfls), @xcite introduced the control hierarchy to characterize an infinite sequence of language classes, starting with cfls and l 2 . the essential idea is that l 2 languages can be recognized by a cfg in which the productions do not apply freely, but are controlled by another cfg. ## derivation trees of two-level formalisms in order to show that our four two-level formalisms are d-strongly equivalent to other l 2 formalisms, we need to establish what derivation trees look like in these formalisms. weir actually gives two definitions of derivation in a two-level grammar. the first is the one we have reproduced above, where a partial control word is written inside the square brackets. the second runs a leftmost derivation of the controller cfg inside the square brackets. in this section, we follow this second approach, except that we use derivation trees, not leftmost derivations. we give a separate definition for each twolevel formalism. ideally, these definitions would have followed "for free" from the definitions of derivation trees of (ld-)cfgs and (ld-)pdas, but we save this level of generality for future work. fig. 3 shows the derivation of string aabbccdd under the four two-level formalisms considered in this paper. the rest of this section discusses each formalism in turn. we assume all controllers and controllees are in normal form; see app. c for the general case. pda ⊲ pda for pda, derivations and derivation trees are the same thing, so derivation trees of pda ⊲ pda follow weir's definition straightforwardly. there are three cases to consider. cfg ⊲ cfg when the controller is a cfg and therefore has branching derivation trees, the controllee's derivation becomes fragmented. to ensure that the fragments form one correct derivation, we need to add some extra information to the derivation nodes: each node is labeled x /z[a], where a is a controller nonterminal, and x and z are controllee nonterminals or ⊥. we write x /⊥[a] as x [a]. moreover, the yield of a subderivation is in general a discontinuous string. we write * to indicate a hole in a string (meant to resemble foot nodes in tag), and we write ( ) to plug into the first hole in ; that is, @xmath3, then ( ) = 1 2 . the yield is . cfg ⊲ pda the derivation trees of cfg ⊲ pda are the most complicated. to cut down on complexity, we make use of the fact that every pda that accepts by empty stack is equivalent to one with only one state @xcite , and indeed the equivalence is d-strong (app. a, prop. 6). therefore, we assume that the controllee has just one state, . derivation nodes are labeled ( , ), where is a state and is a string of symbols of the form x /z[a] (as above, for cfg ⊲ cfg) or * . the yield of the parent is just the yield of the child. (c) if a derivation node is labeled , x /z[a] , and @xmath4, then the reader may be surprised that is placed on the leftmost child. it would be equally sensible to place it on any of the children, but the leftmost child makes the yield function simplest. ## correspondences with l 2 formalisms we can now show how pda ⊲ pda, pda ⊲ cfg, and cfg ⊲ cfg are d-strongly equivalent to epda, lig, and tag, respectively, and to introduce paa, which is d-strongly equivalent to cfg ⊲ pda. ## conclusion we introduced new notions of equivalence between formalisms, d-weak equivalence and dstrong equivalence, that allow for finer-grained comparisons than weak equivalence. by extending weir's idea of control to pdas, we obtained three new formalisms recognizing l 2 , all d-weakly equivalent to weir's original two-level grammar. but by nuancing the idea of control to account for the difference between cfg derivations and derivation trees, we showed that they are not d-strongly equivalent. instead, three of them are d-strongly equivalent to existing l 2 formalisms, namely tag, lig and epda, and the fourth is d-strongly equivalent to our new l 2 formalism, paa.