The IO and OI hierarchies revisited
| Autor: | Sylvain Salvati, Gregory M. Kobele |
|---|---|
| Přispěvatelé: | Computation Institute [Chicago], University of Chicago, Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Models for a Structured Programming of Space and Time (PoSET), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-12-CORD-0004,Polymnie,Analyse et synthèse dans les grammaires catégorielles abstraites : du lexique au discours(2012), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) |
| Rok vydání: | 2015 |
| Předmět: |
ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.3: Studies of Program Constructs/F.3.3.3: Program and recursion schemes
Formal semantics (linguistics) ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages/F.4.3.3: Decision problems Montague semantics 0102 computer and information sciences 01 natural sciences [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL] Theoretical Computer Science Denotational semantics [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] Rule-based machine translation Computer Science::Logic in Computer Science Higher-order grammars ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.2: Grammars and Other Rewriting Systems ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.2: Grammars and Other Rewriting Systems/F.4.2.3: Parsing Gödel's completeness theorem Formal language theory 0101 mathematics ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.2: Semantics of Programming Languages/F.3.2.1: Denotational semantics Mathematics Discrete mathematics Simply typed lambda-calculus Simply typed lambda calculus OI ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages 010102 general mathematics [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) IO Montague grammar ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.2: Grammars and Other Rewriting Systems/F.4.2.0: Decision problems 16. Peace & justice Computer Science Applications Decidability ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.1: Mathematical Logic/F.4.1.2: Lambda calculus and related systems Algebra Membership problem TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Computational Theory and Mathematics 010201 computation theory & mathematics TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS Emptiness Computer Science::Formal Languages and Automata Theory Natural language Information Systems |
| Zdroj: | Automata, Languages, and Programming ISBN: 9783642392115 ICALP (2) ICALP (2), Jul 2013, Riga, Latvia Information and Computation Information and Computation, Elsevier, 2015, 243, pp.205-221. ⟨10.1016/j.ic.2014.12.015⟩ Information and Computation, 2015, 243, pp.205-221. ⟨10.1016/j.ic.2014.12.015⟩ |
| ISSN: | 0890-5401 1090-2651 |
| DOI: | 10.1016/j.ic.2014.12.015 |
| Popis: | International audience; We study languages of lambda-terms generated by IO and OI unsafe grammars. These languages can be used to model meaning representations in the formal semantics of natural languages following the tradition of Montague. Using techniques pertaining to the denotational semantics of the simply typed lambda-calculus, we show that the emptiness and membership problems for both types of grammars are decidable. In the course of the proof of the decidability results for OI, we identify a decidable variant of the lambda-definability problem, and prove a stronger form of Statman's finite completeness Theorem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect