In this paper back-and-forth structures are applied to the semantics of natural language. Back-and-forth structures consist of an event structure and an interval structure communicating via a relational link; transitions in the one structure correspond to transitions in the other. Such entities enable us to view temporal constructions (such as tense, aspect, and temporal connectives) as methods of moving systematically between information sources. We illustrate this with a treatment of the English present perfect, and progressive aspect, that draws on ideas (...) developed in Moens & Steedman (1988), and discuss the role of rich ontologies in formal semantics. (shrink)

We introduce non-associative linear logic, which may be seen as the classical version of the non-associative Lambek calculus. We define its sequent calculus, its theory of proof-nets, for which we give a correctness criterion and a sequentialization theorem, and we show proof search in it is polynomial.

Compact Bilinear Logic , introduced by Lambek [14], arises from the multiplicative fragment of Noncommutative Linear Logic of Abrusci [1] by identifying times with par and 0 with 1. In this paper, we present two sequent systems for CBL and prove the cut-elimination theorem for them. We also discuss a connection between cut-elimination for CBL and the Switching Lemma from [14].

We provide an algorithm for determining a categorial grammar from linguistic data that essentially uses unification of type-schemes assigned to atoms. The algorithm presented here extends an earlier one restricted to rigid categorial grammars, introduced in [4] and [5], by admitting non-rigid outputs. The key innovation is the notion of an optimal unifier, a natural generalization of that of a most general unifier.

This paper is about a special version of PDL, proposed by Marcus Kracht, for reasoning about sibling ordered trees. It has four basic programs corresponding to the child, parent, left- and right-sibling relations in such trees. The original motivation for this language is rooted in the field of model-theoretic syntax. Motivated by recent developments in the area of semi-structured data, and, especially, in the field of query languages for XML (eXtensible Markup Language) documents, we revisit the language. This renewed interest (...) comes with a special focus on complexity and expressivity aspects of the language, aspects that have so far largely been ignored. We survey and derive complexity results, and spend most of the paper on the most important open question concerning the language: what is its expressive power? We approach this question from two angles: Which first-order properties can be expressed? And which second-order properties? While we are still some way from definitive answers to these questions, we discuss two first-order fragments of the PDL language for ordered trees, and show how the language can be used to express some typical (second-order) problems, like the boolean circuit and the frontier problem. (shrink)

We present a new axiomatization of the non-associative Lambek calculus. We prove that it takes polynomial time to reduce any non-associative Lambek categorial grammar to 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 offers an explanation of the fact that sentences of the form (1) ‘X may A or B’ may be construed as implying (2) ‘X may A and X may B’, especially if they are used to grant permission. It is suggested that the effect arises because disjunctions are conjunctive lists of epistemic possibilities. Consequently, if the modal may is itself epistemic, (1) comes out as equivalent to (2), due to general laws of epistemic logic. On the other hand, (...) on a deontic reading of may, (2) is only implied under exceptional circumstances – which usually obtain when (1) is used performatively. (shrink)

The Strongest Meaning Hypothesis of Dalrymple et al (1994,1998), which was originally proposed as a principle for the interpretation of reciprocals, is extended in this paper into a general principle of plural predication. This principle applies to complex predicates that are composed of lexical predicates that hold of atomic entities, and determines the pluralities in the extension of the predicate. The meaning of such a complex predicate is claimed to be the truth-conditionally strongest meaning that does not contradict lexical properties (...) of the simple predicates it contains. Weak interpretations of reciprocals (as in the books are stacked on top of each other), plural predicate conjunction (e.g. the books are old and new) and ’atomic’ distributivity in general are derived by a unified mechanism, which ’weakens’ the basic universal meanings of strong reciprocals, boolean conjunction and quantification over atomic entities. (shrink)

Sentences with multiple occurrences of plural definites give rise to certain effects suggesting that distributivity should be modeled by polyadic operations. Yet in this paper it is argued that the simpler treatment of distributivity using unary universal quantification should be retained. Seemingly polyadic effects are claimed to be restricted to definite NPs. This fact is accounted for by the special anaphoric (dependent) use of definites. Further evidence concerning various plurals, island constraints, and cumulative quantification is shown to support this claim. (...) In addition, it is shown that the evidence against a simple atomic version of unary distributivity is not decisive either. In the (uncommon) cases where distributivity with definites is not strictly atomic, they can be analyzed as dependent on implicit quantifiers. (shrink)

The aim of this paper is twofold: (i) to introduce the framework of update semantics and to explain what kind of semantic phenomena may successfully be analysed in it: (ii) to give a detailed analysis of one such phenomenon: default reasoning.

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.

Hailed by the Bulletin of the American Mathematical Society as "easy to use and a pleasure to read," this research monograph is recommended for students and professionals interested in model theory and definability theory. The sole prerequisite is a familiarity with the basics of logic, model theory, and set theory. 1974 edition.

We introduce and study a natural extension of Marcus external contextual grammars. This mathematically simple mechanism which generates a proper subclass of simple matrix languages, known to be mildly context-sensitive ones, is still mildly context-sensitive. Furthermore, we get an infinite hierarchy of mildly context-sensitive families of languages. Then we attempt to fill a gap regarding the linguistic relevance of these mechanisms which consists in defining a tree structure on the strings generated by many-dimensional external contextual grammars, and investigate some related (...) issues. Several open problems are finally discussed. (shrink)

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)

In this paper the notion of unifier is extended to the infinite set case. The proof of existence of the most general unifier of any infinite, unifiable set of types (terms) is presented. Learning procedure, based on infinite set unification, is described.

This book treats modal logic as a theory, with several subtheories, such as completeness theory, correspondence theory, duality theory and transfer theory and is intended as a course in modal logic for students who have had prior contact with modal logic and who wish to study it more deeply. It presupposes training in mathematical or logic. Very little specific knowledge is presupposed, most results which are needed are proved in this book.

Preface This book is about semantics and logic. More specifically, it is about the semantics and logic of natural language; and, even more specifically than ...

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)

Linear Syntax makes a case for a critical reassessment of the wide-spread view that syntax can be reduced to tree structures. It argues that a crucial part of the description of German clausal syntax should instead be based on concepts that are defined in terms of linear order. By connecting the descriptive tools of modern phrase-structure grammar with traditional descriptive scholarship, Andreas Kathol offers a new perspective on many long-standing problems in syntactic theory.

This first textbook on formal concept analysis gives a systematic presentation of the mathematical foundations and their relations to applications in computer science, especially in data analysis and knowledge processing. Above all, it presents graphical methods for representing conceptual systems that have proved themselves in communicating knowledge. The mathematical foundations are treated thoroughly and are illuminated by means of numerous examples, making the basic theory readily accessible in compact form.

This extended investigation of the semantics of event (and state) sentences in their various forms is a major contribution to the semantics of natural language, simultaneously encompassing important issues in linguistics, philosophy, and logic. It develops the view that the logical forms of simple English sentences typically contain quantification over events or states and shows how this view can account for a wide variety of semantic phenomena. Focusing on the structure of meaning in English sentences at a &"subatomic&" level&-that is, (...) a level below the one most theories accept as basic or &"atomic&"&-Parsons asserts that the semantics of simple English sentences require logical forms somewhat more complex than is normally assumed in natural language semantics. His articulation of underlying event theory explains a wide variety of apparently diverse semantic characteristics of natural language, and his development of the theory shows the importance of seeing the distinction between events and states. Parsons demonstrates that verbs, also, indicate kinds of actions rather than specific, individual actions. Verb phrases, too, he argues, depend on modifiers to make their function and meaning in a sentence specific. An appendix gives many of the details needed to formalize the theory discussed in the body of the text and provides a series of templates that permit the generation of atomic formulas of English. (shrink)

