The equivalence of leaf languages of tree adjoining grammars and monadic linear context-free grammars was shown about a decade ago. This paper presents a proof of the strong equivalence of these grammar formalisms. Non-strict tree adjoining grammars and monadic linear context-free grammars define the same class of tree languages. We also present a logical characterisation of this tree language class showing that a tree language is a member of this class iff it (...) is the two-dimensional yield of an MSO-definable three-dimensional tree language. (shrink)

Disfluencies include editing terms such as uh and um as well as repeats and revisions. Little is known about how disfluencies are processed, and there has been next to no research focused on the way that disfluencies affect structure-building operations during comprehension. We review major findings from both computational linguistics and psycholinguistics, and then we summarize the results of our own work which centers on how the parser behaves when it encounters a disfluency. We describe some new research showing that (...) information associated with misarticulated verbs lingers, and which adds to the large body of data on the critical influence of verb argument structures on sentence comprehension. The paper also presents a model of disfluency processing. The parser uses a Tree Adjoining Grammar to build phrase structure. In this approach, filled and unfilled pauses affect the timing of Substitution operations. Repairs and corrections are handled by a mechanism we term “Overlay,” which allows the parser to overwrite an undesired tree with the appropriate, correct tree. This model of disfluency processing highlights the need for the parser to sometimes coordinate the mechanisms that perform garden-path reanalysis with those that do disfluency repair. The research program as a whole demonstrates that it is possible to study disfluencies systematically and to learn how the parser handles filler material and mistakes. It also showcases the power of Tree Adjoining Grammars, a formalism developed by Aravind Joshi which has yielded results in many different areas of linguistics and cognitive science. (shrink)

We present an algorithm for simultaneously constructing both the syntax and semantics of a sentence using a Lexicalized Tree Adjoining Grammar (LTAG). This approach captures naturally and elegantly the interaction between pragmatic and syntactic constraints on descriptions in a sentence, and the inferential interactions between multiple descriptions in a sentence. At the same time, it exploits linguistically motivated, declarative specifications of the discourse functions of syntactic constructions to make contextually appropriate syntactic choices.

We present an implementation of a discourse parsing system for alexicalized Tree-Adjoining Grammar for discourse, specifying the integrationof sentence and discourse level processing. Our system is based on theassumption that the compositional aspects of semantics at thediscourse level parallel those at the sentence level. This coupling isachieved by factoring away inferential semantics and anaphoric features ofdiscourse connectives. Computationally, this parallelism is achievedbecause both the sentence and discourse grammar are LTAG-based and the sameparser works at both levels. (...) The approach to an LTAG for discourse has beendeveloped by Webber and colleagues in some recent papers. Our system takes a discourseas input, parses the sentences individually, extracts the basic discourseconstituent units from the sentence derivations, and reparses the discoursewith reference to the discourse grammar while using the same parser usedat the sentence level. (shrink)

We describe a categorial system (PPTS) based on partial proof trees(PPTs) as the building blocks of the system. The PPTs are obtained byunfolding the arguments of the type that would be associated with a lexicalitem in a simple categorial grammar. The PPTs are the basic types in thesystem and a derivation proceeds by combining PPTs together. We describe theconstruction of the finite set of basic PPTs and the operations forcombining them. PPTS can be viewed as a categorial system incorporating (...) someof the key insights of lexicalized tree adjoining grammar, namely the notionof an extended domain of locality and the consequent factoring of recursionfrom the domain of dependencies. PPTS therefore inherits the linguistic andcomputational properties of that system, and so can be viewed as a middleground between a categorial grammar and a phrase structure grammar. We alsodiscuss the relationship between PPTS, natural deduction, and linear logicproof-nets, and argue that natural deduction rather than a proof-net systemis more appropriate for the construction of the PPTs. We also discuss howthe use of PPTs allows us to localize the management of resources, therebyfreeing us from this management as the PPTs are combined. (shrink)

We describe a categorial system (PPTS) based on partial proof trees(PPTs) as the building blocks of the system. The PPTs are obtained byunfolding the arguments of the type that would be associated with a lexicalitem in a simple categorial grammar. The PPTs are the basic types in thesystem and a derivation proceeds by combining PPTs together. We describe theconstruction of the finite set of basic PPTs and the operations forcombining them. PPTS can be viewed as a categorial system incorporating (...) someof the key insights of lexicalized tree adjoining grammar, namely the notionof an extended domain of locality and the consequent factoring of recursionfrom the domain of dependencies. PPTS therefore inherits the linguistic andcomputational properties of that system, and so can be viewed as a ’middleground‘ between a categorial grammar and a phrase structure grammar. We alsodiscuss the relationship between PPTS, natural deduction, and linear logicproof-nets, and argue that natural deduction rather than a proof-net systemis more appropriate for the construction of the PPTs. We also discuss howthe use of PPTs allows us to ’localize‘ the management of resources, therebyfreeing us from this management as the PPTs are combined. (shrink)

We present Logical Description Grammar (LDG), a model ofgrammar and the syntax-semantics interface based on descriptions inelementary logic. A description may simultaneously describe the syntacticstructure and the semantics of a natural language expression, i.e., thedescribing logic talks about the trees and about the truth-conditionsof the language described. Logical Description Grammars offer a naturalway of dealing with underspecification in natural language syntax andsemantics. If a logical description (up to isomorphism) has exactly onetree plus truth-conditions as a model, it completely specifies (...) thatgrammatical object. More common is the situation, corresponding tounderspecification, in which there is more than one model. A situation inwhich there are no models corresponds to an ungrammatical input. (shrink)

We present Logical Description Grammar (LDG), a model ofgrammar and the syntax-semantics interface based on descriptions inelementary logic. A description may simultaneously describe the syntacticstructure and the semantics of a natural language expression, i.e., thedescribing logic talks about the trees and about the truth-conditionsof the language described. Logical Description Grammars offer a naturalway of dealing with underspecification in natural language syntax andsemantics. If a logical description (up to isomorphism) has exactly onetree plus truth-conditions as a model, it completely specifies (...) thatgrammatical object. More common is the situation, corresponding tounderspecification, in which there is more than one model. A situation inwhich there are no models corresponds to an ungrammatical input. (shrink)

An NP-hardness proof for non-local Multicomponent Tree Adjoining Grammar (MCTAG) by Rambow and Satta (1st International Workshop on Tree Adjoining Grammers 1992 ), based on Dahlhaus and Warmuth (in J Comput Syst Sci 33:456–472, 1986 ), is extended to some linguistically relevant restrictions of that formalism. It is found that there are NP-hard grammars among non-local MCTAGs even if any or all of the following restrictions are imposed: (i) lexicalization: every tree in the (...) class='Hi'>grammar contains a terminal; (ii) dominance links: every tree set contains at most two trees, and in every such tree set, there is a link between the foot node of one tree and the root node of the other tree, indicating that the former node must dominate the latter in the derived tree. This is the version of MCTAG proposed in Becker et al. (Proceedings of the 5th conference of the European chapter of the Association for Computational Linguistics 1991 ) to account for German long-distance scrambling. This result restricts the field of possible candidates for an extension of Tree Adjoining Grammar that would be both mildly context-sensitive and linguistically adequate. (shrink)

An attractive way to model the relation between an underspecified syntactic representation and its completions is to let the underspecified representation correspond to a logical description and the completions to the models of that description. This approach, which underlies the Description Theory of Marcus et al. 1983 has been integrated in Vijay-Shanker 1992 with a pure unification approach to Lexicalized Tree-Adjoining Grammars (Joshi et al. 1975, Schabes 1990). We generalize Description Theory by integrating semantic information, that is, we (...) propose to tackle both syntactic and semantic underspecification using descriptions. (shrink)

In setting up a formal system to specify a grammar formalism, the conventional (mathematical) wisdom is to start with primitives (basic primitive structures) as simple as possible, and then introduce various operations for constructing more complex structures. An alternate approach is to start with complex (more complicated) primitives, which directly capture some crucial linguistic properties and then introduce some general operations for composing these complex structures. These two approaches provide different domains of locality, i.e., domains over which various types (...) of linguistic dependencies can be specified. The latter approach, characterized as complicate locally, simplify globally (CLSG), pushes non‐local dependencies to become local, i.e., they arise in the basic primitive structures to start with.The CLSG approach has led to some new insights into syntactic description, semantic composition, language generation, statistical processing, and psycholinguistic phenomena, all these with possible relevance to the cognitive architecture of language. In this paper, we will describe these results in an introductory manner making use of the framework of lexicalized tree‐adjoining grammar (LTAG), a key example of the CLSG approach, thereby describing the interplay between formal analysis on the one hand and linguistic and processing issues on the other hand. (shrink)

Theories of natural language syntax often characterize grammatical knowledge as a form of abstract computation. This paper argues that such a characterization is correct, and that fundamental properties of grammar can and should be understood in terms of restrictions on the complexity of possible grammatical computation, when defined in terms of generative capacity. More specifically, the paper demonstrates that the computational restrictiveness imposed by Tree Adjoining Grammar provides important insights into the nature of human grammatical knowledge.

This paper surveys work on applying the insights of lexicalized grammars to low‐level discourse, to show the value of positing an autonomous grammar for low‐level discourse in which words (or idiomatic phrases) are associated with discourse‐level predicate–argument structures or modification structures that convey their syntactic‐semantic meaning and scope. It starts by describing a lexicalized Tree Adjoining Grammar for discourse (D‐LTAG). It then reviews an initial experiment in parsing text automatically, using both a lexicalized TAG and D‐LTAG, (...) and then touches upon issues involved in how lexico‐syntactic elements contribute to discourse semantics. The paper concludes with a brief description of the Penn Discourse TreeBank, a resource being developed for the study of discourse structure and semantics. (shrink)

Back in the 1980’s, the class of mildly context-sensitive formalisms was introduced so as to capture the syntax of natural languages. While the languages generated by such formalisms are constrained by the constant-growth property, the most well-known and used ones—like tree-adjoining grammars or multiple context-free grammars—generate languages which verify the stronger property of being semilinear. In, the operation of IO-substitution was created so as to exhibit mildly-context sensitive classes of languages which are not semilinear. In the present article, (...) we extend the notion of semilinearity, and characterize the Parikh image of the languages in IO, the closure of a class L of semilinear languages under IO-substitution, as universally-semilinear. Based on this result and on the work of Fischer on macro-grammars, we then show that IO is not closed under inverse homomorphism when L is closed under inverse homomorphism, and encompasses the class of regular languages. This result proves that IO is not a full AFL, where \ denotes the class of multiple context-free languages, closing an open question in Bourreau et al.. More importantly, our proof gives an insight into the relation between the non-closure under inverse homomorphism of \}\) and how IO-substitution breaks semilinearity. (shrink)

We recorded participants' eye movements while they read sentences containing verb‐phrase coordination. Results showed evidence of immediate processing disruption when a reflexive pronoun embedded in the conjoined verb phrase mismatched the sentence subject. We argue that this result is incompatible with models of human parsing that employ only bottom‐up parsing procedures, even when flexible constituency is employed. Models need to incorporate a mechanism similar to the adjoining operation in Tree‐Adjoining Grammar, in which one structure is inserted (...) into another. (shrink)

This paper develops a framework for TAG (Tree Adjoining Grammar) semantics that brings together ideas from different recent approaches. Then, within this framework, an analysis of scope is proposed that accounts for the different scopal properties of quantifiers, adverbs, raising verbs and attitude verbs. Finally, including situation variables in the semantics, different situation binding possibilities are derived for different types of quantificational elements.

In this paper, we introduce a system, Sentence Planning Using Description, which generates collocations within the paradigm of sentence planning. SPUD simultaneously constructs the semantics and syntax of a sentence using a Lexicalized Tree Adjoining Grammar (LTAG). This approach captures naturally and elegantly the interaction between pragmatic and syntactic constraints on descriptions in a sentence, and the inferential and lexical interactions between multiple descriptions in a sentence. At the same time, it exploits linguistically motivated, declarative speci- fications (...) of the discourse functions of syntactic constructions to make contextually appropriate syntactic choices. (shrink)

We compare our model of unsupervised learning of linguistic structures, ADIOS [1, 2, 3], to some recent work in computational linguistics and in grammar theory. Our approach resembles the Construction Grammar in its general philosophy (e.g., in its reliance on structural generalizations rather than on syntax projected by the lexicon, as in the current generative theories), and the Tree Adjoining Grammar in its computational characteristics (e.g., in its apparent affinity with Mildly Context Sensitive Languages). The (...) representations learned by our algorithm are truly emergent from the (unannotated) corpus data, whereas those found in published works on cognitive and construction grammars and on TAGs are hand-tailored. Thus, our results complement and extend both the computational and the more linguistically oriented research into language acquisition. We conclude by suggesting how empirical and formal study of language can be best integrated. (shrink)

