nach oben

2016 | Buch

Kapitel lesen Erstes Kapitel lesen

Formal Grammar

20th and 21st International Conferences, FG 2015, Barcelona, Spain, August 2015, Revised Selected Papers. FG 2016, Bozen, Italy, August 2016, Proceedings

herausgegeben von: Prof. Annie Foret, Prof. Glyn Morrill, Dr. Reinhard Muskens, Rainer Osswald, Sylvain Pogodalla

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the refereed proceedings of the 20th and 21st International Conference on Formal Grammar 2015 and 2016, collocated with the European Summer School in Logic, Language and Information in August 2015/2016. The 19 revised full papers presented together with 2 invited talks were carefully reviewed and selected from a total of 34 submissions.
The focus of papers are as follows:
Formal and computational phonology, morphology, syntax, semantics and pragmaticsModel-theoretic and proof-theoretic methods in linguistics
Logical aspects of linguistic structure
Constraint-based and resource-sensitive approaches to grammar
Learnability of formal grammar
Integration of stochastic and symbolic models of grammar
Foundational, methodological and architectural issues in grammar and linguistics
Mathematical foundations of statistical approaches to linguistic analysis

Inhaltsverzeichnis

Frontmatter

Erratum to: The Proper Treatment of Linguistic Ambiguity in Ordinary Algebra

Christian Wurm, Timm Lichte

Formal Grammar 2015: Invited Papers

Frontmatter

Frames as Records

Abstract

We suggest a way of formalizing frames using records in type theory. We propose an analysis of frames as records which model situations (including events) and we suggest that frame types (record types) are important in both the analysis of the Partee puzzle concerning rising temperatures and prices and in the analysis of quantification which involves counting events rather than individuals likes passengers or ships passing through a lock.