Inertia is enshrined in Newton’s first law of motion, a body at rest or in uniform motion remains in that state unless a force is applied to it. Now, consider (1). (1) Pat stopped the car before it hit the tree. Can we conclude from (1) that the car struck the tree? Not without further information such as that supplied in (2). (2) But the bus behind kept going. A post-condition for Pat stopping the car is that the car be (...) at rest. To satisfy a pre-condition for the car hitting the tree (namely, that the car not be at rest), inertia requires that some intervening force act on the car (as hinted, for example, by (2)). In the absence of such a force, (1) would appear to suggest that Pat prevented a collision between car and tree. Exactly what bit of physics are we importing into natural language interpretation here? Oversimplified, Newton’s first law of motion says: no change without force. Identifying force with cause, we come to the slogan no temporality without cause, capturing in a phrase the proposal from Steedman 2000 that.. (shrink)

It is routinely observed in NLP that sentences seem to “evoke” situations (where I use this term comprehensively to cover events, episodes, eventualities, processes, etc.). Much like discourse entities evoked by explicit noun phrases, these evoked situations can be referred to anaphorically, as for instance in (1) and (3) below, and can be modified in various ways, for instance by supplying their duration and location, as in (2) and (4).

Formal concept analysis as a methodology of data analysis and knowledge representation has potential to be applied to a variety of linguistic problems. First, linguistic applications often involve the identification and analysis of features, such as phonemes or syntactical or grammatical markers. Formal concept analysis can be used to record and analyze such features. The line diagrams of concept lattices can be used for communication among linguists about such features (see section 2). Second, modeling and storage of lexical information is (...) becoming increasingly important for natural language processing tasks. This causes a growing need for detailed lexical databases, which should preferably be automatically constructed. Section 3 describes the role that formal concept analysis can play in the automated or semi-automated construction of lexical databases from corpora. Third, lexical databases usually contain hierarchical components, such as hyponymy or type hierarchies. Because formal concept lattices are a natural representation of hierarchies and classifications, lexical databases can often be represented or analyzed using formal concept analysis. This is described in section 4. It should be remarked that because this paper appears in a collection volume of papers on formal concept analysis, the underlying notions, such as formal concept, formal object and attribute, and lattice, are not further explained in this paper. The reader is referred to Ganter & Wille (1999) for detailed information on formal concept analysis. (shrink)

The “surge in use of finite-state methods” ([10]) in computational linguistics has largely, if not completely, left semantics untouched. The present paper is directed towards correcting this situation. Techniques explained in [1] are applied to a fragment of temporal semantics through an approach we call finite-state temporality. This proceeds from the intuition of an event as “a series of snapshots” ([15]; see also [12]), equating snapshots with symbols that collectively form our alphabet. A sequence of snapshots then becomes a string (...) over that alphabet, evoking comic/film strips. Jackendoff has, among others, objected to conceptualizing events in terms of snapshots ([8]). To counter these objections, we step up from events-as-strings to event-typesas-regular languages ([5, 6]), recognizing the need for variable granularity. Beyond the introduction of disjunction implicit in the step from a single string up to a set of strings, we obtain a useful logic from the regular operations and a careful choice of the snapshots (constituting our alphabet). (shrink)

Linguists rely on intuitive conceptions of structure when comparing expressions and languages. In an algebraic presentation of a language, some natural notions of similarity can be rigorously defined (e.g. among elements of a language, equivalence w.r.t. isomorphisms of the language; and among languages, equivalence w.r.t. isomorphisms of symmetry groups), but it tums out that slightly more complex and nonstandard notions are needed to capture the kinds of comparisons linguists want to make. This paper identihes some of the important notions of (...) structural similarity, with attention to similarity claims that are prominent in the current linguistic tradition of transformational grammar. @ 2002 Elsevier Science B.V. All rights reserved. (shrink)