This papers presents a compositional semantic analysis of interrogatives clauses in LTAG (Lexicalized Tree Adjoining Grammar) that captures the scopal properties of wh- and nonwh-quantificational elements. It is shown that the present approach derives the correct semantics for examples claimed to be problematic for LTAG semantic approaches based on the derivation tree. The paper further provides an LTAG semantic derivation of interrogative clauses under question embedding verbs.

The goal of this dissertation is twofold. First, we aim to identify the source of distributivity in natural language. Our hypothesis is that throughout the grammar, distributivity can be tracked down to a single operator. Two converging lines of reasoning help us identify this operator. One line emerges as a result of generalizing and unifying previously disparate treatments of distributivity in the domain of nominal quantifiers. The other line comes from analyzing the meaning of durative adverbials, with special attention (...) to their interaction with cumulative readings. Second, we aim to provide a unified formal semantic framework for the treatment of interactions between verbs and their arguments, most importantly aspect, plurality, and quantification, and to shed light on the way in which thematic arguments are associated with the verb in the lexicon and in the compositional process. Although existing frameworks deal with parts of this picture, no such unified framework exists to date. The theoretical results presented in this proposal include a novel argument in favor of a quantificational analysis of durative adverbials (Dowty, 1979; Moltmann, 1991); a novel account of cumulativity and distributivity that covers both the two-quantifier and three-quantifier case in the nominal domain, including readings prominently discussed by Schein (1993); a reason for severing not only the external, but also the internal argument from the semantics of the verb, in response to Kratzer (1996); and the first event-based semantics for Tree-adjoining grammar (TAG, Joshi et al., 1975). (shrink)

We introduce LTAG-spinal, a novel variant of traditional Lexicalized Tree Adjoining Grammar (LTAG) with desirable linguistic, computational and statistical properties. Unlike in traditional LTAG, subcategorization frames and the argument-adjunct distinction are left underspecified in LTAG-spinal. LTAG-spinal with adjunction constraints is weakly equivalent to LTAG. The LTAG-spinal formalism is used to extract an LTAG-spinal Treebank from the Penn Treebank with Propbank annotation. Based on Propbank annotation, predicate coordination and LTAG adjunction structures are successfully extracted. The LTAG-spinal Treebank makes (...) explicit semantic relations that are implicit or absent from the original PTB. LTAG-spinal provides a very desirable resource for statistical LTAG parsing, incremental parsing, dependency parsing, and semantic parsing. This treebank has been successfully used to train an incremental LTAG-spinal parser and a bidirectional LTAG dependency parser. (shrink)

This paper provides a unification-based implementation of Binding Theory (BT) for the English language in the framework of feature-based lexicalized tree-adjoining grammar (LTAG). The grammar presented here does not actually coindex any noun phrases, it merely outputs a set of constraints on co- and contraindexation that may later be processed by a separate anaphora resolution module. It improves on previous work by implementing the full BT rather than just Condition A. The main technical innovation consists in (...) allowing lists to appear as values of semantic features. (shrink)

We compare our model of unsupervised learning of linguistic structures, ADIOS [1], to some recent work in computational linguistics and in grammar theory. Our approach resembles the Construction Grammar in its general philosophy (e.g., in its reliance on structural generalizations rather than on syntax projected by the lexicon, as in the current generative theories), and the Tree Adjoining Grammar in its computational characteristics (e.g., in its apparent affinity with Mildly Context Sensitive Languages). The representations learned (...) by our algorithm are truly emergent from the (unannotated) corpus data, whereas those found in published works on cognitive and construction grammars and on TAGs are hand-tailored. Thus, our results complement and extend both the computational and the more linguistically oriented research into language acquisition. We conclude by suggesting how empirical and formal study of language can be best integrated. (shrink)

We outline an unsupervised language acquisition algorithm and offer some psycholinguistic support for a model based on it. Our approach resembles the Construction Grammar in its general philosophy, and the Tree Adjoining Grammar in its computational characteristics. The model is trained on a corpus of transcribed child-directed speech (CHILDES). The model’s ability to process novel inputs makes it capable of taking various standard tests of English that rely on forced-choice judgment and on magnitude estimation of linguistic (...) acceptability. We report encouraging results from several such tests, and discuss the limitations revealed by other tests in our present method of dealing with novel stimuli. (shrink)

I show how a conversational process that takes simple, intuitively meaningful steps may be understood as a sophisticated computation that derives the richly detailed, complex representations implicit in our knowledge of language. To develop the account, I argue that natural language is structured in a way that lets us formalize grammatical knowledge precisely in terms of rich primitives of interpretation. Primitives of interpretation can be correctly viewed intentionally, as explanations of our choices of linguistic actions; the model therefore fits our (...) intuitions about meaning in conversation. Nevertheless, interpretations for complex utterances can be built from these primitives by simple operations of grammatical derivation. In bridging analyses of meaning at semantic and symbol‐processing levels, this account underscores the fundamental place for computation in the cognitive science of language use. (shrink)

Proof-theoretic models of grammar are based on the view that an explicit characterization of a language comes in the form of the recursive enumeration of strings in that language. That recursive enumeration is carried out by a procedure which strongly generates a set of structural descriptions Σ and weakly generates a set of strings S; a grammar is thus a function that pairs an element of Σ with elements of S. Structural descriptions are obtained by means of Context-Free (...) phrase structure rules or via recursive combinatorics and structure is assumed to beuniform: binary branching trees all the way down. In this work we will analyse natural language constructions for which such a rigid conception of phrase structure is descriptively inadequate and propose a solution for the problem of phrase structure grammars assigning too much or too little structure to natural language strings: we propose that the grammar can oscillate between levels of computational complexity in local domains, which correspond to elementary trees in a lexicalised Tree Adjoining Grammar. (shrink)

Polarized unification grammar (PUG) is a linguistic formalism which uses polarities to better control the way grammar fragments interact. The grammar combination operation of PUG was conjectured to be associative. We show that PUG grammar combination is not associative, and even attaching polarities to objects does not make it order-independent. Moreover, we prove that no non-trivial polarity system exists for which grammar combination is associative. We then redefine the grammar combination operator, moving to the (...) powerset domain, in a way that guarantees associativity. The method we propose is general and is applicable to a variety of tree-based grammar formalisms. (shrink)

This paper addresses the problem of the origin and principle of Aristotle’s distinctions among the categories. It explores the possibilities of reformulating and reviving the “grammatical” theory, generally ascribed first to Trendelenburg. The paper brings two new perspectives to the grammatical theory: that of Aristotle’s own theory of syntax and that of contemporary linguistic syntax and semantics. I put forth a provisional theory of Aristotle’s categories in which (1) I propose that the Categories sets forth a theory of lexical structure, (...) with the ten categories emerging as lexical or semantic categories, and (2) I suggest conceptual links, both in Aristotle’s writings and in actuality, between these semantic categories and certain grammatical inflections. (shrink)

This paper addresses the problem of the origin and principle of Aristotle’s distinctions among the categories. It explores the possibilities of reformulating and reviving the “grammatical” theory, generally ascribed first to Trendelenburg. The paper brings two new perspectives to the grammatical theory: that of Aristotle’s own theory of syntax and that of contemporary linguistic syntax and semantics. I put forth a provisional theory of Aristotle’s categories in which (1) I propose that the Categories sets forth a theory of lexical structure, (...) with the ten categories emerging as lexical or semantic categories, and (2) I suggest conceptual links, both in Aristotle’s writings and in actuality, between these semantic categories and certain grammatical inflections. (shrink)

This paper studies the relation between some extensions of the non-associative Lambek Calculus NL and their interpretation in tree models (free groupoids). We give various examples of sequents that are valid in tree models, but not derivable in NL. We argue why tree models may not be axiomatizable if we add finitely many derivation rules to NL, and proceed to consider labeled calculi instead.We define two labeled categorial calculi, and prove soundness and completeness for interpretations that are (...) almost the intended one, namely for tree models where some branches of some trees may be resp. all branches of all trees must be infinitely extending. Extrapolating from the experiences in our quite simple systems, we briefly discuss some problems involved with the introduction of labels in categorial grammar, and argue that many of the basic questions are not yet understood. (shrink)

