Bericht Nr. 84, Februar 1997

ISSN 0947-6954/97

Arbeitspapiere des Sonderforschungsbereichs 340

Sprachtheoretische Grundlagen für die Computer linguistik

James Rogers :

The Descriptive Complexity of Generalized Local Sets

Universität Stuttgart Universität Tübingen Deutschland Informationssysteme GmbH Arbeitspapiere des SFB 340

Bericht Nr. 84, Februar 1997

THE DESCRIPTIVE COMPLEXITY OF GENERALIZED LOCAL SETS

JAMES ROGERS

Abstract. Context-free grammars and tree automata, because they are required to be finite, are limited to defining sets of trees in which the branching is bounded by a finite constant. As a result they cannot capture accounts of syntactic phenomena in which no such a priori bound exists—in flat accounts of coordination, for instance. This mismatch led Langendoen in 1976 and Gazdar, et al., in 1985 (GPSG) to propose varieties of two level grammars, in the one case infinite grammars that are themselves generated by other grammars, in the other grammars that permit regular expressions on the right-hand side of rewrite rules. In earlier work, we have characterized the local sets (the sets of trees generated by CFGs) and the recognizable sets (those accepted by tree automata) by definability in the logical language L_{K,P}^{2} . In defining such sets of trees in L_{K,P}^{2} , however, one must explicitly bound the branching. In this paper we explore the consequences of relaxing these bounds. We show, for instance, that the GPSG account of coordination can be captured in L_{K,P}^{2} . Moreover, we show that the sets of finite trees definable in L_{K,P}^{2} without the bound are exactly the sets of trees accepted by tree automata that are representable as regular sets, or, equivalently, projections of sets of trees generated by infinite CFGs that are themselves generated by regular grammars.

1. Introduction

Let us take, as a starting point, the following descriptive characterization of the strongly context-free sets:

Theorem 1. A set of finite trees with bounded branching is definable in L_{K,P}^{2} iff it is a projection of a local set.

To appear in: Kolb, H.-P. & U. Mönnich (eds.), The Mathematics of Syntactic Structure.

ISSN 0947-6954/97 \begin{matrix}c \\ ◯ \end{matrix}1997 Der Autor

This is a variation of a result originally due to Doner [Don70]. It characterizes the sets of derivation trees generated by context-free grammars (the local sets) in terms of their definability as sets of models for a restricted logical language, in this case L_{K,P}^{2} , a monadic second-order language over trees, which is a linguistically oriented language equivalent in descriptive power to SωS, the monadic second-order theory of the complete ω-branching tree.^{1} The content of the theorem is that if one restricts to finite trees in which there is a fixed finite bound on the branching (both definable restrictions in L_{K,P}^{2} ), then the sets of such trees that satisfy collections of constraints stateable in L_{K,P}^{2} are strongly context-free in the sense that it is possible to generate them with a context-free grammar, possibly by adding auxiliary labels that refine the categories labeling the trees into finitely many sub-categories. All of this will be made more precise shortly.

The qualifications to this theorem—the restriction to trees with bounded branching and the projection—have both formal and linguistic significance.^{2} The effect of the projection is to permit the refinement of categories on the basis of local context that is typical of GPSG and HPSG (as in slashed categories). Exploring this in [Rog96c] we establish some formal consequences of the question of whether to require all categories to be empirically justified or whether to admit their arbitrary refinement in this way. In this paper we turn our attention to the requirement that there be a finite bound on the branching factor of the trees. Such a bound exists for the local sets simply because we require CFGs to be finite—since there can be only finitely many rewriting rules and since they are restricted to expanding non-terminals into finite strings of terminals and non-terminals such a bound must always exist. Furthermore, it has be argued (on learnability grounds, for instance, see [Kay84]) that such a bound should exist for human languages. Nonetheless, tree sets in which no finite bound on the branching exists are linguistically interesting figuring, for instance, in all flat accounts of coordination.^{3} Such accounts of coordination also figure prominently in GPSG and HPSG. Strikingly, when we relax this restriction and allow trees with arbitrary finite branching, the sets of trees definable in L_{K,P}^{2} (or SωS) turn out to be a mild generalization of the sets of trees definable using GPSG-style grammars.

1Doner’s result was in terms of wSnS, a definable sub-theory of SωS.

2The requirement that the trees be finite is a simple consequence of our assumption that they can be generated by a finite process. This restriction is without great significance.

3Note that finiteness of the trees will still require all branching to be finite, branching of any finite degree, however, may be admitted.

In the next two sections we introduce L_{K,P}^{2} and present our formalizations of CFGs, tree automata, and the sets of trees they generate. We discuss the descriptive characterizations of these classes of sets of trees in Section 4. In Section 5 we look at the linguistic motivation for accounts of syntax without fixed bounds on branching. We then introduce generalizations of CFGs and tree automata that can accommodate sets of trees without such bounds and characterize the sets of trees definable in L_{K,P}^{2} without explicitly bounded branching in those terms. We close, in Section 7, with some thoughts on the significance of the model-theoretic approach to syntax these results exemplify.

2. L_{K,P}^{2}

L_{K,P}^{2} is a mathematical language for specifying properties of trees which can naturally express the types of constraints that typically comprise theories of natural language syntax. It includes the binary predicates:

◁: — immediate domination (constituency), ◁^{∗}: — (reflexive) domination, ◁^{+}: — proper domination, ≺: — linear precedence (left-of), and ≈: — equality,

as well as a collection of labels P (constants ranging over sets of nodes), a collection of individual constants K, and two sorts of variables—those ranging over individuals (for which we will use lower case), and those ranging over arbitrary sets (for which we will use upper case). Either sort of variable may be bound by quantifiers. We denote the fact that an individual a is a member of the set labeled A with the formula A(a). Similarly, the formula X(x) will be made true iff the individual assigned to the variable x is a member of the set assigned to the variable X.