Our original inspiration for frames comes from the work of [13, 14] and work on FrameNet (https://framenet.icsi.berkeley.edu). An important aspect of our approach to frames, which differs from the Fillmorean approach, is that we treat them as first class objects. That is, they can be arguments to predicates and can be quantified over. The proposal that we have made for solving the Partee puzzle is closely related to the work of [22, 23] whose inspiration is from the work of [1‐3] rather than Fillmore.

Robin Cooper

Types from Frames as Finite Automata

Abstract

An approach to frame semantics is built on a conception of frames as finite automata, observed through the strings they accept. An institution (in the sense of Goguen and Burstall) is formed where these strings can be refined or coarsened to picture processes at various bounded granularities, with transitions given by Brzozowski derivatives.

Tim Fernando

Formal Grammar 2015: Contributed Papers

Frontmatter

Cyclic Multiplicative-Additive Proof Nets of Linear Logic with an Application to Language Parsing

Abstract

This paper concerns a logical approach to natural language parsing based on proof nets (PNs), i.e. de-sequentialized proofs, of linear logic (LL). It first provides a syntax for proof structures (PSs) of the cyclic multiplicative and additive fragment of linear logic (CyMALL). A PS is an oriented graph, weighted by boolean monomial weights, whose conclusions \(\varGamma \) are endowed with a cyclic order \(\sigma \). Roughly, a PS \(\pi \) with conclusions \(\sigma (\varGamma )\) is correct (so, it is a proof net), if any slice \(\varphi (\pi )\), obtained by a boolean valuation \(\varphi \) of \(\pi \), is a multiplicative (CyMLL) PN with conclusions \(\sigma (\varGamma _r)\), where \(\varGamma _r\) is an additive resolution of \(\varGamma \), i.e. a choice of an additive subformula for each formula of \(\varGamma \). The correctness criterion for CyMLL PNs can be considered as the non-commutative counterpart of the famous Danos-Regnier (DR) criterion for PNs of the pure multiplicative fragment (MLL) of LL. The main intuition relies on the fact that any DR-switching (i.e. any correction or test graph for a given PN) can be naturally viewed as a seaweed, that is, a rootless planar tree inducing a cyclic order on the conclusions of the given PN. Unlike the most part of current syntaxes for non-commutative PNs, our syntax allows a sequentialization for the full class of CyMALL PNs, without requiring these latter to be cut-free.

One of the main contributions of this paper is to provide a characterization of CyMALL PNs for the additive Lambek Calculus and thus a geometrical (non inductive) way to parse sentences containing words with syntactical ambiguity (i.e., with polymorphic type).

Vito Michele Abrusci, Roberto Maieli

Algebraic Governance and Symmetry in Dependency Grammars

Abstract

We propose a purely algebraic approach to governance structure in dependency grammars aiming to capture all linguistic dependencies (such as morphological, lexico-semantic, etc.) in monoidal patterns. This provides a clear perspective and allows us to define grammars declaratively through classical projective structures. Using algebraic concepts the model is going to suggest some symmetries among languages.

Carles Cardó

On the Mild Context-Sensitivity of k-Tree Wrapping Grammar

Abstract

Tree Wrapping Grammar (TWG) has been proposed in the context of formalizing the syntactic inventory of Role and Reference Grammar (RRG). It is close to Tree Adjoining Grammar (TAG) while capturing predicate-argument dependencies in a more appropriate way and being able to deal with discontinuous constituents in a more general way. This paper is concerned with the formal properties of TWG. More particularly, it considers k-TWG, a constrained form of TWG. We show that for every k-TWG, a simple Context-Free Tree Grammar (CFTG) of rank k can be constructed, which is in turn equivalent to a well-nested Linear Context-Free Rewriting System (LCFRS) of fan-out \(k+1\). This shows that, when formalizing a grammar theory such as RRG, which is based on thorough and broad empirical research, we obtain a grammar formalism that is mildly context-sensitive.

Laura Kallmeyer

Distributional Learning and Context/Substructure Enumerability in Nonlinear Tree Grammars

Abstract

We study tree-generating almost linear second-order ACGs that admit bounded nonlinearity either on the context side or on the substructure side, and give distributional learning algorithms for them.

Makoto Kanazawa, Ryo Yoshinaka

Between the Event Calculus and Finite State Temporality

Abstract

Event Calculus formulas dealing with instantaneous and continuous change are translated into regular languages interpreted relative to finite models. It is shown that a model over the real line for a restricted class of these Event Calculus formulas (relevant for natural language semantics) can be transformed into a finite partition of the real line, satisfying the regular languages. Van Lambalgen and Hamm’s treatment of type coercion is reduced to changes in the alphabet from which the strings are formed.

Derek Kelleher, Tim Fernando, Carl Vogel

A Modal Representation of Graded Medical Statements

Abstract

Medical natural language statements uttered by physicians are usually graded, i.e., are associated with a degree of uncertainty about the validity of a medical assessment. This uncertainty is often expressed through specific verbs, adverbs, or adjectives in natural language. In this paper, we look into a representation of such graded statements by presenting a simple non-normal modal logic which comes with a set of modal operators, directly associated with the words indicating the uncertainty and interpreted through confidence intervals in the model theory. We complement the model theory by a set of RDFS-/OWL 2 RL-like entailment (if-then) rules, acting on the syntactic representation of modalized statements. Our interest in such a formalization is related to the use of OWL as the de facto standard in (medical) ontologies today and its weakness to represent and reason about assertional knowledge that is uncertain or that changes over time. The approach is not restricted to medical statements, but is applicable to other graded statements as well.

Hans-Ulrich Krieger, Stefan Schulz

Models for the Displacement Calculus

Abstract

The displacement calculus \(\mathbf {D}\) is a conservative extension of the Lambek calculus \(\mathbf {L1}\) (with empty antecedents allowed in sequents). \(\mathbf {L1}\) can be said to be the logic of concatenation, while \(\mathbf {D}\) can be said to be the logic of concatenation and intercalation. In many senses, it can be claimed that \(\mathbf {D}\) mimics \(\mathbf {L1}\) in that the proof theory, generative capacity and complexity of the former calculus are natural extensions of the latter calculus. In this paper, we strengthen this claim. We present the appropriate classes of models for \(\mathbf {D}\) and prove some completeness results; strikingly, we see that these results and proofs are natural extensions of the corresponding ones for \(\mathbf {L1}\).

Oriol Valentín

On Some Extensions of Syntactic Concept Lattices: Completeness and Finiteness Results

Abstract

We provide some additional completeness results for the full Lambek calculus and syntactic concept lattices, where the underlying structure is extended to tuples of arbitrary finite and infinite size. Whereas this answers an open question for finite tuples, infinite tuples have not been considered yet. Nonetheless, they have a number of interesting properties which we establish in this paper, such as a particular class of languages which results in a finite lattice.

Christian Wurm

Formal Grammar 2016: Contributed Papers

Frontmatter

Overtly Anaphoric Control in Type Logical Grammar

Abstract

In this paper we analyse anaphoric pronouns in control sentences and we investigate the implications of these kinds of sentences in relation to the Propositional Theory versus Property Theory question. For these purposes, we invoke the categorial calculus with limited contraction, a conservative extension of Lambek calculus that builds contraction into the logical rules for a customized slash type-constructor.

María Inés Corbalán, Glyn Morrill

A Single Movement Normal Form for Minimalist Grammars

Abstract

Movement is the locus of power in Minimalist grammars (MGs) but also their primary source of complexity. In order to simplify future analysis of the formalism, we prove that every MG can be converted into a strongly equivalent MG where every phrase moves at most once. The translation procedure is implemented via a deterministic linear tree transduction on the derivation tree language and induces at most a linear blow-up in the size of the lexicon.

Thomas Graf, Alëna Aksënova, Aniello De Santo

Word Ordering as a Graph Rewriting Process

Abstract

This paper shows how the correspondence between a unordered dependency tree and a sentence that expresses it can be achieved by transforming the tree into a string where each linear precedence link corresponds to one specific syntactic relation. We propose a formal grammar with a distributed architecture that can be used for both synthesis and analysis. We argue for the introduction of a topological tree as an intermediate step between dependency syntax and word order.

Sylvain Kahane, François Lareau

Undecidability of the Lambek Calculus with a Relevant Modality

Abstract

Morrill and Valentín in the paper “Computational coverage of TLG: Nonlinearity” considered an extension of the Lambek calculus enriched by a so-called “exponential” modality. This modality behaves in the “relevant” style, that is, it allows contraction and permutation, but not weakening. Morrill and Valentín stated an open problem whether this system is decidable. Here we show its undecidability. Our result remains valid if we consider the fragment where all division operations have one direction. We also show that the derivability problem in a restricted case, where the modality can be applied only to variables (primitive types), is decidable and belongs to the NP class.

Max Kanovich, Stepan Kuznetsov, Andre Scedrov

Introducing a Calculus of Effects and Handlers for Natural Language Semantics

Abstract

In compositional model-theoretic semantics, researchers assemble truth-conditions or other kinds of denotations using the lambda calculus. It was previously observed [26] that the lambda terms and/or the denotations studied tend to follow the same pattern: they are instances of a monad. In this paper, we present an extension of the simply-typed lambda calculus that exploits this uniformity using the recently discovered technique of effect handlers [22]. We prove that our calculus exhibits some of the key formal properties of the lambda calculus and we use it to construct a modular semantics for a small fragment that involves multiple distinct semantic phenomena.

Jirka Maršík, Maxime Amblard

Proof Nets for the Displacement Calculus

Abstract

We present a proof net calculus for the Displacement calculus and show its correctness. This is the first proof net calculus which models the Displacement calculus directly and not by some sort of translation into another formalism. The proof net calculus opens up new possibilities for parsing and proof search with the Displacement calculus.

Richard Moot

Countability: Individuation and Context

Abstract

Much of the recent countability research agrees on the idea that a satisfactory account of individuation in terms of what counts as “one” unit for counting is highly relevant for characterizing a semantics of the mass/count distinction. (What counts as “one” is not necessarily a formal atom in a Boolean algebra or a natural unit associated with natural kinds like cat.) Taking the most parsimonious stance, our main question is: If we have a full-fledged formal theory of individuation (what counts as “one”), what data would still remain to be explained for a formal theory of the mass/count distinction? Would classical mereology be sufficient to cover such data? And, if not, what minimal extensions would be required to classical mereology to do so? We conclude that, minimally, two dimensions of context sensitivity are needed to enrich a mereological semantics of count nouns denotations. The first kind of context sensitivity enables counting operations to apply by removing overlap from an overlapping set of individuated entities. The second kind of context sensitivity allows us to motivate how a set of individuated entities can sometimes be taken as a counts as “one” despite not being a formal atom or a natural unit associated with a natural kind.

Peter R. Sutton, Hana Filip

The Proper Treatment of Linguistic Ambiguity in Ordinary Algebra

Abstract

We present a first algebraic approximation to the semantic content of linguistic ambiguity. Starting from the class of ordinary Boolean algebras, we add to it an ambiguity operator \(\Vert \) and a small set of axioms which we think are correct for linguistic ambiguity beyond doubt. We then show some important, non-trivial results that follow from this axiomatization, which turn out to be surprising and not fully satisfying from a linguistic point of view. Therefore, we also sketch promising algebraic alternatives.

Christian Wurm, Timm Lichte

Backmatter

Titel: Formal Grammar
herausgegeben von: Prof. Annie Foret
Prof. Glyn Morrill
Dr. Reinhard Muskens
Rainer Osswald
Sylvain Pogodalla
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-53042-9
Print ISBN: 978-3-662-53041-2
DOI: https://doi.org/10.1007/978-3-662-53042-9