This paper examines feature selection for log linear models over rich constraint-based grammar (HPSG) representations by building decision trees over features in corresponding probabilistic context free grammars (PCFGs). We show that single decision trees do not make optimal use of the available information; constructed ensembles of decision trees based on different feature subspaces show signifi- cant performance gains (14% parse selection error reduction). We compare the performance of the learned PCFG grammars and log linear models over the same features.

It has sometimes been suggested that people represent the structure of action in terms of an action tree. A question now arises about the relationship between this action tree representation and people’s moral judgments. A natural hypothesis would be that people first construct a representation of the action tree and then go on to use this representation in making moral judgments. The present paper argues for a more complex view. Specifically, the paper reports a series of experimental (...) studies that appear to show that people’s moral judgments can actually impact their representations of the action tree itself. (shrink)

While rules and exemplars are usually viewed as opposites, this paper argues that they form end points of the same distribution. By representing both rules and exemplars as (partial) trees, we can take into account the fluid middle ground between the two extremes. This insight is the starting point for a new theory of language learning that is based on the following idea: If a language learner does not know which phrase‐structure trees should be assigned to initial sentences, s/he allows (...) (implicitly) for all possible trees and lets linguistic experience decide which is the “best” tree for each sentence. The best tree is obtained by maximizing “structural analogy” between a sentence and previous sentences, which is formalized by the most probable shortest combination of subtrees from all trees of previous sentences. Corpus‐based experiments with this model on the Penn Treebank and the Childes database indicate that it can learn both exemplar‐based and rule‐based aspects of language, ranging from phrasal verbs to auxiliary fronting. By having learned the syntactic structures of sentences, we have also learned the grammar implicit in these structures, which can in turn be used to produce new sentences. We show that our model mimicks children’s language development from item‐based constructions to abstract constructions, and that the model can simulate some of the errors made by children in producing complex questions. (shrink)

In this paper we discuss a new perspective on the syntax-semantics interface. Semantics, in this new set-up, is not ‘read off’ from Logical Forms as in mainstream approaches to generative grammar. Nor is it assigned to syntactic proofs using a Curry-Howard correspondence as in versions of the Lambek Calculus, or read off from f-structures using Linear Logic as in Lexical-Functional Grammar (LFG, Kaplan & Bresnan [9]). All such approaches are based on the idea that syntactic objects (trees, proofs, (...) fstructures) are somehow prior and that semantics must be parasitic on those syntactic objects. We challenge this idea and develop a grammar in which syntax and semantics are treated in a strictly parallel fashion. The grammar will have many ideas in common with the (converging) frameworks of categorial grammar and LFG, but its treatment of the syntax-semantics interface is radically different. Also, although the meaning component of the grammar is a version of Montague semantics and although there are obvious affinities between Montague’s conception of grammar and the work presented here, the grammar is not compositional, in the sense that composition of meaning need not follow surface structure. (shrink)

A method is described for inducing a type-logical grammar from a sample of bare sentence trees which are annotated by lambda terms, called term-labelled trees . Any type logic from a permitted class of multimodal logics may be specified for use with the procedure, which induces the lexicon of the grammar including the grammatical categories. A first stage of semantic bootstrapping is performed, which induces a general form lexicon from the sample of term-labelled trees using Fulop’s (J Log (...) Lang Inf 14(1):49–86, 2005) procedure. Next we present a two-stage procedure for performing distributional learning by unifying the lexical types that are initially discovered. The first structural unification algorithm in essence unifies the initial family of sets of types so that the resulting grammar will generate all term-labelled trees that follow the usage patterns evident from the learning sample. Further altering the lexical categories to generate a recursively extended language can be accomplished by a second unification. The combined unification algorithm is shown to yield a new type-logical lexicon that extends the learning sample to a possibly infinite (and possibly context-sensitive) language in a principled fashion. Finally, the complete learning strategy is analyzed from the perspective of algorithmic learning theory; the range of the procedure is shown to be a class of term-labelled tree languages which is finitely learnable from good examples (Lange et al in Algorithmic learning theory, Vol 872 of lecture notes in artificial intelligence, Springer, Berlin, pp 423–437), and so is identifiable in the limit as a corollary. (shrink)

