Strong Equivalence of TAG and CCG (2021)

Abstract: Tree-adjoining grammar (TAG) and combinatory categorial grammar (CCG) are two well-established mildly context-sensitive grammar formalisms that are known to have the same expressive power on strings (i.e., generate the same class of string languages). It is demonstrated that their expressive power on trees also essentially coincides. In fact, CCG without lexicon entries for the empty string and only first-order rules of degree at most 2 are sufficient for its full expressive power.

## introduction combinatory categorial grammar (ccg) @xcite is one of several grammar formalisms that were introduced as an extension of context-free grammars. in particular, ccg extends the classical categorial grammar @xcite , which has the same expressivity as context-free grammar, by rules that are inspired by combinatory logic @xcite . ccg is a mildly context-sensitive grammar formalism @xcite . contextsensitive grammar formalisms are formalisms that are efficiently parsable (i.e., in polynomial time) and have expressivity beyond the contextfree languages. they are able to express a limited amount of cross-serial dependencies and have the constant growth property. because of these features and its notion of syntactic categories, which is quite intuitive for natural languages, ccg has become widely applied in compuational linguistics @xcite . further, it can be enhanced by semantics through the lambda calculus. ccg is based on a lexicon and a rule system. the lexicon assigns syntactic categories to the symbols of an input string and the rule system describes how neighboring categories can be combined to new categories. each category has a target, which is similar to the return type of a function, and optionally, a number of arguments. different from functions, each argument has a directionality that indicates if it is expected on the left or the right side. if repeated combination of categories leads to a (binary) derivation tree that comprises all input symbols and is rooted in an initial category, then the input string is accepted. when defining ccg, there are many degrees of freedom yielding a number of different variants @xcite @xcite . this is a consequence of the linguistically motivated need to easily express specific structures that have been identified in a particular theory of syntax for a given natural language. however, we and others @xcite are interested in the expressive power of ccgs as generators of formal languages, since this allows us to disentangle the confusion of subtly different formalisms and identify the principal structures expressible by a common core of the formalisms. as linguistic structure calls for a representation that goes beyond strings, we aim for a characterization of expressive power in terms of the generated trees. the most famous result on the expressive power of ccg is by @xcite , showing that tree-adjoining grammar (tag), linear-indexed grammar (lig), head grammar (hg), and ccg generate the same string languages. an equivalent automaton model is the embedded push-down automaton @xcite . in the definition of ccg used by @xcite , the lexicon allows ε-entries, which assign syntactic categories to the empty string ε. their rule system restricts rules to specific categories and limits the rule degree. ccg with unbounded rule degree are turingcomplete @xcite . prefix-closed ccg without target restrictions, in which the rules obey special closure properties, are less powerful. this even holds for multimodal ccgs @xcite , which allow many types of directionality indicators (i.e., slashes). when going beyond the level of string languages, there exist different notions of strong generative power. we consider two formalisms as strongly equivalent if their generated derivation tree languages coincide modulo relabelings. for example, the well-known local and regular tree grammars @xcite are strongly equivalent. on the other hand, @xcite regard two formalisms as strongly equivalent if they capture the same sets of dependencies. then there exist specific scrambling cases whose dependencies can be expressed by their ccg, but not by lexicalized tag (ltag). their ccg are syntactically more expressive than ours and allow type-raising, whereas the strong generative capacity (in our sense) of ltag is strictly smaller than that of tag @xcite . the dependencies expressed by ccg without rule restrictions and tag are shown to be incomparable by @xcite . returning to our notion of strong generative capacity, @xcite investigated the tree-generative capacity of ccg without ε-entries. the generated trees are always binary. ccg with application and first-degree composition rules generate exactly the regular tree languages @xcite . without the composition rules, only a proper subset can be generated. the languages of ccg rule trees (i.e., trees labeled by applied rules instead of categories) with bounded rule degree can also be generated by simple monadic context-free tree grammar (scftg). for the converse direction, we show that the tree languages generated by scftg can also be generated by ccg, which shows strong equivalence. this answers several open questions. since scftg and tag are strongly equivalent @xcite , our result also shows strong equivalence of ccg and tag. in contrast to the construction of @xcite , which relies heavily on ε-entries, our construction avoids them and shows that they do not increase the expressive power of ccg. additionally, we only use rules up to degree 2 and first-order categories (i.e., arguments are atomic), which shows that larger rule degree or higher-order categories do not increase the expressive power. our construction proceeds roughly as follows. we begin with a spine grammar, which is a variant of scftg that is also strongly equivalent to tag. we encode its spines using a context-free grammar, which in turn can be represented by a special variant of push-down automata. finally, the runs of the push-down automaton are simulated by a ccg such that the stack operations of the automaton are realized by adding and removing arguments of the categories. ## preliminaries the nonnegative integers are n. for every @xmath0, we let [k] = {@xmath1. the set σ * contains all strings over the finite set σ including the empty string ε. we let σ + = σ * \ {ε}. the length of @xmath2, and concatenation is written as juxtaposition. the prefixes pref(w) of a a string language is a subset l ⊆ σ * . given a relation ⇒ ⊆ s 2 , we let ⇒ * be the reflexive, transitive closure of ⇒. ## push-down automata we start by introducing a moore variant of pushdown automata @xcite ) that is geared towards our needs and still accepts the context-free languages (of strings of @xmath3. it will be similar to the push-down moore machines of @xcite . instead of processing input symbols as part of transitions (as in mealy machines), moore machines output a unique input symbol in each state @xcite . for every set γ, we let γ ≤1 = {ε} ∪ γ and γ ≥2 = {@xmath4, respectively. definition 2. a moore push-down automaton (mpda) @xmath5, σ, γ, δ, τ, i, f ) consists of (i) finite sets q, σ, and γ of states, input symbols, and stack symbols, respectively, (ii due to the definition of δ, in a single step we can either push or pop a single stack symbol or ignore the stack. note that we explicitly exclude the case where a symbol is popped and another symbol is pushed at the same time. in the following, let @xmath6, σ, γ, δ, τ, i, f ) be an mpda. on the set and a configuration q, α ∈ conf a is initial (respectively, final) if @xmath7, @xmath8. an accepting run is a sequence ξ 0 , . . . , ξ @xmath9.e., ξ i-1 a ξ i for all @xmath10, starts with an initial configuration ξ 0 , and finishes in a final configuration ξ n . in other words, we can start in an initial state with an arbitrary symbol on the stack and finish in a final state with the empty stack, and for each intermediate step there has to exist a transition. the language accepted by a contains exactly those strings @xmath11, for which there exists an accepting thus, we accept the strings that are output symbol-by-symbol by the states attained during an accepting run. as usual, two mpda are equivalent if they accept the same language. since no initial configuration is final, each accepting run has length at least 2, so we can only accept strings of length at least 2. while we could adjust the model to remove this restriction, the presented version serves our later purposes best. theorem 3. mpda accept the context-free languages of strings of length at least 2. the mpda a is pop-normalized if there exists a map pop : γ → q such that @xmath12, γ, ε, q ) ∈ δ. in other words, for each stack symbol γ ∈ γ there is a unique state pop(γ) that the mpda enters whenever γ is popped from the stack. later on, we will simulate the runs of an mpda in a ccg such that subsequent configurations are represented by subsequent primary categories. popping transitions are modeled by removing the last argument of a category. thus, the target state has to be stored in the previous argument. this argument is added when the according pushing transition is simulated, so at that point we already have to be aware in which state the mpda will end up after popping the symbol again. this will be explained in more detail in section 7. we can easily establish this property by storing a state in each stack symbol. each pushing transition is replaced by one variant for each state (i.e., we guess a state when pushing), but when a symbol is popped, this is only allowed if the state stored in it coincides with the target state. lemma 4. for every mpda we can construct an equivalent pop-normalized mpda. the next statement shows that we can provide a form of look-ahead on the output. in each new symbol we store the current as well as the next output symbol. standard techniques can be used to prove the statement. we will briefly sketch why this look-ahead is necessary. before constructing the ccg, the mpda will be used to model a spine grammar. the next output symbol of the mpda corresponds to the label of the parent node along a so-called spine of a tree generated by the spine grammar. from this parent node we can determine the possible labels of its other child. this information will be used in the ccg to control which secondary categories are allowed as neighboring combination partners. lemma 5. for every context-free language l ⊆ σ * and / ∈ σ, the language next(l) is context-free, where corollary 6. for every context-free language l ⊆ σ ≥2 there exists a pop-normalized mpda a such that l(a) = next(l). ## spine grammars now we move on to representations of tree languages. we first recall context-free tree grammars @xcite , but only the monadic simple variant @xcite . definition 7. a simple monadic context-free tree grammar (scftg) is a tuple @xmath13, σ, s, p ) consisting of (i) disjoint ranked alphabets n and σ of nonterminal and terminal symbols with @xmath14, (ii) a nullary start nonterminal @xmath15, and (iii) a finite set p ⊆ p 0 ∪ p 1 of productions, where in the following let @xmath16, σ, s, p ) be an scftg. we write (n, r) ∈ p simply as @xmath17. given t, @xmath18,n 1 (σ 0 ∪ n 0 ) we let t ⇒ g u if there exist (@xmath19, or (ii) t| @xmath20 spine grammars (fujiyoshi and kasai, 2000) are a restriction on simple monadic context-free tree grammars that remain equally expressive by lemma 5.4 of fujiyoshi and kasai (2000) modulo relabelings. let us clarify this result. clearly, each spine grammar is itself an scftg and for each scftg g there exists a spine grammar g and a although scftgs are more established, we elect to utilize spine grammars because of their essential notion of spines. definition 8. the scftg g is a spine grammar if there exists a map d : σ 2 → {1, 2} such that @xmath21. henceforth let g be a spine grammar with map d : σ 2 → {1, 2}. consider a production (@xmath22. the spine of c is simply the path from the root of c to the unique occurrence pos (c) of . the special feature of a spine grammar is that the symbols along the spine indicate exactly in which direction the spine continues. since only the binary terminal symbols offer branching, the special feature of spine grammars is the existence of a map d that tells us for each binary terminal symbol σ ∈ σ 2 whether the spine continues to the left, in which case d(σ) = 1, or to the right, in which case d(σ) = 2. this map d, called spine direction, applies to all instances of σ in all productions with spines. in the original definition of spine grammars (fujiyoshi and kasai, 2000, definition 3.2), only nonterminal symbols have a spine direction. by creating copies of binary terminal symbols we can show that both variants are equivalent modulo relabelings. in spine grammars in normal form, the initial nonterminals are isolated and cannot occur on the right-hand sides. the 3 production types of the normal form are illustrated in figure 2 . using a single start production followed by a number of chain and terminal productions, a nullary nonterminal n can be rewritten to a tree t that consists of a spine of terminals, where each nonspinal child is a nullary nonterminal. formally, for every nullary nonterminal @xmath23 so we perform a single derivation step using the productions of g followed by any number of derivation steps using only productions of g . the elements of i g (n) are called spinal trees for n and their spine generator is n. by a suitable renaming of nonterminals we can always achieve that the spine generator does not occur in any of its spinal trees. the spine grammar g is normalized if it is in normal form and for every nullary nonterminal @xmath24. the following result is a variant of theorem 1 of @xcite . theorem 10. for every spine grammar there is a strongly equivalent normalized spine grammar. example 11. we define the spine grammar @xmath25, σ, {s}, p ) with n 1 = {t, a, b, c, b , e}, n 0 = {s, a, b, c, e}, σ 2 = {α 2 , β 2 , γ 2 , η 2 }, σ 0 = {α, β, γ, δ}, and p as shown below. the tree in figure 3a , in which the spines are marked by thick edges, is generated by g. the spinal tree corresponding to the main spine of the depicted tree is shown in figure 3b . the yield of t (g) is {α n δ γ n β m | n, @xmath26. ## tree-adjoining grammars before we proceed we will briefly introduce tag and sketch how a spine grammar is obtained from it. tag is a mildly context-sensitive grammar formalism that operates on a set of elementary trees of which a subset is initial. to generate a tree, we start with an initial tree and successively splice elementary trees into nodes using adjunction operations. in an adjunction, we select a node, insert a new tree there, and reinsert the original subtree below the selected node at the distinguished and specially marked foot node of the inserted tree. we use the nonstrict variant of tag, in which the root and foot labels of the inserted tree need not coincide with the label of the replaced node to perform an adjunction. to control at which nodes adjunction is allowed, each node is equipped with two types of constraints. the selective adjunction constraint specifies a set of trees that can be adjoined and the boolean obligatory adjunction constraint specifies whether adjunction is mandatory. only trees without obligatory adjunction constraints are part of the generated tree language. figure 4 shows the elementary trees of an example tag. only tree 1 is initial and foot nodes are marked by a superscript asterisk • * on the label. whenever adjunction is forbidden (i.e., empty set as selective adjunction constraint and nonobligatory adjunction), we omit the constraints altogether. otherwise, the constraints are put next to the label. for example, {2, 3} + indicates that tree 2 or 3 must (+ = obligatory) be adjoined. we briefly sketch the transformation from tag to scftg by @xcite . tag is a notational variant of footed simple cftg, in which all variables in right-hand sides of productions appear in order directly below a designated foot node. to obtain an scftg, the footed simple cftg is first converted into a spine grammar, where the spine is the path from the root to the foot node, and then brought into normal form using the construction of @xcite . the spine grammar of example 11 is strongly equivalent to the tag shown in figure 4 . ## decomposition into spines we proceed with the construction starting from the normalized spine grammar g. first, we will construct a context-free grammar (cfg) that captures all information of g. it represents the spinal trees (from bottom to top) as strings and enriches the symbols with the spine generator (initialized by start productions and preserved by chain productions) and a non-spinal child (given by terminal productions). the order of these annotations depends on the spine direction of the symbol. the leftmost symbol of the generated strings has only a spine generator annotated since the bottom of the spine has no children. to simplify the notation, we write n g for (n, g) ∈ n 2 , α n for (α, n) ∈ σ 0 × n , and and productions @xmath27. on the other hand, for each chain or terminal production we have to combine them with all nonterminals, as we do not know the spine generator of the nonterminal on the left side of the original production. when a string is derived, the spine generators are pulled through originating from start productions and are consistent throughout the string. the language generated by g is note that each string generated by the cfg belongs to (σ 0 × n )(σ 2 × n 2 ) * . next we define how to reassemble those spines to form trees again, which then relabel to the original trees generated by g. the operation given in the following definition describes how a string generated by the cfg can be transformed into a tree by attaching subtrees in the non-spinal direction of each symbol, whereby the non-spinal child annotation of the symbol and the spinal annotation of the root of the attached tree have to match. for @xmath28, let t @xmath29. we define the tree language att t (w) ⊆ t σ 2 ×n,∅ (σ 0 ×n ) recursively by att t (α n ) = {α n } for all α @xmath30, and for all @xmath31. to obtain the tree language defined by g, it is necessary to apply this operation recursively on the set of spines. we inductively define the tree language f(l) generated by l to be the smallest tree language f such that att f (w) ⊆ f for every @xmath32. example 16. the cfg g of example 13 generates the set of spines s(g) and f(s(g)) s contains the correctly assembled trees formed from these spines. figure 3c shows a tree of f(s(g)) s since the generator of the main spine is @xmath33, which is stored in spinal direction in the root label α 2 ā s . we can observe the correspondence of annotations in non-spinal direction and the spine generator of the respective child in the same direction. next we prove that f s(g) s and t (g) coincide modulo relabeling. this shows that the context-free language s(g) of spines completely describes the tree language t (g) generated by g. corollary 18. there exists a pop-normalized mpda a such that l(a) example 19. the mpda constructed in corollary 18 for the spine grammar g of example 11 is depicted in figure 5 . initial states are indicated using a start marker and final states are marked by a double circle. pushing and popping stack operations are written with downwards and upwards arrows, respectively. the mpda consists of two components. the bigger one describes the main spine, and the smaller one describes the side spine. the distinction between the three stack symbols is necessary due to popnormalization. the distinction between q 1 and q 1 (and similar states) is necessary because their previous action distinguishes their produced input symbol since we recognize next s(g 2 ) . for example, τ (q 1 ) = and τ (q 1 ) = β 2 s b , γ 2 s c . similarly, τ (p 1 ) = (z, z) and τ (p 1 ) = ( , z) where @xmath34. to completely capture the behavior of g, we additionally require the set l 1 = {( , α ā), ( , βb), ( , β ē), ( , γ c)}, which contains the spines of length 1. the spine generator gen : @xmath35, where τ (q) = (s 1 , s 2 ) ∈ δ. since a cannot accept strings of length 1, we have to treat them separately. recall that @xmath36, \}. the slash type slash : (q \ f ) → d and combining nonterminal comb : (q \ f ) ∪ {⊥} → n of a state @xmath37. let τ (q) = σ n 1 n 2 , s 2 with σ n 1 n 2 ∈ σ 2 × n 2 and s 2 ∈ σ . the slash type and the combining nonterminal can be determined from the next symbol σ n 1 n 2 . formally, slash(q) = / if d(σ) = 1 and slash(q) = \ otherwise. in addition, comb(q) = n 3-d(σ) and comb(⊥) = s. we simulate the accepting runs of a in the spines consisting of primary categories of the ccg. the main idea is that the primary categories on the spine store the current configuration of a. this is achieved by adding an additional argument for transitions that push a symbol, whereas for each popping transition, an argument is removed. the rightmost argument stores the current state in the first component and the top of the stack in the second component. the previous arguments store the preceding stack symbols in their second components and the state the automaton returns to when the stack symbol stored in the next argument is popped in the first components. to implement the required transformations of consecutive primary categories, the secondary categories need to have a specific structure. this mandates that the categories at the top of a spine (which act as secondary categories unless they belong to the main spine) cannot store their corresponding automaton state in the first component of the last argument as usual, but instead utilize the third component of their target. thus each argument stores the final state corresponding to its secondary combination partner in the third component. this third component also allows us to decide whether a category is primary: a category is a primary category if and only if the spine generator of the state stored in the first component of the last argument and the spine generator of the state stored in the last component of the target coincide. this is possible since g is normalized, which yields that attaching spines have a spine generator that is different from the spine generator of the spine that they attach to. definition 20. we define the ccg g a,l 1 = (δ 0 , a, r, i , l) as follows: we use a i to refer to the i-th component of an atom @xmath38. additionally, we listed all the forward rules, but for each forward rule there also exists a symmetric backward rule yielding the rule sets r \ 1 , r \ 2 , and r \ 3 . we need some notions for the lexicon. a category @xmath39, i). let c @xmath40. clearly i ⊆ c wf . in addition, we introduce sets l 1 and a of top-of-spine categories derived from the short strings of l 1 and the strings accepted by a, respectively: each atom of a consists of three components. the first component stores the current state of a (or the special symbol ⊥), the second component stores the current symbol at the top of the stack, and the third component stores the final state corresponding to the combining category of the attaching side spine. with this intuition, the rule system directly implements the transitions of a. the lexicon assigns categories to symbols that can label leaves, so these symbols are taken from the nullary terminal symbols. the assigned categories consist of a category that appears at the top of a spine and an additional argument for the initial state of an accepting run. the spines of length 1 are translated directly to secondary categories or initial categories. let us make a few general observations that hold for all the categories that appear in derivation trees of g a,l 1 : (i) all categories are well-formed. this follows from the fact only well-formed categories occur in the lexicon and all categories in the derivation trees consist of atoms and arguments that were already present in the lexicon. (ii) all primary categories ax | b obey gen(a 3 ) = gen(b 1 ). this is directly required by the rule system. finally, we will now describe how to relabel the derivation trees d(g a,l 1 ) of the ccg g a,l 1 that uses categories built using the input symbols of the mpda a. note that only well-formed categories will occur in derivation trees. primary and nonprimary categories are relabeled differently. the relabeling ρ : c @xmath41; i.e., gen(a 3 ) = gen(b 1 ). otherwise ρ(ax) = τ (a 3 ) for all initial and secondary categories @xmath42. the following property requires that the spine grammar g is normalized, so a spine never has the same spine generator as its attached spines. lemma 21. for all secondary categories ax | b we have gen(a 3 ) = gen(b 1 ). we are now ready to describe the general form of primary spines of g a,l 1 . given a primary spine c 0 . . . c n read from lexicon entry towards the root with @xmath43, we know that it starts with a lexicon entry c 0 = ax | @xmath44, which as such cannot be further modified. category c n is relabeled to τ (a 3 ) and c is relabeled to τ (q m ). additionally, unless a 1 = ⊥, the first components of all atoms in ax have the same spine generator gen(a 1 ) and gen(q 1 ) = • • • = gen(q m ), but gen(a 1 ) = gen(q 1 ). finally, neighboring this coupling is introduced in the rules of second degree and preserved by the other rules. using these observations, it can be proved that the primary spines of g a,l 1 are relabeled to strings of next s(g) and vice versa. additionally, spines attach in essentially the same manner in the ccg and using f. this yields the following main theorem. theorem 22. given a spine grammar g, we can construct a ccg g that can generate t (g). example 23. figure 6 shows part of the derivation tree of ccg g a,l 1 that corresponds to the tree of figure 3a , which is generated by the spinal grammar g of example 11. we use the following abbreviations: α = ( , α a ), β = ( , β b ), and γ = ( , γ c ). the labeling of the depicted section is δ γ 2 γ 2 β 2 for the main spine and β η 2 for the side spine (see figure 3a ). the corresponding runs of a are q 0 , ω , q 1 , ω , q 1 , υω , q 2 , υω and p 0 , χ , p 1 , ε . let us observe how the transitions of a are simulated by g a,l 1 . the first transition (q 0 , ε, ε, q 1 ) on the main spine does not modify the stack. it is implemented by replacing the last argument /(q 0 , ω, γ) by /(q 1 , ω, γ). the next transition (q 1 , ε, υ, q 1 ) pushes the symbol υ to the stack. the argument /(q 1 , ω, γ) is thus replaced by \(q 3 , ω, α)/(q 1 , υ, p 1 ). as the stack grows, an additional argument with the new state and stack symbol is added. the previous argument stores pop(υ) = q 3 to ensure that we enter the correct state after popping υ. it also contains the previous unchanged stack symbol ω. the popping transition (p 0 , χ, ε, p 1 ) on the side spine run is realized by removing /(p 0 , χ, β). the third components are required to relabel the non-primary categories. at the bottom of the main spine, c 1 = (⊥, ε, q 3 )/(q 0 , ω, γ) is a primary category because q 0 and q 3 are associated with the same spine generator s. thus, c 1 gets relabeled to τ (q 0 ). however, for c 2 = (q 0 , ω, γ)/(q 1 , ω, γ) the spine generators of γ and of the output of q 1 are different (c and s). hence it is a non-primary category and gets relabeled to γ. concerning the lexicon, c 1 is a lexical category due to the fact that (⊥, ε, q 3 ) ∈ a can appear at the top of a spine as an initial category with q 3 ∈ f in its third component, while the appended (q 0 , ω, γ) represents an initial configuration of a. similarly, c 2 is a well-formed secondary category of a rule and the third component of its target is in l 1 . therefore, it is an element of l 1 , which is a subset of the lexicon. let us illustrate how the attachment of the side spine to the main spine is realized. the lexicon contains (q 1 , υ, p 1 )\(q 2 , υ, α)\(p 0 , χ, β), of which the first two atoms are responsible for performing a transition on the main spine. this part cannot be modified since the rule system disallows it. the target stores the final state p 1 of the side spine run in its third component. the appended argument models the initial configuration of the side spine run starting in state p 0 with χ on the stack. for the converse inclusion we utilize theorem 20 of @xcite . it states that for every ccg g there exists an scftg that generates the rule trees of g . whereas derivation trees are labeled by categories, rule trees are labeled by lexicon entries at leaves and by applied rules (instead of the output category) at inner nodes. rule trees are a natural encoding of derivation trees using only a finite set of labels. as each rule indicates the target and last argument of its output category, rule trees can be relabeled in the same manner as derivation trees. for completeness' sake we restate definition 16 of @xcite . definition 24. let @xmath45, a, r, i, l) be a ccg and @xmath46,∅ (l(σ)). a tree @xmath47, where the partial map cat : @xmath48, (ii) cat axy ax\b by (t 1 , t 2 ) = azy for all trees the set of all rule trees of g is denoted by r(g). we observe that any category relabeling can equivalently be applied to rule trees instead of derivation trees (because a category relabeling only depends on the target a and the last argument | b of a category ax | b). this yields the second main theorem. theorem 25. ccgs and scftgs are strongly equivalent up to relabeling. @xcite proved that tags and scftgs are strongly equivalent, which shows that they are also strongly equivalent (up to relabeling) to ccgs. ## conclusion we presented a translation from spine grammar to ccg. due to the strong equivalence of spine grammar and tag @xcite , we can also construct a strongly equivalent ccg for each tag. together with the translation from ccg to scftg @xcite , this proves the strong equivalence of tag and ccg, which means that both formalisms generate the same derivation trees modulo relabelings. our construction uses ccg rules of degree at most 2, only first-order categories, lexicon entries of arity at most 3, and no ε-entries in the lexicon. such ccgs thus have full expressive power. avoiding ε-entries is particularly interesting because they violate the principle of adjacency @xcite , which is a fundamental linguistic principle underlying ccg and requires that all combining categories correspond to phonologically realized counterparts in the input and are string-adjacent. their elimination is performed by trimming them from the scftg obtained from a ccg with ε-entries and translating the trimmed scftg back to a ccg using our construction. translating ccg to scftg @xcite yields scftgs whose size is exponential in a ccg-specific constant, which depends on the maximal rule degree and the maximal arity of lexicon entries. the increase can be attributed to variables in ccg rules, which need to be properly instantiated. our construction increases the grammar size only polynomially, which can be verified for each step. overall, a k-ccg can be converted to an equivalent 2-ccg without ε-entries in time and space exponential in k (and the maximal length of lexicon entries) and polynomial in the size of the grammar.