We present a new axiomatization of the non-associative Lambek categorial grammar. We prove that it takes polynomial time to translate any non-associative Lambek categorial grammar into an equivalent context-free grammar. Since it is possible to recognize a sentence generated by a context-free grammar in polynomial time, this proves that a sentence generated by any non-associative Lambek categorial grammar can be recognized in polynomial time.
This paper presents a categorial analysis of several types of verbs selecting a verbal complement in Dutch. In particular, we demonstrate that the various word orders found in the verbal complex can be accounted for by mechanisms operating in the lexicon only. Our theoretical starting point is the proposal of Jack Hoeksema, who accounts for `verb raising' by stipulating a polymorphic category for verbs inducing this type of word order. The effect of polymorphism is equivalent to using a categorial rule of division in the lexicon. We implement this rule as a recursive constraint. The coverage of the analysis is extended by showing that various other word order possibilities within the verb cluster imply that harmonic and disharmonic versions of division are needed. Finally, we argue that overgeneration can be avoided by requiring that the argument of a `verb raising' verb must be a `verbal complex'.
This paper presents an alternative approach to the Binding Theory (cf. Chomsky 1981, Pollard and Sag 1994, a.o). It will be argued that the core issue of such a theory should be locality constraints rather than descriptive content. We demonstrate that a reformulation of the Binding Theory in this spirit accounts more adequately for phenomena like kataphora and weak cross-over. We will furthermore place the approach in the perspective of a theory of discourse, and argue that the notion descriptive content belongs at the level of discourse rather than in sentence grammar.
This paper presents a formalisation of realizational approaches to inflectional morphology, exemplified by Anderson's Extended Word and Paradigm theory and Stump's Paradigm Function Morphology. The three levels of morphological organisation, namely the morpholexical rules, disjunctive blocks and conjunctive sequences, are modelled in typed feature structures as used in the context of Head-driven Phrase Structure Grammar.
This research is concerned with the genetic grammatical inference of formal languages: the induction of pushdown automata and context-free grammars for context-free languages from finite sets of example sentences from these languages using genetic algorithms. Setup of experiments and analyses of their results are presented. The induction of both deterministic and nondeterministic pushdown automata was successful; the induction of context-free grammars proved more difficult. A number of propositions are made for extensions and improvements.
In recent analyses in CCG, Steedman has suggested that the class of legitimate constituency bracketings is determined by intonational structure and its pragmatic interpretation. According to this theory, the intonational, informational and syntactic structures of English are one, and can be captured in a single unifed grammar. In this paper we argue that the prosodic grammar is higly restrictive. The only operation is Application. We argue against the original proposals of Steedman. Under the assumption that the derivation should directly define the domains of phonological implementation, we show that correct assingment of tonal domains only can be obtained if Application is the sole operation available in prosody. Finally we present a reanalysis of certain structures in which according to Steedman prosocic composition must apply, and argue for a more refined representation of the intonational forms as well as its interpretation.
This paper presents a genetic algorithm used to infer context-free grammars from legal and illegal examples of a language. It discusses the representation of grammar rules in the form of bitstrings by way of an interval coding scheme, genetic operators for reproduction of grammars, and the method of evaluating the fitness of grammars with respect to the training examples. Results are reported on the inference of several of these grammars. Grammars for the language of correctly balanced and nested brackets, the language of sentences containing an equal number of a's and b's, a set of regular languages, and a micro-NL language were inferred. Furthermore, some possible improvements and extensions of the algorithm are discussed.
Of all the time-honoured issues of semantics, the distinction between sense and reference ascribed to Frege is without doubt the most famous one. It has been applied time and again in the analysis of belief contexts. During many years the usefulness of the notions `sense' and `reference' have hardly been called into doubt. Only quite recently, however, (say, since Kripke) has there been a trend to question it. To mention only one example, Richard (1990, p. 60) writes `Frege's view of content and attitude ascription seems to me to be mistaken. So do its modern descendants'. On the other hand, Fregeanism has also quite recently been defended by a number of philosophers. Forbes, to mention just one of those modern descendants, has written a series of books and articles, one of which carrying the programmatic title `The indispensibility of Sinn'. Compare Forbes (1991). The present paper is mainly about the question of whether Forbes is right in his conviction that senses are indispensable. After a few introductory section I will give an extensive discussion of Forbes' so-called logophoric account. My conclusion will be that it, in spite of all its ingenuity, is too complex. Modal logic offers much more elegant ways to model the semantics of belief ascriptions. This is not to deny that senses are indispensable. Perhaps the most powerful argument in favor of senses may be found in intentional identity contexts. However, it would appear, however, that King (1993) is a viable analysis of intentional identity which does not make use of senses.
A formal framework is required to investigate the interaction between transformations and constraints with respect to the manner in which linguistic structures are described in Chomsky 1993. In this paper I will present the outline of one possible instantiation of such a formal framework. The formalism, Tree Logic, is based on First Order Predicate Logic and adopts a standard model-theoretic semantics. Tree Logic is interpreted in the domain of tree structure interpretations. Tree Logic is defined to a large extent analogously to Smolka's Feature Logic.
Semantic Syntax (SeSyn) is a grammatical theory still under development by Pieter Seuren. It describes how logic-based tree structures, called Semantic Analyses (SA) are mapped onto the surface structure of sentences by a language specific Generator in a two stage process: the cycle (which by applying transformations turns an SA into a shallow structure) and the post cycle (which converts the shallow structure into a surface structure). SeSynPro is the first attempt to implement Semantic Syntax (in Prolog). To implement the formation rules according to which the SAs have to be formed, a logic grammar (SALG, "SA Logic Grammar") is introduced that plays a role in several parts of the implementation. Pattern matching techniques are used to implement the transformations and the postcyclic operations on trees executed by the generator. SeSynPro makes extensive use of the graphic interface possibilities of the Apple Macintosh to make it as linguist friendly as possible. Crucial for this is the DrawTree module that draws trees in accordance with the conventions Seuren uses in his papers. Another feature is a graphic-oriented, formation rule driven SA-editor, that enables the user to draw SAs to be input to the generator, thus freeing him from specifying complicated input lists. Other graphic oriented editors will be added in the future (e.g. for the Formation Rules and the Transformations).
SEMANTIC SYNTAX (SeSyn) is a direct continuation of work done in the 60s and 70s under the name of GENERATIVE SEMANTICS. The main component of SeSyn is a rule system which transforms the Semantic Analysis (SA) of any given sentence into a Surface Structure (SS) of that sentence. SAs are formulated in a higher order Predicate Calculus, according to a small set of context-free Formation Rules and a Lexicon. SA-trees have simple branchings and deep embeddings. They are input to the Transformation Rules, which deliver a corresponding SS. The Transformation Rules fall into two classes, those of the Cycle, and those of the Postcycle. The former apply cyclically, starting with the most deeply embedded S and ending with the top-S. They are mostly lexicon-driven: predicates are lexically marked for the cyclic rules they induce. The largely structure-driven postcyclic rules apply in linear order as defined by the grammar. Morphology is largely, and phonology totally, left out of account. It is claimed that the fully implementable theory of SeSyn (significant parts have been implemented by Henk Schotel) makes for a subtler and more precise coverage of the facts of the languages treated than any other grammar system on the market. It moreover appears that language-specific differences amount largely to different postcyclic rule orderings, to different parameter settings in otherwise identical rules, to different lexical inductions of cyclic rules, or to different positions in the formation rules. When more grammars of different languages are available a parametrization of the general theory should be feasible. SA-trees are not entirely universal: they are to some extent still language-specific. They are, moreover, to some extent semantically redundant. They are language-specific in so far as different structures express identical meanings (eg. he could have eaten vs Dutch hij had kunnen eten). The structural differences must be manifest at SA-level if the syntax is to remain non-arbitrary. They are redundant in so far as scope sometimes has to be assigned where it is semantically irrelevant. For the grammar to work, adverbials and the tenses, for example, require precise scope assignments with respect to each other. For the semantics however, it is sometimes indifferent which comes first and which last. The paper illustrates how, in principle, structurally different translation equivalents between English and Dutch can be handled in a principled way. It must be seen as a small part of a large project extended over many years.
We describe an experiment of a two-level approach for the automated semantic analysis of N-N compounds. The first stage of the interpretation process consists of the translation of compounds into a representational format called Quasi Logical Form (QLF). The second stage consist of a mapping of QLFs onto domain-dependent, conceptual representations. Specifically, in the context of the Plinius project these QLFs are mapped onto relevant, formal expressions in terms of the so-called Plinius ontology KB. We briefly describe the linguistic analysis and then focus on a number of cases of deriving conceptual descriptions from QLFs. Our ultimate goal is to apply the method to a large ($>$ 2000) number of compounds within a specific domain.
To the Table of Contents.
To the Title page.