Second-order abstract categorial grammars (de Groote in Association for computational linguistics, 39th annual meeting and 10th conference of the European chapter, proceedings of the conference, pp. 148–155, 2001) and hyperedge replacement grammars (Bauderon and Courcelle in Math Syst Theory 20:83–127, 1987; Habel and Kreowski in STACS 87: 4th Annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol 247, Springer, Berlin, pp 207–219, 1987) are two natural ways of generalizing “context-free” grammar formalisms for string and (...) tree languages. It is known that the string generating power of both formalisms is equivalent to (non-erasing) multiple context-free grammars (Seki et al. in Theor Comput Sci 88:191–229, 1991) or linear context-free rewriting systems (Weir in Characterizing mildly context-sensitive grammar formalisms, University of Pennsylvania, 1988). In this paper, we give a simple, direct proof of the fact that second-order ACGs are simulated by hyperedge replacement grammars, which implies that the string and tree generating power of the former is included in that of the latter. The normal form for tree-generating hyperedge replacement grammars given by Engelfriet and Maneth (Graph transformation. Lecture notes in computer science, vol 1764. Springer, Berlin, pp 15–29, 2000) can then be used to show that the tree generating power of second-order ACGs is exactly the same as that of hyperedge replacement grammars. (shrink)

This paper presents a simple and versatile tree-rewriting lexicalized grammar formalism, TAGLET, that provides an effective scaffold for introducing advanced topics in a survey course on natural language processing (NLP). Students who implement a strong competence TAGLET parser and generator simultaneously get experience with central computer science ideas and develop an effective starting point for their own subsequent projects in data-intensive and interactive NLP.

The analysis of survival data often aims at the prediction of failure time distribution. In cases of competing risk events, the time distributions of more than one failure are under investigation. In this paper, the comparison of two approaches to analyzing survival data with competing risks is presented. The analyses are performed by use of an ensemble of dipolar trees with and without adjustment to competing risks.

A modal logic is developed to deal with finite ordered binary trees a they are used in linguistics. A modal language is introduced with operators for the ‘mother of’, ‘first daughter of’ and ‘second daughter of’ relations together with their transitive reflexive closures. The relevant class of tree models is defined and three linguistic applications of this language are discussed: context free grammars, command relations, and trees decorated with feature structures. An axiomatic proof system is given for which completeness (...) is shown with respect to the class of finite ordered binary trees. A number of decidability results follow. (shrink)

We reformulate minimalist grammars as partial functions on term algebras for strings and trees. Using filler/role bindings and tensor product representations, we construct homomorphisms for these data structures into geometric vector spaces. We prove that the structure-building functions as well as simple processors for minimalist languages can be realized by piecewise linear operators in representation space. We also propose harmony, i.e. the distance of an intermediate processing step from the final well-formed state in representation space, as a measure of processing (...) complexity. Finally, we illustrate our findings by means of two particular arithmetic and fractal representations. (shrink)

Jones argues that extending Seneca kin terms to second cousins requires a revised version of Optimality Theoretic grammar. I extend Seneca terms using three constraints on expression of markers in nested binary classification trees. Multiple constraint rankings on a nested set coupled with local parity checking determines how a given kin classification grammar marks structural endogamy.

Analytical commentary -- Fruits upon one tree -- The continuation of the early draft into philosophy of mathematics -- Hidden isomorphism -- A common methodology -- The flatness of philosophical grammar -- Following a rule 185-242 -- Introduction to the exegesis -- Rules and grammar -- The tractatus and rules of logical syntax -- From logical syntax to philosophical grammar -- Rules and rule-formulations -- Philosophy and grammar -- The scope of grammar -- Some (...) morals -- Exegesis 185-8 -- Accord with a rule -- Initial compass bearings -- Accord and the harmony between language and reality -- Rules of inference and logical machinery -- Formulations and explanations of rules by examples -- Interpretations, fitting and grammar -- Further misunderstandings -- Exegesis 189-202 -- Following rules, mastery of techniques and practices -- Following a rule -- Practices and techniques -- Doing the right thing and doing the same thing -- Privacy and the community view -- On not digging below bedrock -- Private linguists and private linguists : Robinson Crusoe sails again -- Is a language necessarily shared with a community of speakers? -- Innate knowledge of a language -- Robinson Crusoe sails again -- Solitary cavemen and monolinguists -- Private languages and private languages -- Exegesis 203-37 -- Agreement in definitions, judgements, and form of life -- The scaffolding of facts -- The role of our nature -- Forms of life -- Agreement : consensus of human beings and their actions -- Exegesis 238-42 -- Grammar and necessity -- Setting the stage -- Leitmotifs -- External guidelines -- Necessary propositions and norms of representation -- Concerning the truth and falsehood of necessary propositions -- What necessary truths are about illusions of correspondence : ideal objects, kinds of reality, and ultra-physics -- The psychology of the A priori -- Knowledge -- Belief -- Certainty -- Surprise -- Discoveries and conjectures -- Compulsion -- Propositions of logic and laws of thought -- Alternative forms of representation -- The arbitrariness of grammar -- A kinship to the non-arbitrary -- Proof in mathematics -- Conventionalism. (shrink)