We interpret these formulae over trees in the form of ordinary modeltheoretic structures T = ⟨T, P_{T} , D_{T} , L_{T} , I_{K}, I_{P}⟩. The domain T is a tree domain [Gor67]—a set of strings of natural numbers which are interpreted as node addresses: the root of the tree occurs at address ε and the children of a node at address w are at addresses w0, w1, …, wn in left-to right order. Tree domains are required to be both prefix closed (uv ∈ T ⇒ u ∈ T) and left closed (ui ∈ T and j < i ⇒ uj ∈ T). The predicates ◁, ◁^{∗}, and ≺ are interpreted by P_{T}, D_{T}, and L_{T}, respectively, which are fixed

NP \overline{N} N  VP S V  VP V NP PP Det \overline{N}  \overline{P} N P NP \overline{N} N  ^{0}^{00}^{000}  ^{1}^{ε}^{10}  ^{11}^{110} ^{111} ^{112}^{1110}^{1111} ^{1120}^{11110}^{11200}^{11201}^{112010}^{1120100} T =  T =
K = ∅, P = \{S, NP, VP, PP, \overline{N}, \overline{P}, N, V, Det, P\}
P_{T} = {⟨ε, 0⟩ , ⟨ε, 1⟩ , ⟨0, 00⟩ , ⟨00, 000⟩ , ⟨1, 10⟩ , …, ⟨112010, 1120100⟩}
D_{T} = {⟨ε, ε⟩ , ⟨ε, 0⟩ , ⟨ε, 00⟩ , ⟨ε, 000⟩ , ⟨ε, 1⟩ , …, ⟨112010, 1120100⟩ ,
⟨1120100, 1120100⟩}
L_{T} = {⟨0, 1⟩ , ⟨0, 10⟩ , ⟨0, 11⟩ , …, ⟨00, 1⟩ , ⟨00, 10⟩ , ⟨00, 11⟩ , ⟨00, 110⟩ ,
…, ⟨11200, 1120100⟩}
I_{K} = ∅
I_{P} = {S ↦ {ε} , NP ↦ {0, 111, 11201} , VP ↦ {1, 11} , …, P ↦ {11200}}

Figure 1. A tree, e.g., We should give the award to Alice

by T:

P_{T} =^{def} {⟨u, ui⟩ ∈ T × T | u ∈ IN^{∗}, i ∈ IN}
D_{T} =^{def} {⟨u, uv⟩ ∈ T × T | u, v ∈ IN^{∗}}
L_{T} =^{def} {⟨uiv, ujw⟩ ∈ T × T | u, v, w ∈ IN^{∗}, i < j ∈ IN} .

Finally, the individual and set constants are interpreted by I_{K} and I_{P} which map K to individuals in T and P to subsets of T, respectively.

A formula φ(x⃗, X⃗) of L_{K,P}^{2} with free variables in the sequences x⃗ = ⟨x_{1}, …, x_{m}⟩ and X⃗ = ⟨X_{1}, …, X_{n}⟩ is satisfied in a tree T = ⟨T, P_{T} , D_{T} , L_{T} , I_{K}, I_{P}⟩ relative to an assignment s mapping individual variables in x⃗ to individuals in T and labels X⃗ to subsets of T. We extend this to a function ŝ interpreting terms:

ŝ(t) = \{ \begin{matrix}s(t) & if t ∈ x⃗ or t ∈ X⃗ \\ I_{K}(t) & if t ∈ K \\ I_{P}(t) & if t ∈ P. \end{matrix}

Then T satisfies φ(x⃗, X⃗) with s in the standard way:

T ⊧ t ◁ u [s] ⟺^{def} ⟨ŝ(t), ŝ(u)⟩ ∈ P_{T} ,
T ⊧ U(t) [s] ⟺^{def} ŝ(t) ∈ ŝ(U),
T ⊧ (∃X)[φ(X)] [s] ⟺^{def} T ⊧ φ(X) [s[X ↦ A]] for some A ⊆ T ,

etc.

where s[X ↦ A] is the assignment s modified to map X to A. Proper domination (◁^{+}) is treated as a defined predicate—dominates and not equal to.

In this setting the individual constants K are, in fact, redundant since we can take them to denote singleton sets. Thus, since the interpretations of the binary predicates are fixed in the domain, models depend only on the domain and the interpretation of P. If we invert I_{P} to get a mapping of nodes in T to labels we get the standard notion of a P-labeled tree:

⟨T, τ⟩ where τ(w) = A ⟺^{def} w ∈ I_{P}(A).

3. Local and Recognizable Sets

The defining characteristic of the “context-freeness” of a syntactic theory is that it is (or can be) stated in terms of local relationships— relationships that hold between a category and its immediate constituents (i.e., between categories labeling a node and its children) or between phrase mates (categories labeling siblings). Such relationships can be expressed as local trees.

Definition 1 (Local trees). The local tree occurring at a node w in a P -labeled tree T = ⟨T, τ⟩ is the pair

L(T , w) =^{def} ⟨τ(w), τ(⟨wi | i ∈ IN, wi ∈ T ⟩)⟩ .

That is, the pair consisting of the label of that node and the sequence of labels of its children—here we extend τ to sequences of nodes in the usual way by taking τ(⟨w_{0}, …, w_{n}⟩) to be ⟨τ(w_{0}), …, τ(w_{n})⟩.

The set of local trees occurring in T is

L(T ) =^{def} {L(T , w) | w ∈ T } .

There are specific sequences of labels occurring in a tree and, in particular, sets of such sequences (i.e., languages) that have distinguished roles in the theory.

Definition 2. Suppose T = ⟨T, τ⟩ is a P -labeled tree. Then:

• The set of leaves of T is the set of its atomic categories—those labeling nodes with no children:

l(T ) =^{def} {σ ∈ P | ⟨σ, ϵ⟩ ∈ L(T )}

• The yield of T is the sequence of leaves of T in left-to-right order:

Yd(T ) =^{def} τ(⟨w_{i} | w_{i} ∈ l(T ), i < j ⇒ w_{i} ≺ w_{j}⟩).

• For all σ ∈ P, the child language of σ in T is the set of strings labeling the children of nodes labeled σ:

Ch_{σ}(T ) =^{def} {α ∈ P^{∗} | ⟨σ, α⟩ ∈ L(T )}

Again as usual, we extend these to a set of trees 𝕋 by taking the union over each tree in the set, e.g.,

L(𝕋) =^{def} ⋃_{T ∈𝕋}[L(T )].

In particular, the yield of a set of trees 𝕋 is the string language associated with that set

Yd(𝕋) =^{def} {Yd(T ) | T ∈ 𝕋} .

3.1. Local Sets. While Context-free grammars are familiar objects, we present them in a somewhat unusual manner, one that is chosen to emphasize the relationships between CFGs and the local sets and between CFGs and tree automata.

Definition 3 (Context-free grammars). A (positive) context-free grammar (CFG) is a finite set of local trees over some alphabet Σ:

G ⊆ Σ × Σ^{∗}, finite .

For any Σ_{S} ⊆ Σ the set of trees admitted by G wrt Σ_{S} is the set of finite trees constructed from the local trees in G in which the root is labeled with some symbol in Σ_{S}:

G(Σ_{S}) =^{def} {T = ⟨T, τ⟩ | T finite , τ(ϵ) ∈ Σ_{S}, and L(T ) ⊆ G}

The set of terminal symbols of G is:

Λ_{G} =^{def} {σ ∈ Σ | ⟨σ, ϵ⟩ ∈ G} .

This definition generalizes the standard notion of CFG in two ways: we allow a finite set of start symbols (rather than just one), and we allow productions for terminal symbols. Thus terminal symbols may label interior nodes of the tree, although, since leaves are local trees with empty sequences of children and must be licensed by G, only terminal symbols may label the leaves (i.e., l(T ) ⊆ Λ(G)). These generalizations are inconsequential for string languages, of course, but are significant when considering the set of trees admitted by a grammar, where the standard notion is unnaturally restrictive. Note that all grammars in this form are positive—they do not admit languages including the empty string. Since local trees with empty sequences of children are taken to be terminals, there is no way of erasing a non-terminal.

It should be clear that a tree is admitted by a CFG iff it is a derivation tree generated by that CFG in its more typical presentation.

Definition 4 (Local sets). A set of trees is local iff it is the set of trees admitted by some CFG.

The context-free (string) languages are exactly the yields of the local sets.

3.2. Recognizable Sets. As we have noted, constraints stated in L_{K,P}^{2} are capable of defining sets of trees that are not local sets. We will show in the next section that the definable sets are, in fact recognizable sets. These are the sets of trees that are recognized by tree automata [GS84], which we can regard as CFGs with a set of auxiliary labels (states) that are employed in controlling the derivation but do not show up in the derived tree.

Definition 5 (Tree Automata). A tree automaton over an alphabet Σ and a finite set of states Q is a finite set of triples:

A ⊆ Σ × Q × Q^{∗}, finite .

For any Q_{S} ⊆ Q the set of trees recognized by A (wrt Q_{S}) is

A(Q_{S}) =^{def}

{T = ⟨T, τ⟩ | T finite and

∃r : T → Q such that
r(ϵ) ∈ Q_{S} and
(∀w ∈ T)[⟨τ(w), r(w), r(⟨wi ∈ T ⟩)⟩ ∈ A]}.

Which is to say, ⟨T, τ⟩ is accepted by A wrt Q_{S} iff it is possible to assign states in Q to the nodes in T, with the root being assigned a state

A^{S_{0}}  ^{A} ^{S_{0}}  ^{A}^{S_{1}} ^{A} ^{S_{1}}^{A}^{S_{1}}^{B}^{S_{0}}^{A} ^{S_{1}} ^{A}^{S_{1}}  ^{A} ^{S_{1}} A_{1B} = { ⟨B, S_{0}, ⟨S_{1}, S_{1}⟩⟩ , ⟨A, S_{1}, ⟨S_{1}, S_{1}⟩⟩ , ⟨A, S_{0}, ⟨S_{0}, S_{1}⟩⟩ , ⟨A, S_{0}, ϵ⟩ , ⟨A, S_{0}, ⟨S_{1}, S_{0}⟩⟩ , ⟨A, S_{1}, ϵ⟩ , ⟨B, S_{0}, ϵ⟩  }

Figure 2. Separating the recognizable and local sets.

in Q_{S}, that is consistent with A in the sense that if a node labeled σ is assigned state q and its children are assigned the sequence of states ⟨q_{0}, …, q_{n}⟩ (ε if there are no children) then ⟨σ, q, ⟨q_{0}, …, q_{n}⟩⟩ is in A. The assignment r of states to nodes in the domain of T is referred to a run of A (for Q_{S}) on T .

Definition 6 (Recognizable Sets). A set of trees is recognizable iff it is A(Q_{S}) for some A and Q_{S}.

Clearly every local set is recognizable—take Q to be Σ. The converse is not true, however; the inclusion is proper. For example, let A_{1B} be the tree automaton of Fig. 2. The set A_{1B}({S_{0}}) is the set of binarybranching trees in which at most one node is labeled B, all others are labeled A (a set we will refer to as “OneB”). To see that this is not a local set, note that if the local tree ⟨A, ⟨A, B⟩⟩, for instance, occurs in a tree admitted by a CFG then it must occur in that CFG. But then that CFG will license trees in which ⟨A, ⟨A, B⟩⟩ occurs any number of times.

The automaton of the example recognizes OneB by distinguishing nodes that may dominate a B from those that may not by assigning them distinct states (S_{0} and S_{1}, respectively). If we make that state explicit by labeling the trees with pairs in Σ × Q then the set becomes a local set.

The CFG G_{1B} of Fig. 3 generates trees in which no more than one node is labeled ⟨B, S_{0}⟩, all nodes that properly dominate such a node are labeled ⟨A, S_{0}⟩, and those that don’t are labeled ⟨A, S_{1}⟩. In effect we are making OneB local by refining the original categories ({A, B}) into finitely many sub-categories ({⟨A, S_{0}⟩ , ⟨A, S_{1}⟩ , ⟨B, S_{0}⟩ , ⟨B, S_{1}⟩}) which suffice to distinguish those nodes that may dominate Bs from those that

⟨A, S_{1}⟩^{⟨A, S_{1}⟩}^{⟨A, S_{0}⟩}^{⟨B, S_{0}⟩}^{⟨A, S_{1}⟩}^{⟨A, S_{1}⟩} ^{⟨A, S_{1}⟩}^{⟨A, S_{0}⟩}  ^{⟨A, S_{1}⟩} G_{1B} = { ⟨A, S_{0}⟩ → ⟨⟨A, S_{1}⟩ , ⟨A, S_{0}⟩⟩ , ⟨A, S_{1}⟩ → ⟨⟨A, S_{1}⟩ , ⟨A, S_{1}⟩⟩ , ⟨B, S_{0}⟩ → ⟨⟨A, S_{1}⟩ , ⟨A, S_{1}⟩⟩ , ⟨A, S_{0}⟩ →  ε, ⟨A, S_{1}⟩ →  ε, ⟨B, S^{0}⟩ →  ε  } ⟨A, S_{0}⟩ → ⟨⟨A, S_{0}⟩ , ⟨A, S_{1}⟩⟩ , ⟨A, S_{0}⟩ → ⟨⟨B, S_{0}⟩ , ⟨A, S_{1}⟩⟩ , ⟨A, S_{0}⟩ → ⟨⟨A, S_{1}⟩ , ⟨B, S_{0}⟩⟩ ,

Figure 3. Making the state explicit.

may not. Note that the original trees are recoverable from the “refined” trees by taking the first projection of their labels. This approach works in general—whenever it is possible to refine the categories labeling a set of trees into finitely many sub-categories in such a way that the ways in which a given category may be expanded is determined entirely by its subcategory then the equivalent set of trees labeled with the sub-categories will be a local. This is always the case for recognizable sets.

Definition 7. Suppose T = ⟨T, τ⟩ is a tree and the range of τ is a set of n-tuples. The i^{th} -projection of T , for 0 < i ≤ n, is ⟨T, π_{i} ∘ τ⟩—T with nodes labeled with the i^{th} component of their labels in T .

Lemma 1 (Thatcher [Tha67]). Every recognizable set is the projection of a local set.

Proof. The proof simply carries out the idea of the example. Suppose 𝕋 = A(Q_{S}) for some tree automaton A over Σ and Q and set of initial states Q_{S}. Let Â(Q_{S}) be the set of Σ × Q-labeled trees:

Â(Q_{S}) = {⟨T, τ⟩ | T = ⟨T, π_{1} ∘ τ⟩ ∈ A(Q_{S}) and π_{2} ∘ τ is a run of A on T } .

Which is to say that ⟨T, τ⟩ ∈ Â(Q_{S}) iff the first projection of T is a tree in A(Q_{S}) and the second projection of τ encodes a run of A(Q_{S}) on that tree.

Thus A(Q_{S}) is a projection of Â(Q_{S}). It is not hard to show that Â(Q_{S}) is generated by a CFG and is, therefore, a local set.

Corollary 1. A language is a CFL iff it is the yield of a recognizable set.

This follows from the fact that we might as well label the leaves in Â(Q_{S}) with Σ.

4. Descriptive Characterization

We are now in a position to establish the characterization we took as our starting point, which is, in essence, a characterization of the recognizable sets by definability in L_{K,P}^{2} . The result was originally established for SnS, the monadic second-order theory of n successor functions [Rab69]. As we will show shortly, L_{K,P}^{2} and SnS are equivalent in their descriptive power; we work in L_{K,P}^{2} because it has a relatively natural signature for reasoning about trees in the manner typical of theories of syntax. Thus, while encodings of linguistically significant relationships in SnS tend to be rather difficult to decipher, in L_{K,P}^{2} they are reasonably transparent.

Definition 8 (SnS). Let n_{n} = ⟨T_{n}, ε, ◁^{∗}, ⪯≀, r_{i}⟩_{i<n}, where T_{n} is the complete n-branching tree-domain, ε is the root of T_{n}, ◁^{∗} and ⪯≀ are domination and lexicographic order on T_{n}, respectively, and r_{i} takes elements of T_{n} to their i^{th} child.

SnS is the monadic second-order theory of n_{n}; wSnS is the weak monadic second-order theory of n_{n}, the theory in which second-order quantification is restricted to finite sets.

Finiteness is a definable property of subsets in SnS, therefore wSnS is a definable fragment of SnS.

Theorem 2 (Büchi [Büc60]). S1S is decidable.

Theorem 3 (Rabin [Rab69]). SnS is decidable for all n ≤ ω.

Büchi’s result is a special case of Rabin’s. We will sketch Rabin’s proof. Rabin first establishes this result for the n = 2 case. The proof is based on the idea that assignments making some formula φ(X⃗) over the signature of S2S true in n_{2} are, in effect, P(X⃗)-labeled trees with domain T_{2} (where P(X⃗) is the powerset of the set of elements of X⃗). He gives an effective procedure for constructing, for any such φ(X⃗), a Rabin treeautomaton—an automaton over infinite trees which is, in essence, a tree automaton with an acceptance condition based on the sets of states that occur infinitely often along the paths of the tree—which accepts a P(X⃗)- labeled tree iff it encodes a satisfying assignment for φ(X⃗). It follows that (∃X⃗)[φ(X⃗)] ∈ S2S iff the set of trees accepted by this automaton is non-empty. He then shows that the class of sets of labeled trees accepted by these automata (the class of Rabin recognizable sets) is closed under

00 0 01 02 ε 10 1 11  2

Figure 4. Embedding SωS in S2S.

Boolean operations and that emptiness is decidable for these sets. Thus, the result extends to arbitrary formulae over the signature of S2S and satisfiability in S2S is decidable.

Rabin generalizes this result to SnS for all n ≤ ω by showing that n_{n} for any such n can be embedded in n_{2} via the map h : T_{n} → (1^{∗}0)^{∗} where:

h(w) = \{ \begin{matrix}ε & if w = ε \\ h(u) · 1^{i} · 0 & if w = ui. \end{matrix}

This map locates the i^{th} child of w at the left child of the i^{th} node on the right-most branch of the subtree rooted at w. This is pretty much the standard way of interpreting an arbitrarily branching tree as a binary branching tree. The contribution of the proof is the observation that the range of h and the relations and functions of n_{n} in terms of the range of h are all definable on n_{2}.

Definition 9. A set 𝕋 of P -labeled trees, where P = {σ_{1}, …, σ_{m}}, is definable in SnS iff there is a formula φ(X_{U}, X_{1}, …, X_{m}) such that

n_{n} ⊧ φ[X_{U} ↦ T, X_{i} ↦ τ^{−1}(σ_{i})] ⇔ ⟨T, τ⟩ ∈ 𝕋.

In words, the trees in the set encode all and only the satisfying assignments for φ.

Theorem 4. A set of trees is definable in L_{K,P}^{2} iff it is definable in SωS.

Proof (Sketch). The crux of the proof^{4} is to show that immediate domination (◁) and linear precedence (≺) are definable in SωS and that root (ε), lexicographic order (⪯≀), and the successor functions (r_{i}) are definable in L_{K,P}^{2} . This is not hard. Let T = ⟨T, τ⟩ and s = x ↦ v, y ↦ w for some v, w ∈ T. Then, first we have:

T ⊧ x ◁ y [s] ⇔ n_{ω} ⊧ x ◁^{∗} y ∧ (∀z)[(z ◁^{∗} y ∧ ¬y ◁^{∗} z) → z ◁^{∗} x] [s]
T ⊧ x ≺ y [s] ⇔ n_{ω} ⊧ x⪯≀y ∧ ¬x ◁^{∗} y [s].

Which simply says that (the point assigned to) x is the parent of (the point assigned to) y iff it dominates y and all points that properly dominate y (i.e., that dominate y but are not themselves dominated by y) dominate x. For linear precedence, it says that x is left of y iff it precedes y in lexicographic order but does not dominate it. For the other direction we have:

n_{ω} ⊧ ε ≈ x [s] ⇔ T ⊧ (∀z)[x ◁^{∗} z] [s]
n_{ω} ⊧ x⪯≀y [s] ⇔ T ⊧ x ◁^{∗} y ∨ x ≺ y [s]
n_{ω} ⊧ r_{0}(x) ≈ y ⇔ T ⊧ x ◁ y ∧ (∀z)[x ◁ z → z ⊀ y] [s]
n_{ω} ⊧ r_{i+1}(x) ≈ y ⇔ T ⊧ x ◁ y ∧ (∀z)[r_{i}(x) ≺ z → (y ◁^{∗} z ∨ y ≺ z)] [s]

In words, x is the root iff it dominates all points in T, it lexicographically precedes (or is equal to) y iff it dominates y or is left-of y, and y is the 0^{th} successor of x iff it is a child of x and no child of x is left-of y. The i + 1^{st} successor function is defined in terms of the i^{th} : y is the i + 1^{st} successor of x iff it is a child of x and every point right-of the i^{th} successor of x is either dominated by y or to its right. This, of course, introduces r_{i}, which then must be expanded in the same way. Since i ∈ IN the translation of any SωS formula will terminate after finitely many such steps.

Note that this theorem is not true for any n < ω, even if we restrict ourselves to finite trees. For any finite n it is simple to construct an L_{K,P}^{2} formula that requires, for instance, every point with any children at all to have at least n + 1 children. While there are infinitely many trees satisfying this formula, there can only be one satisfying assignment in n_{n}—the trivial tree (containing just the root)—for any translation of it into the language of SnS.

Lemma 2. Every set of finite trees definable in SnS for some n < ω is recognizable.

4For full details see [Rog96a]

This is a consequence of the fact that, if we restrict ourselves to sets of finite trees, Rabin’s tree automata reduce to ordinary tree automata. Note that this lemma holds only for finite n, which insures that the branching factor of the models is finitely bounded. It is easy to define sets of trees, even sets of finite trees, in SωS in which there is no finite bound on the branching factor; in fact, unless a formula explicitly includes such a bound, if it has models with n-ary branching it will have models with branching factors greater than n as well. Such sets are not recognizable.

Theorem 5. A set of finite trees with bounded branching is definable in L_{K,P}^{2} iff it is recognizable.

Proof. Clearly, if the set is definable in L_{K,P}^{2} and has bounded branching it is definable in SnS for some finite n and is, by the lemma, recognizable. For the other direction, we must show that every recognizable set is definable in L_{K,P}^{2} . This is straightforward. Given some automaton A = ⟨δ_{1}, …, δ_{l}⟩ ⊆ P × Q × Q^{∗} over the alphabet P and the set of states Q, the idea is to interpret the states in Q as set variables (which we will denote as the sequence Q⃗). Each of the triples defining the automaton can then be directly encoded into an L_{K,P}^{2} formula that holds at a sequence of points iff those points form a local tree at which the triple is satisfied. E.g., for the triple δ_{i} = ⟨P, Q_{0}, ⟨Q_{1}, Q_{2}, …, Q_{m}⟩⟩:

φ_{i}(x_{0}, …, x_{m}, Q⃗) = (∀y)[x_{0} ◁ y ↔ (y ≈ x_{1} ∨ y ≈ x_{2} ∨ ⋯ ∨ y ≈ x_{m})] ∧
x_{1} ≺ x_{2} ∧ x_{2} ≺ x_{3} ∧ ⋯ ∧ x_{m−1} ≺ x_{m} ∧
P (x_{0}) ∧ Q_{0}(x_{0}) ∧ Q_{1}(x_{1}) ∧ ⋯ ∧ Q_{n}(x_{m}).

We then collect these into a universally quantified formula that requires some triple to be satisfied by every local tree:

φ_{A}(Q⃗) = (∀x_{0}, …, x_{n})[⋁_{i} φ_{i}(x⃗, Q⃗)].

(This formula is finite only because there is a finite bound on the branching of the local trees that satisfy the triples; otherwise we would have to quantify over all sequences of nodes, which would require unboundedly many individual variables.) This gives us a formula that is satisfied by a tree relative to an assignment of the variables in Q⃗ to subsets of the tree. Such an assignment is, in essence, a run of the automaton on the tree. All that is then required is to add a conjunct requiring the root to be in the set assigned to one of the initial states in Q_{S} and to existentially quantify the Q⃗ and we have a sentence that is satisfied by a tree iff it is in A(Q_{S}).

Theorem 6 (Büchi [Büc60]). Every language definable in S1S is regular.

Here we must modify our notion of the string language defined by a set of models. Clearly, S1S models—unary branching trees—have yield languages that are limited to words of length one (and are consequently finite). Instead, we will take the string language defined by an S1S formula to be the path language of its set of models, that is, the strings labeling the path from the root to the leaf of these models. Since tree automata on unary-branching trees reduce to ordinary finite-state automata on strings these languages are regular. The other direction is a special case of the previous theorem.

Theorem 7 (Doner [Don70]). A language is context-free iff it is the yield of a set of finite trees definable in wSnS for some n < ω.

Since we are restricting ourselves to sets of finite trees and finiteness is definable in SnS, we need not restrict Doner’s result to weak SnS. Similarly, when we are working with sets of trees with bounded branching we can assume that the bound is given explicitly and work in SωS, equivalently L_{K,P}^{2} .

Corollary 2. A language is context-free iff it is the yield of a set of finite trees definable in SnS for some n < ω; equivalently, if it is the yield of a set of finite trees with bounded branching that is definable in L_{K,P}^{2} .

5. Unbounded Branching

As should be clear from the discussion of the previous section, there is something of a misfit between L_{K,P}^{2} and the recognizable and local sets. While the requirement that grammars and automata be finite restricts the latter to defining sets of trees with finitely bounded branching L_{K,P}^{2} suffers from no such restriction. The distinction would be, perhaps, a minor point if it were not for the fact that sets of trees in which there is no finite bound on the branching are characteristic of some linguistic analyses, in particular flat analyses of coordination. Perhaps the best known presentation of this is in GPSG [GKPS85]. The relevant component consists of three (finite) rule schemas and a linear precedence rule:

X ⟶ H[CONJ a_{0}], H[CONJ a_{i}]^{+} ⟨a_{0}, a_{1}⟩ ∈ {⟨and, NIL⟩ , ⟨NIL, and⟩ , ⟨neither, nor⟩ , ⟨or, NIL⟩ , ⟨NIL, or⟩} X[CONJ NIL] ⟶ H

X[CONJ a] ⟶ {[SUBCAT a]} , H a ∈ {and, both, but, neither, nor, or}

[CONJ a_{0}] ≺ [CONJ a_{1}] a_{0} ∈ {both, either, neither, NIL} a_{1} ∈ {and, but, nor, or}

Here X is not a variable but, rather, is a radically underspecified category (no features are specified at all). The effect of the first schema (the iterating coordination schema) is to allow any category to be expanded to a sequence of two or more categories, all of which are heads (and therefore are of the same basic grammatical type although they can differ considerably in details), in which any one is marked as a CONJ of type a_{0} while all the rest are marked as CONJ of the corresponding type a_{1}. The second and third schemas expand categories marked as [CONJ NIL] simply as the same category unmarked, and those marked [CONJ a] as and X, both X, etc. for a in and, both, etc. Finally the linear precedence rule requires categories marked with CONJ of type both, either, etc. to precede in the sequence all categories marked with CONJ of type and, but, etc. The effect is to license expansions of any category X into one of

X and X

X or X

neither X nor X

X … X and X

X and X … and X

X … X or X

neither X nor X … nor X Such an account is easy to capture in L_{K,P}^{2} . We will assume that P is

the (finite) set of feature matrices employed in the GPSG account.^{5} One can assert, for example, that the ⟨and, NIL⟩ instance of the iterating coordination schema is satisfied in the local tree rooted at the node assigned to x with:

(∃y_{0}, y_{1})[ x ◁ y_{0} ∧ x ◁ y_{1}∧
H(y_{0}) ∧ [CONJ and](y_{0})∧
(∀z)[(x ◁ z ∧ z ≉ y_{0}) → (H(z) ∧ [CONJ NIL](z))]]

This just says that x has at least two children, that one of them is a head and is marked [CONJ and], and that all the rest are heads and are marked [CONJ NIL]. The other rule schemas can be treated similarly.

5For details of this and other aspects of the treatment see [Rog97]

The linear precedence schema is just as easy to capture:

(∀x, y)[((∃z)[z ◁ x ∧ z ◁ y] ∧ [CONJ NIL](x) ∧ [CONJ and](y)) → x ≺ y].

Which just says that whenever x and y are siblings, x is marked [CONJ NIL] and y is marked [CONJ and], then x will precede y.

6. Generalized Local and Recognizable Sets

The iterating coordination schema is stateable in GPSG because GPSG specifically allows the Kleene star to be applied to categories on the righthand side of its rewrite rules. Thus these grammars are no longer finite, but are still finitely presentable. That is to say, the grammar consists of an infinite set of rewrite rules, but that set itself is generated by a finite grammar, in this case a regular grammar. Such a notion of grammar is not new. Langendoen refers to them as hypergrammars in [Lan76], where he motivates them with a flat account of coordination quite similar to the GPSG account. A class of hypergrammars is determined by both the class of the generated grammar and the class of the generating grammar, with the weak generative capacity being the larger of the capacities of the two. Here we will focus on the generated grammars, referring to infinite, but finitely presentable, sets of context-free rewrite rules as generalized CFGs, and to the sets of trees generated by them as generalized local sets. We will refer to the equivalent notions in the realm of tree automata as generalized tree automata and generalized recognizable sets. We are interested, in particular, in the variants in which the generated grammar (or automaton) is a regular set. This gives a slight generalization of the GPSG style grammars, in that, rather than restricting application of the Kleene star to individual non-terminals, we, in essence, admit arbitrary regular expressions on the rhs of rewrite rules.

Definition 10 (Regular Generalized Context-free Grammars). A regular generalized context-free grammar is a regular set of local trees over some alphabet Σ:

G ⊆ Σ × Σ^{∗}, regular.

Definition 11 (Regular Generalized Local Sets). A set of trees is a regular generalized local set iff it is admitted by a regular generalized CFG in the sense of Definition 3.

Definition 12 (Regular Generalized Tree Automata). A regular generalized tree automaton over an alphabet Σ and a finite set of states Q is a regular set of triples:

A ⊆ Σ × Q × Q^{∗}, regular.

Definition 13 (Regular Generalized Recognizable Sets). A set of trees is a regular generalized recognizable set iff it is A(Q_{S}) for some regular generalized tree automaton A and Q_{S}, where A(Q_{S}) is defined as in Definition 5.

As the fact that the iterating coordination schema of GPSG can be captured in L_{K,P}^{2} suggests, L_{K,P}^{2} suffices to define any regular generalized local set, and in fact any regular generalized recognizable set.

Lemma 3. Every regular generalized recognizable set is definable in L_{K,P}^{2} .

Proof. The construction of the proof of Theorem 5 is limited to bounded branching, first of all, because it employs individual variables to pick out the children of a node and only a fixed number of these can occur in a formula. We can circumvent this obstacle by using a single set variable in their stead, but this is still not quite enough. Since the set of triples is, in general, infinite, the disjunction over the formulae encoding the triples which is used to require one of these to hold at every local tree will not necessarily be finite. The way we overcome this is to follow the approach used in capturing the iterating coordination scheme. Rather than having a distinct formula for each triple, we use a distinct formula for each label/state pair ⟨P, Q⟩ ∈ P × Q, which will require the string of states assigned to the children of a point with label P and state Q to be in the set of sequences of states associated with ⟨P, Q⟩ in A. (If we regard the triples of the automaton as a set of (P × Q) ∪ Q-labeled local trees, this set is just the child language Ch_{⟨P,Q⟩}(A).) Since A is a regular generalized tree-automaton, this set of sequences is a regular language and thus, by Theorem 6, definable in S1S. Now, the set of children of a node, when ordered by linear precedence, is isomorphic to a unary branching tree. It follows that the set of sequences is definable in terms of ≺ (and some auxiliary labels, S⃗, say) on the set of children of a node. Let ψ_{⟨P,Q⟩}(X, Q⃗, S⃗) define Ch_{⟨P,Q⟩}(A) on X. Using these we can replace the formulae φ_{i}(x_{0}, …, x_{m}, Q⃗) with:

\begin{aligned}φ_{⟨Q,P ⟩}(x_{0}, X, Q⃗) & = & (P (x_{0}) ∧ Q(x_{0}) ∧ (∀y)[x_{0} ◁ y ↔ X(y)]) → \\ & & (∃S⃗)[ψ_{⟨P,Q⟩}(X, Q⃗, S⃗)], \end{aligned}

Since P and Q are both finite, there are but finitely many of such formulae. With this modification, the proof of Theorem 5 goes through.

B C D ⋯  ^{⟨A, s_{1}⟩}^{⟨B, s_{2}⟩} ^{⟨A′, s_{3}⟩}^{⟨D, s_{6}⟩} ⋯^{⟨A′, s_{5}⟩}^{⟨C, s_{4}⟩}^{G_{𝕋}(Q_{0})} h(𝕋) 𝕋 A  A · B C  · D  ⋯

Figure 5. Proof of Lemma 4

Corollary 3. Every regular generalized local set is definable in L_{K,P}^{2} .

This follows from the fact that the regular generalized local sets are a subclass of the regular generalized recognizable sets.

The question now arises whether we can do more than this. While L_{K,P}^{2} clearly cannot capture any class stronger than the context-free generalized recognizable sets (since such sets can have non-context free yield languages) is it possible to capture the context-free generalized recognizable sets in L_{K,P}^{2} ? The answer is no.

Lemma 4. Every set of finite trees definable in L_{K,P}^{2} is a regular generalized recognizable set.

Proof. Suppose 𝕋 is a set of finite P -labeled trees definable in L_{K,P}^{2} . The fact that 𝕋 is definable in L_{K,P}^{2} implies that it is definable in SωS, which

in turn implies that h(𝕋) ( =^{def} {h(T ) | T ∈ 𝕋}) is definable in S2S (where h is the embedding of SωS into S2S). From the proof of Lemma 1 we have, then, that there is CFG G_{𝕋} ⊆ (P′ × Q) × (P′ × Q)^{∗} and some Q_{S} ⊆ P′ × Q such that h(𝕋) = π_{1}(G_{𝕋}(Q_{S})). (Here P′ extends P with some arbitrary labels for the nodes falling between the nodes in the range of h.) Now, 𝕋 is certainly recognizable in the sense that the states (and hence labels) of any set of children depend only on the state and label of their parent (this follows from the fact that G_{𝕋}(Q_{S}) is local), so it is a generalized recognizable set of some sort. It remains only to show that the child languages of 𝕋 are regular. Note that, for any ⟨P, Q⟩ ∈ P ×Q we can pick out the subset of G_{𝕋} that licenses the images in G_{𝕋}(Q_{S}) of local trees in 𝕋 rooted at nodes labeled P and assigned state Q; and that these form a CFG G_{⟨P,Q⟩} generating, in essence, Ch_{⟨P,Q⟩}(𝕋) (modulo taking the first projection of the leaves). In the example of Figure 5, for the pair ⟨A, s_{1}⟩ this would include

⟨A, s_{1}⟩ ⟶ B ⟨A′, s_{3}⟩
⟨A′, s_{3}⟩ ⟶ C ⟨A′, s_{5}⟩
⟨A′, s_{5}⟩ ⟶ D ⟨A′, s_{7}⟩
⋮

Because h maps local trees in 𝕋 to right branching trees these CFGs are all right linear. Consequently, Ch_{⟨P,Q⟩}(𝕋) is regular for all P and Q and 𝕋 is a regular generalized recognizable set.

This, then, establishes the strong generative power of L_{K,P}^{2} with unrestricted branching.

Corollary 4. A set of finite trees is definable in L_{K,P}^{2} iff it is a regular generalized recognizable set, equivalently, iff it is a projection of a regular generalized local set.

7. Conclusions

The characterization of the recognizable sets in terms of definability in L_{K,P}^{2} was originally developed as a means of establishing languagetheoretic complexity results for theories of syntax that are presented as systems of constraints on the structure of trees. Here we have shown that if we don’t require L_{K,P}^{2} theories to explicitly establish the finite bound on branching that is a characteristic of recognizable sets then the class of sets they can define is a mild generalization of the class of sets of trees definable by GPSG-style grammars. Thus the natural strong generative capacity of L_{K,P}^{2} coincides with a linguistically natural class of sets of structures.

When coupled with the flexibility of L_{K,P}^{2} in expressing principles and constraints occurring in a variety of theories of syntax, this offers a new perspective on relationships between these theories. We have, for instance, shown that L_{K,P}^{2} suffices to capture both a substantially complete GB account of English D- and S-structure [Rog96a] and the syntactic component of the GPSG account of English of [GKPS85] (see [Rog97]). Because L_{K,P}^{2} gives a common formalization that is independent of the grammars and mechanisms employed to present these theories, it provides a framework for direct comparison of the properties of the sets of structures they license. In the case of GB and GPSG, issues that have been the focus of many contrasts of the two—like the distinction between transformational and monostratal theories—turn out to have little in the way of actual formal consequences. Distinctions that have been previously overlooked, on the other hand, in particular differences in the nature of linguistic universals, appear to be formally more significant [Rog96b]. As this model-theoretic approach is extended to more complex classes of sets of structures and is applied to a broader range of theories it promises to offer considerable insight into the regularities of natural language syntax that transcend specific theories and to the issues that actually distinguish them.

References

[Büc60] J. R. Büchi. Weak second-order arithmetic and finite automata. Zeitschrift

für mathematische Logik und Grundlagen der Mathematik, 6:66–92, 1960.

[Don70] John Doner. Tree acceptors and some of their applications. Journal of Computer and System Sciences, 4:406–451, 1970.

[GKPS85] Gerald Gazdar, Ewan Klein, Geoffrey Pullum, and Ivan Sag. Generalized Phrase Structure Grammar. Harvard University Press, 1985.

[Gor67] Saul Gorn. Explicit definitions and linguistic dominoes. In John F. Hart and Satoru Takasu, editors, Systems and Computer Science, Proceedings of the Conference held at Univ. of Western Ontario, 1965. Univ. of Toronto Press, 1967.

[GS84] Ferenc Gécseg and Magnus Steinby. Tree Automata. Akadémiai Kiadó, Budapest, 1984.

[Kay84] Richard S. Kayne. Connectedness and Binary Branching. Foris, Dordrecht, 1984.

[Lan76] D. Terrence Langendoen. On the weak generative capacity of infinite grammars. CUNYForum, 1:13–24, 1976.

[Rab69] Michael O. Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society, 141:1– 35, July 1969.

[Rog96a] James Rogers. A Descriptive Approach to Language-Theoretic Complexity. Studies in Logic, Language, and Information. CSLI Publications, 1996. To appear.

[Rog96b] James Rogers. A model-theoretic framework for theories of syntax. In 34th Annual Meeting of the Association for Computational Linguistics, UC Santa Cruz, 1996.

[Rog96c] James Rogers. Strict LT2 : Regular :: Local : Recognizable. Paper presented to LACL’96—Logical Aspects of Computational Linguistics, Villerslès Nancy, FR, 1996.

[Rog97] James Rogers. “Grammarless” phrase structure grammar. Linguistics and Philosophy, 1997. To Appear.

[Tha67] J. W. Thatcher. Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. Journal of Computer and System Sciences, 1:317–322, 1967.

University of Central Florida

E-mail address: jrogers@cs.ucf.edu