Some recent studies in computationallinguistics have aimed to take advantage of various cues presented by punctuation marks. This short survey is intended to summarise these research efforts and additionally, to outline a current perspective for the usage and functions of punctuation marks. We conclude by presenting an information-based framework for punctuation, influenced by treatments of several related phenomena in computationallinguistics.
Open peer commentary on the target article “How and Why the Brain Lays the Foundations for a Conscious Self” by Martin V. Butz. Excerpt: In this commentary to Martin V. Butz’s target article I am especially concerned with his remarks about language (§33, §§71–79, §91) and modularity (§32, §41, §48, §81, §§94–98). In that context, I would like to bring into discussion my own work on computational models of self-monitoring (cf. Neumann 1998, 2004). In this work I explore the (...) idea of an anticipatory drive as a substantial control device for modelling high-level complex language processes such as selfmonitoring and adaptive language use. My work is grounded in computationallinguistics and, as such, uses a mathematical and computational methodology. Nevertheless, it might provide some interesting aspects and perspectives for constructivism in general, and the model proposed in Butz’s article, in particular. (shrink)
Lexical semantics has become a major research area within computationallinguistics, drawing from psycholinguistics, knowledge representation, computer algorithms and architecture. Research programmes whose goal is the definition of large lexicons are asking what the appropriate representation structure is for different facets of lexical information. Among these facets, semantic information is probably the most complex and the least explored.Computational Lexical Semantics is one of the first volumes to provide models for the creation of various kinds of computerised lexicons (...) for the automatic treatment of natural language, with applications to machine translation, automatic indexing, and database front-ends, knowledge extraction, among other things. It focuses on semantic issues, as seen by linguists, psychologists, and computer scientists. Besides describing academic research, it also covers ongoing industrial projects. (shrink)
Narrative passages told from a character's perspective convey the character's thoughts and perceptions. We present a discourse process that recognizes characters' thoughts and perceptions in third-person narrative. An effect of perspective on reference in narrative is addressed: References in passages told from the perspective of a character reflect the character's beliefs. An algorithm that uses the results of our discourse process to understand references with respect to an appropriate set of beliefs is presented.
There is currently much interest in bringing together the tradition of categorial grammar, and especially the Lambek calculus, with the recent paradigm of linear logic to which it has strong ties. One active research area is designing non-commutative versions of linear logic (Abrusci, 1995; Retoré, 1993) which can be sensitive to word order while retaining the hypothetical reasoning capabilities of standard (commutative) linear logic (Dalrymple et al., 1995). Some connections between the Lambek calculus and computations in groups have long been (...) known (van Benthem, 1986) but no serious attempt has been made to base a theory of linguistic processing solely on group structure. This paper presents such a model, and demonstrates the connection between linguistic processing and the classical algebraic notions of non-commutative free group, conjugacy, and group presentations. A grammar in this model, or G-grammar is a collection of lexical expressions which are products of logical forms, phonological forms, and inverses of those. Phrasal descriptions are obtained by forming products of lexical expressions and by cancelling contiguous elements which are inverses of each other. A G-grammar provides a symmetrical specification of the relation between a logical form and a phonological string that is neutral between parsing and generation modes. We show how the G-grammar can be oriented for each of the modes by reformulating the lexical expressions as rewriting rules adapted to parsing or generation, which then have strong decidability properties (inherent reversibility). We give examples showing the value of conjugacy for handling long-distance movement and quantifier scoping both in parsing and generation. The paper argues that by moving from the free monoid over a vocabulary V (standard in formal language theory) to the free group over V, deep affinities between linguistic phenomena and classical algebra come to the surface, and that the consequences of tapping the mathematical connections thus established can be considerable. (shrink)
We combine state-of-the-art techniques from computational linguisticsand theorem proving to build an engine for playing text adventures,computer games with which the player interacts purely through naturallanguage. The system employs a parser for dependency grammar and ageneration system based on TAG, and has components for resolving andgenerating referring expressions. Most of these modules make heavy useof inferences offered by a modern theorem prover for descriptionlogic. Our game engine solves some problems inherent in classical textadventures, and is an interesting test case (...) for the interactionbetween natural language processing and inference. (shrink)
This book deals with a major problem in the study of language: the problem of reference. The ease with which we refer to things in conversation is deceptive. Upon closer scrutiny, it turns out that we hardly ever tell each other explicitly what object we mean, although we expect our interlocutor to discern it. Amichai Kronfeld provides an answer to two questions associated with this: how do we successfully refer, and how can a computer be programmed to achieve this? Beginning (...) with the major theories of reference, Dr Kronfeld provides a consistent philosophical view which is a synthesis of Frege's and Russell's semantic insights with Grice's and Searle's pragmatic theories. This leads to a set of guiding principles, which are then applied to a computational model of referring. The discussion is made accessible to readers from a number of backgrounds: in particular, students and researchers in the areas of computationallinguistics, artificial intelligence and the philosophy of language will want to read this book. (shrink)
This volume is a collection of original contributions from outstanding scholars in linguistics, philosophy and computationallinguistics exploring the relation between word meaning and human linguistic creativity. The papers present different aspects surrounding the question of what is word meaning, a problem that has been the center of heated debate in all those disciplines that directly or indirectly are concerned with the study of language and of human cognition. The discussions are centered around the newly emerging view (...) of the mental lexicon, as outlined in the Generative Lexicon theory (Pustejovsky, 1995), which proposes a unified model for defining word meaning. The individual contributors present their evidence for a generative approach as well as critical perspectives, which provides for a volume where word meaning is not viewed only from a particular angle or from a particular concern, but from a wide variety of topics, each introduced and explained by the editors. (shrink)
Some of the systems used in natural language generation (NLG), a branch of applied computationallinguistics, have the capacity to create or assemble somewhat original messages adapted to new contexts. In this paper, taking Bernard Williams’ account of assertion by machines as a starting point, I argue that NLG systems meet the criteria for being speech actants to a substantial degree. They are capable of authoring original messages, and can even simulate illocutionary force and speaker meaning. Background intelligence (...) embedded in their datasets enhances these speech capacities. Although there is an open question about who is ultimately responsible for their speech, if anybody, we can settle this question by using the notion of proxy speech, in which responsibility for artificial speech acts is assigned legally or conventionally to an entity separate from the speech actant. (shrink)
A primary problem in the area of natural language processing has been semantic analysis. This book looks at the semantics of natural languages in context. It presents an approach to the computational processing of English text that combines current theories of knowledge representation and reasoning in Artificial Intelligence with the latest linguistic views of lexical semantics. The book will interest postgraduates and researchers in computationallinguistics as well as industrial research groups specializing in natural language processing.
In spite of alleged differences in purpose, descriptive and computationallinguistics share many problems, due to the fact that any precise study on language needs some form of knowledge representation. This constraint is mostly apparent when interpretation of sentences takes into account elements of the so-called “context”. The parametrization of context, i.e. the explicit listing of features relevant to some intepretation task, is difficult because it requires flexible formal structures for understanding or simulating inferential behaviour, as well as (...) a large amount of information about conventional structures in the given language. This paper aims at illustrating major difficulties in these two fields, in relation with the necessity of a contextual approach. It offers a (clearly partial) enumeration of open problems inthe reperesentation of commonsense knowledge and languages-dependent structures, with some attempt to delineate future solutions. (shrink)
The notions of argument and argumentation have become increasingly ubiquitous in Artificial Intelligence research, with various application and interpretations. Less attention has been, however, specifically devoted to rhetorical argument The work presented in this paper aims at bridging this gap, by proposing a framework for characterising rhetorical argumentation, based on Perelman and Olbrechts-Tyteca's New Rhetoric. The paper provides an overview of the state of the art of computational work based on, or dealing with, rhetorical aspects of argumentation, before presenting (...) the characterisation proposed, corroborated by walked-through examples. (shrink)
Pregroups are partially ordered monoids in which each element has two “adjoints”. Pregroup grammars provide a computational approach to natural languages by assigning to each word in the mental dictionary a type, namely an element of the pregroup freely generated by a partially ordered set of basic types. In this expository article, the attempt is made to introduce linguists to a pregroup grammar of English by looking at Chomsky’s earliest examples.
We examine an argument for the non-context-freeness of English that has received virtually no discussion in the literature. It is based on adjuncts of the form ‘X or no X’, where X is a nominal. The construction has been held to exemplify unbounded syntactic reduplication. We argue that although the argument can be made in a mathematically valid form, its empirical basis is not claimed unbounded syntactic identity between nominals does not always hold in attested cases, and second, an understanding (...) of the semantics of the construction removes the necessity of making reference to any syntactic reduplication. (shrink)
Computational models of memory are often expressed as hierarchic sequence models, but the hierarchies in these models are typically fairly shallow, reflecting the tendency for memories of superordinate sequence states to become increasingly conflated. This article describes a broad-coverage probabilistic sentence processing model that uses a variant of a left-corner parsing strategy to flatten sentence processing operations in parsing into a similarly shallow hierarchy of learned sequences. The main result of this article is that a broad-coverage model with constraints (...) on hierarchy depth can process large newspaper corpora with the same accuracy as a state-of-the-art parser not defined in terms of sequential working memory operations. (shrink)
Typed feature structures are used extensively for the specification of linguistic information in many formalisms. The subsumption relation orders TFSs by their information content. We prove that subsumption of acyclic TFSs is well founded, whereas in the presence of cycles general TFS subsumption is not well founded. We show an application of this result for parsing, where the well-foundedness of subsumption is used to guarantee termination for grammars that are off-line parsable. We define a new version of off-line parsability that (...) is less strict than the existing one; thus termination is guaranteed for parsing with a larger set of grammars. (shrink)
We study the computational complexity of polyadic quantifiers in natural language. This type of quantification is widely used in formal semantics to model the meaning of multi-quantifier sentences. First, we show that the standard constructions that turn simple determiners into complex quantifiers, namely Boolean operations, iteration, cumulation, and resumption, are tractable. Then, we provide an insight into branching operation yielding intractable natural language multi-quantifier expressions. Next, we focus on a linguistic case study. We use computational complexity results to (...) investigate semantic distinctions between quantified reciprocal sentences. We show a computational dichotomy<br>between different readings of reciprocity. Finally, we go more into philosophical speculation on meaning, ambiguity and computational complexity. In particular, we investigate a possibility to<br>revise the Strong Meaning Hypothesis with complexity aspects to better account for meaning shifts in the domain of multi-quantifier sentences. The paper not only contributes to the field of the formal<br>semantics but also illustrates how the tools of computational complexity theory might be successfully used in linguistics and philosophy with an eye towards cognitive science. (shrink)
Many of the formalisms used in Attribute Value grammar are notational variants of languages of propositional modal logic, and testing whether two Attribute Value Structures unify amounts to testing for modal satisfiability. In this paper we put this observation to work. We study the complexity of the satisfiability problem for nine modal languages which mirror different aspects of AVS description formalisms, including the ability to express re-entrancy, the ability to express generalisations, and the ability to express recursive constraints. Two main (...) techniques are used: either Kripke models with desirable properties are constructed, or modalities are used to simulate fragments of Propositional Dynamic Logic. Further possibilities for the application of modal logic in computationallinguistics are noted. (shrink)
We expose the implications of lexical innovation as supported by the ONOMATURGE knowledge-based paradigm, for policies intended to foster native or national languages. In certain cases, the survival of native cultures, as supported by their language, depends on their ability to fill lexical gaps due to the technological gap. In certain other cases, the native culture itself is not in crisis (e.g., in the case of the national language of a sovereign country), but the local technologists or translators participate in (...) lexical innovation in a specific technical domain, and can benefit from the ONOMATURGE paradigm. (shrink)
In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial (...) time. Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)
Polysemy is a term used in semantic and lexical analysis to describe a word with multiple meanings. Although such words present few difficulties in everyday communication, they do pose near-intractable problems for linguists and lexicographers. The contributors in this volume consider the implications of these problems for linguistic theory and how they may be addressed in computationallinguistics.
We compare our model of unsupervised learning of linguistic structures, ADIOS [1, 2, 3], to some recent work in computationallinguistics 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 afﬁnity 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)
Stuart M. Shieber’s name is well known to computational linguists for his research and to computer scientists more generally for his debate on the Loebner Turing Test competition, which appeared a decade earlier in Communications of the ACM (Shieber 1994a, 1994b; Loebner 1994).1 With this collection, I expect it to become equally well known to philosophers.
The article reports the results from the developmentof four data-driven discovery systems, operating inlinguistics. The first mimics the induction methods ofJohn Stuart Mill, the second performs componentialanalysis of kinship vocabularies, the third is ageneral multi-class discrimination program, and thefourth finds logical patterns in data. These systemsare briefly described and some arguments are offeredin favour of machine linguistic discovery. Thearguments refer to the strength of machines incomputationally complex tasks, the guaranteedconsistency of machine results, the portability ofmachine methods to new tasks and (...) domains, and thepotential machines provide for our gaining newinsights. (shrink)
In this paper, I argue for a modified version of what Devitt (2006) calls the Representational Thesis (RT). According to RT, syntactic rules or principles are psychologically real, in the sense that they are represented in the mind/brain of every linguistically competent speaker/hearer. I present a range of behavioral and neurophysiological evidence for the claim that the human sentence processing mechanism constructs mental representations of the syntactic properties of linguistic stimuli. I then survey a range of psychologically plausible computational (...) models of comprehension and show that they are all committed to RT. I go on to sketch a framework for thinking about the nature of the representations involved in sentence processing. My claim is that these are best characterized not as propositional attitudes but, rather, as subpersonal states whose representational properties are determined by their functional role. Finally, I distinguish between explicit and implicit representations and argue that the latter can be drawn on as data by the algorithms that constitute our sentence processing routines. I conclude that skepticism concerning the psychological reality of grammars cannot be sustained. (shrink)
This book introduces the most important problems of reference and considers the solutions that have been proposed to explain them. Reference is at the centre of debate among linguists and philosophers and, as Barbara Abbott shows, this has been the case for centuries. She begins by examining the basic issue of how far reference is a two place (words-world) or a three place (speakers-words-world) relation. She then discusses the main aspects of the field and the issues associated with them, including (...) those concerning proper names; direct reference and individual concepts; the difference between referential and quantificational descriptions; pronouns and indexicality; concepts like definiteness and strength; and noun phrases in discourse. Professor Abbott writes with exceptional verve and wit. She presupposes no technical knowledge or background and presents issues and analyses from first principles, illustrating them at every stage with well-chosen examples. Her book is addressed in the first place to advanced undergraduate and graduate students in linguistics and philosophy of language, but it will also appeal to students and practitioners in computationallinguistics, cognitive psychology, and anthropology. All will welcome the clarity this guide brings to a subject that continues to challenge the leading thinkers of the age. (shrink)
The ability to produce and understand referring expressions is basic to human language use and human cognition. Reference comprises the ability to think of and represent objects (both real and imagined/fictional), to indicate to others which of these objects we are talking about, and to determine what others are talking about when they use a nominal expression. The articles in this volume are concerned with some of the central themes and challenges in research on reference within the cognitive sciences - (...) philosophy (including philosophy of language and mind, logic, and formal semantics), theoretical and computationallinguistics, and cognitive psychology. The papers address four basic questions: What is reference? What is the appropriate analysis of different referring forms, such as definite descriptions? How is reference resolved? and How do speaker/writers select appropriate referring forms, such as pronouns vs. full noun phrases, demonstrative vs. personal pronouns, and overt vs. null/zero pronominal forms? Some of the papers assume and build on existing theories, such as Centering Theory and the Givenness Hierarchy framework; others propose their own models of reference understanding or production. The essays examine reference from a number of disciplinary and interdisciplinary perspectives, informed by different research traditions and employing different methodologies. While the contributors to the volume were primarily trained in one of the four represented disciplines-computer science, linguistics, philosophy and psychology, and use methodologies typical of that discipline, each of them bridges more than one discipline in their methodology and/or their approach. (shrink)
For the past three decades linguistic theory has been based on the assumption that sentences are interpreted and constructed by the brain by means of computational processes analogous to those of a serial-digital computer. The recent interest in devices based on the neural network or parallel distributed processor (PDP) principle raises the possibility ("eliminative connectionism") that such devices may ultimately replace the S-D computer as the model for the interpretation and generation of language by the brain. An analysis of (...) the differences between the two models suggests that the effect of such a development would be to steer linguistic theory towards a return to the empiricism and behaviorism which prevailed before it was driven by Chomsky towards nativism and mentalism. Linguists, however, will not be persuaded to return to such a theory unless and until it can deal with the phenomenon of novel sentence construction as effectively as its nativist/mentalist rival. (shrink)
This paper presents a study of the effect of working memory load on the interpretation of pronouns in different discourse contexts: stories with and without a topic shift. We discuss a computational model (in ACT-R, Anderson, 2007) to explain how referring expressions are acquired and used. On the basis of simulations of this model, it is predicted that WM constraints only affect adults' pronoun resolution in stories with a topic shift, but not in stories without a topic shift. This (...) latter prediction was tested in an experiment. The results of this experiment confirm that WM load reduces adults' sensitivity to discourse cues signaling a topic shift, thus influencing their interpretation of subsequent pronouns. (shrink)
While situation theory and situation semantics provide an appropriate framework for a realistic model-theoretic treatment of natural language, serious thinking on their `computational' aspects has just started. Existing proposals mainly offer a Prolog- or Lisp-like programming environment with varying degrees of divergence from the ontology of situation theory. In this paper, we introduce a computational medium (called BABY-SIT) based on situations. The primary motivation underlying BABY-SIT is to facilitate the development and testing of programs in domains ranging from (...)linguistics to artificial intelligence in a unified framework built upon situation-theoretic constructs. (shrink)