We callsyntactic coding a technique which converts syntactic principles or constraints on representations into grammatical rules which can be implemented in any given rule grammar. In this paper we show that any principle or constraint on output trees formalizable in a certain fragment of dynamic logic over trees can be coded in this sense. This allows to reduce in a mechanical fashion most of the current theories of government and binding into GPSG-style grammars. This will be exemplified with Rizzi'sRelativized (...) Minimality. (shrink)

This paper presents empirical studies and closely corresponding theoretical models of the performance of a chart parser exhaustively parsing the Penn Treebank with the Treebank’s own CFG grammar. We show how performance is dramatically affected by rule representation and tree transformations, but little by top-down vs. bottom-up strategies. We discuss grammatical saturation, including analysis of the strongly connected components of the phrasal nonterminals in the Treebank, and model how, as sentence length increases, the effective grammar rule size (...) increases as regions of the grammar are unlocked, yielding super-cubic observed time behavior in some configurations. (shrink)

I wholeheartedly endorse Grodzinsky's program of attempting to tie the particular deficits observed in Broca's aphasics' comprehension and production to changes in their mentally represented model of grammar. At the level of detail, however, I see problems with two specific changes that Grodzinsky posits. One is a default Agent-assignment strategy in comprehension. The other is the hypothesis that production involves pruning all functional projections above Agreement Phrase.

The ‘syntax’ and ‘combinatorics’ of my title are what Curry (1961) referred to as phenogrammatics and tectogrammatics respectively. Tectogrammatics is concerned with the abstract combinatorial structure of the grammar and directly informs semantics, while phenogrammatics deals with concrete operations on syntactic data structures such as trees or strings. In a series of previous papers (Muskens, 2001a; Muskens, 2001b; Muskens, 2003) I have argued for an architecture of the grammar in which finite sequences of lambda terms are the basic (...) data structures, pairs of terms syntax, semantics for example. These sequences then combine with the help of simple generalizations of the usual abstraction and application operations. This theory, which I call Lambda Grammars and which is closely related to the independently formulated theory of Abstract Categorial Grammars (de Groote, 2001; de Groote, 2002), in fact is an implementation of Curry’s ideas: the level of tectogrammar is encoded by the sequences of lambda-terms and their ways of combination, while the syntactic terms in those sequences constitute the phenogrammatical level. In de Groote’s formulation of the theory, tectogrammar is the level of abstract terms, while phenogrammar is the level of object terms. (shrink)

Many studies confirm the fact that women do not have sufficient knowledge about reproductive health, which is a significant problem nowadays due to the large percentage of people who suffer from infertility. A sources of knowledge from which information about health, including reproductive health, is obtained have various levels of reliability. The aim of the study was to use regression trees to find which of the analysed parameters had the greatest impact on the level of respondents’ knowledge about fertility and (...) the impact of diet on fertility. The study was conducted among women who practice dance in Max Dance studio in Białystok. The group consisted of 42 women with an average age of 26.3 years, dancing in various dance styles at various levels of proficiency. A questionnaire on lifestyle and a sources of information on fertility was used; the questionnaire also contained a knowledge test focused on reproductive health and the impact of diet on fertility, in which the questions were based on information from the latest research. Three regression trees were created for three indicators determining the level of respondents’ knowledge. The obtained results revealed certain areas that have a significant impact on the level of knowledge about reproductive health, which may require additional education. The use of the regression trees method made it possible to determine the relationships between the analysed data that were not fully visible after standard biostatistical analyses had been performed. The created trees can be useful in improving the process of disseminating knowledge about reproductive health among women of childbearing age. (shrink)