Logic and Algorithms in Computational Linguistics 2021 (LACompLing2021)

Description

This book assesses the place of logic, mathematics, and computer science in present day, interdisciplinary areas of computational linguistics. Computational linguistics studies natural language in its various manifestations from a computational point of view, both on the theoretical level (modeling grammar modules dealing with natural language form and meaning and the relation between these two) and on the practical level (developing applications for language and speech technology). It is a collection of chapters presenting new and future research. The book focuses mainly on logical approaches to computational processing of natural language and on the applicability of methods and techniques from the study of formal languages, programming, and other specification languages. It presents work from other approaches to linguistics, as well, especially because they inspire new work and approaches. Preface Contents Complexity of the Lambek Calculus and Its Extensions 1 Introduction 2 The Lambek Calculus and Its Limitations 2.1 The Lambek Calculus 2.2 Language Models 2.3 The Unit Constant 2.4 Lambek Grammars 2.5 Lambek Grammars and Context-Free Grammars 3 Complexity of the Lambek Calculus and Its Fragments 3.1 NP-Completeness of the Lambek Calculus 3.2 Polynomial and Pseudo-polynomial Algorithms 4 Additive Operations 5 ``Harmless'' and ``Dangerous'' Extensions 5.1 Classifying Extensions of the Lambek Calculus 5.2 The Displacement Calculus 5.3 The Lambek Calculus with Brackets 5.4 ``Harmless'' Extensions as ``Linear'' Ones 6 (Sub)exponentials 7 Kleene Star 8 Conclusion References Categorial Dependency Grammars: Analysis and Learning 1 Introduction to CDG 1.1 Surface Dependency Structures 1.2 CDG Types Express Dependency Valencies 1.3 Projective Dependencies and Anchors 1.4 Non-projective Dependencies 1.5 Non-projective Dependencies with Anchors 2 CDG Definitions 2.1 From Rules to Dependency Structures 2.2 Generated Languages 3 CDG Analysis 3.1 CDGAnalyst 3.2 CDGLab with Filtering 3.3 Greedy Parser 4 Grammatical Inference 4.1 Learnability Properties 4.2 Learnability of K-valued CDG 5 K-star CDG 5.1 Learning Approaches with Iterated Types 5.2 TGE-Algorithm 5.3 Criteria and Readings of the ``Repetition Principle'' 5.4 Experiments on Corpora and Prospective Work 6 Open Problems 6.1 CDG-Types and Learning from Structures 6.2 Membership Properties and Hierarchies 6.3 Abstract Family of Languages 7 Conclusion References Diamonds Are Forever 1 Introduction 1.1 The Lambek Hierarchy 1.2 Modalities for Structural Control 2 Dependency-Enhanced Types 2.1 Rethinking Constituency 2.2 Case Study: Dutch Verb Clusters 3 Dependencies and Neural Language Models 3.1 Experimental Design 3.2 Results and Analysis 4 Conclusion References A Hybrid Approach of Distributional Semantics and Event Semantics for Telicity 1 Introduction 2 Background and Related Work 2.1 Eventuality 2.2 Logic-Based Computational Linguistics 2.3 Corpus-Based Computational Linguistics 3 System Overview 3.1 Syntactic Analysis 3.2 Semantic Analysis 3.3 Aspect Analysis 3.4 Theorem Proving 4 System Demonstration 5 Discussion and Conclusion References Generalized Computable Models and Montague Semantics 1 Introduction 2 Basic Notions of Generalized Computability 3 Montague Intensional Logic 4 Ershov-Scott Functional Spaces 5 Rank and Vector Models of Intensional Logic 5.1 Isomorphism Between Rank and Vector Models 6 Interpreting the Semantics of Possible Worlds 6.1 Interpretation of Possible Worlds Semantics for Simplest Model 6.2 Interpretation of Semantics of Possible Worlds for Vector Model 6.3 Analysis of Past Simple, Future Simple and Present Continuous in English References Multilingual Text Generation for Abstract Wikipedia in Grammatical Framework: Prospects and Challenges 1 Introduction 2 From Templates to Rendering Functions 3 Rendering Functions in Grammatical Framework 4 Abstraction Levels in GF 5 Smart Paradigms and the Lexicon 6 More Abstraction Levels 7 Improving the Style 8 Selecting Content 9 Authoring 10 Roles and Skills 11 First Results 12 Conclusion References Decomposing Events into GOLOG 1 Introduction 2 Data and Background 2.1 Events in Philosophy 2.2 Events in AI 2.3 Data 3 The Situation Calculus 3.1 The Language of the Situation Calculus 3.2 Domain Dependent and Independent Axioms 3.3 Aspect in GOLOG 4 Grammar to GOLOG 5 Future Work 6 Conclusion References Generating Pragmatically Appropriate Sentences from Logic: The Case of the Conditional and Biconditional 1 Introduction 1.1 Conditional Perfection 1.2 Generating Natural Language from Logical Formulas 1.3 Focus of the Paper 2 A Pragmatic Algorithm for Expressing Propositional Logic Formulas in English 2.1 Key Ideas Underlying the Algorithm 2.2 The Pragmatic Algorithm and the Baseline 2.3 Example of Input and Output 3 Evaluating the Algorithm 3.1 Design and Materials 3.2 Participants and Procedure 3.3 Results and Discussion 4 Conclusion and Future Work References White Roses, Red Backgrounds: Bringing Structured Representations to Search 1 Introduction 2 How Search Works 2.1 Inverted Indices 2.2 Beyond Inverted Indices 2.3 Ranking Features 2.4 An Example: Milk Chocolate Versus Chocolate Milk 3 Why Inverted Indices Are Not Enough 3.1 Vocabulary Mismatches 3.2 Mapping to Structured Data 3.3 Negation and Syntactic Structure 3.4 Robustness Through Embeddings 4 Towards a Solution: Incorporating Structure 4.1 Structure Where It Matters 4.2 Robustness Where Needed 4.3 Color-Object Queries 4.4 Towards Negation 5 Conclusion References Rules Are Rules: Rhetorical Figures and Algorithms 1 Introduction 2 Rhetorical Figures, a Primer 3 Figurative Functions 4 Figure Detection 5 Subtotal 6 Epanalepsis, Argument Foreclosure, and Semantic-Feature Promotion 7 Detecting `Chiasmus' 8 Antimetabole, Mesodiplosis, and Parison; AMP Constructions 8.1 Irrelevance of Order or Rank 8.2 Reciprocality 8.3 Comprehensiveness 9 Antithesis, Antimetabole, Mesodiplosis, and Parison; AAMP Constructions 9.1 Subclassification 9.2 Reject-Replace 10 Conclusion References Integrating Deep Neural Networks with Dependent Type Semantics 1 Introduction 1.1 Symbolic and Soft Reasoning 1.2 Criteria for a Soft Reasoning System 1.3 Names and Predicates in DTS 1.4 Are Symbolic and Soft Reasoning Incompatible? 2 Neural DTS 2.1 Real Numbers and Quotient Types 2.2 Setoids in DTS 2.3 Setoids of Natural Numbers, Integers, Rationals, and Reals 2.4 Embedding of an Entity into a Vector Space 2.5 Neural Classifiers as Predicates 3 Does Neural DTS Provide Soft Reasoning? 3.1 Continuous Truth Values 3.2 Comparable Representations 3.3 Learnable Representations 4 Verification Conditions for Predicates 5 Related Work 5.1 Logic and DNN 5.2 Natural Language and DNN 5.3 Programming Languages and DNN 6 Conclusion and Future Work References Meaning-Driven Selectional Restrictions in Remember Versus Imagine Whether 1 Introduction 2 Non-explanations 2.1 Anti-rogativity 2.2 Neg-Raising 2.3 Veridicality 3 Experiential Parasitism 3.1 Experientially Parasitic Attitudes 3.2 Experientially Parasitic Remembering 4 Veridicality Inferences in Remember-Reports 4.1 Semantics for Declarative Remember 4.2 Capturing Factivity Variation 4.3 Semantics for Interrogative Remember 5 Remembering and Imagining Whether 5.1 Remembering Whether 5.2 Imagining Whether 6 Outlook References A Unified Cluster of Valence Resources 1 Introduction 2 The Norwegian Valence Catalogue NorVal and the Computational Grammars NorSource and TypeGram 2.1 Basic Constructs of a Valence Catalogue: Lexvals and Valpods 2.2 Frame Types and Their Notation 2.3 Frame Types Represented in AVM Format, Combining Grammatical Functions and Logical Form 2.4 Grammars 2.5 Summary of a Unified Cluster of Valence Resources for Norwegian 3 Valence Catalogue for Ga (GaVal) 3.1 Overall Design of GaVal 3.2 Lexvals and Valpods in GaVal 3.3 Interacting CL Labels, AVMs and Semantic Specification 3.4 Summary: A Unified Cluster of Valence Resources for Ga 4 Final Remarks References