A logical approach to grammar description

• Autorzy: Clément L. , Kirman J. , Salvati S.

Identyfikatory

DOI

10.15398/jlm.v3i1.94

• Języki publikacji: EN

Abstrakty

EN

In the tradition of Model Theoretic Syntax, we propose a logical approach to the description of grammars. We combine in one formalism several tools that are used throughout computer science for their power of abstraction: logic and lambda calculus. We propose then a high-level formalism for describing mildly context sensitive grammars and their semantic interpretation. As we rely on the correspondence between logic and finite state automata, our method combines conciseness with effectivity. We illustrate our approach with a simple linguistic model of several interleaved linguistic phenomena involving extraction. The level of abstraction provided by logic and lambda calculus allows us not only to use this linguistic model for several languages, namely English, German, and Dutch, but also for semantic interpretation.

Słowa kluczowe

EN

grammar description; logic; finite state automata; logical transduction; lambda calculus; Abstract Categorial Grammars

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Journal of Language Modelling
• Rocznik: 2015
• Tom: Vol. 3, No. 1
• Strony: 87--143
• Opis fizyczny: Bibliogr. 49 poz., rys., tab.

Twórcy

autor

Clément L.

• Université de Bordeaux LaBRI, France

autor

Kirman J.

• Université de Bordeaux LaBRI, France

autor

Salvati S.

• Université de Bordeaux LaBRI, France

Bibliografia

• [1] Henk P. Barendregt (1984), The Lambda Calculus: Its Syntax and Semantics, volume 103, Studies in Logic and the Foundations of Mathematics, North-Holland Amsterdam, revised edition.
• [2] Philippe Blache (2001), Les grammaires de propriétés. Des contraintes pour le traitement automatique des langues naturelles, number 2-7462-0236-0 in Technologies et cultures, Hermes Science Publications.
• [3] Anudhyan Boral and Sylvain Schmitz (2013), Model-Checking Parse Trees, in Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS’13, pp. 153-162, IEEE Computer Society, Washington, DC, USA.
• [4] Joan Bresnan (2001), Lexical-functional syntax, volume 16 of Blackwell textbooks in linguistics, Blackwell.
• [5] Norbert Bröker (1998), Separating Surface Order and Syntactic Relations in a Dependency Grammar, in Proceedings of COLING-ACL98, pp. 174-180.
• [6] Marie-Hélène Candito (1999), Organisation modulaire et paramétrable de grammaires électroniques lexicalisées. Application au français et à l’italien., Ph.D. thesis, Université Paris 7.
• [7] Noam Chomsky (1981), Lectures on Government and Binding, in The Pisa Lectures, Foris Publications, Holland.
• [8] Thomas Cornell and James Rogers (1998), Model theoretic syntax, The Glot International State of the Article Book, 1: 101-125.
• [9] Bruno Courcelle (1994), Monadic second-order definable graph transductions: a survey, Theoretical Computer Science, 126: 53-75.
• [10] Bruno Courcelle and Joost Engelfriet (1995), A Logical Characterization of the Sets of Hypergraphs Defined by Hyperedge Replacement Grammars, Mathematical Systems Theory, 28 (6): 515-552.
• [11] Bruno Courcelle and Joost Engelfriet (2012), Graph Structure and Monadic Second-Order Logic, Encyclopedia of Mathematics and its Applications, Cambridge University Press.
• [12] Benoit Crabbé, Denys Duchier, Claire Gardent, Joseph Le Roux, and Yannick Parmentier (2013), XMG: eXtensible MetaGrammar, Computational Linguistics, 39 (3): 591-629.
• [13] Haskell B. Curry (1961), Some Logical Aspects of Grammatical Structure, in Roman Jakobson, editor, Structure of Language and Its Mathematical Aspects, pp. 56-68, AMS Bookstore.
• [14] Mary Dalrymple (2001), Lexical Functional Grammar, volume 34 of Syntax and Semantics, Academic Press, New York.
• [15] Philippe de Groote (2001), Towards Abstract Categorial Grammars, in Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics, ACL’01, pp. 252-259, Association for Computational Linguistics, Stroudsburg, PA, USA, doi: 10.3115/1073012.1073045.
• [16] Philippe de Groote and Sylvain Pogodalla (2004), On the expressive power of Abstract Categorial Grammars: Representing context-free formalisms, Journal of Logic, Language and Information, 13 (4): 421-438.
• [17] Ralph Debusmann, Denys Duchier, and Geert-Jan Kruijff (2004), Extensible Dependency Grammar: A New Methodology, in Recent Advances in Dependency Grammars, pp. 78-85.
• [18] John Doner (1965), Decidability of the weak second-order theory of two successors, Notices of the American Mathematical Society, 12: 365-468.
• [19] Denys Duchier, Thi-Bich-Hanh Dao, and Yannick Parmentier (2014), Model-theory and implementation of property grammars with features, Journal of Logic and Computation, 24 (2): 491-509.
• [20] Denys Duchier, Thi-Bich-Hanh Dao, Yannick Parmentier, and Willy Lesaint (2012), Property Grammar Parsing Seen as a Constraint Optimization Problem., in Philippe de Groote and Mark-Jan Nederhof, editors, Formal Grammar – 15th and 16th International Conferences, FG 2010-2012, volume 7395, pp. 82-96, Springer.
• [21] Denys Duchier, Jean-Philippe Prost, and Thi-Bich-Hanh Dao (2009), A model-theoretic framework for grammaticality judgements, in Conference on Formal Grammar (FG 2009), pp. 1-14.
• [22] Joost Engelfriet and Linda Heyker (1992), Context-free hypergraph grammars have the same term-generating power as attribute grammars, Acta Informatica, 29 (2): 161-210.
• [23] Kilian Foth, Wolfgang Menzel, and Ingo Schröder (2005), Robust parsing with weighted constraints, Natural Language Engineering, 11 (01): 1-25.
• [24] J. Roger Hindley and Jonathan P. Seldin (2008), Lambda-Calculus and Combinators, Cambridge University Press.
• [25] Aravind K. Joshi (1985), Tree-adjoining grammars: How much context sensitivity is required to provide reasonable structural descriptions?, in David Dowty, Lauri Karttunen, and Arnold M. Zwicky, editors, Natural Language Parsing, pp. 206-250, Cambridge University Press.
• [26] Makoto Kanazawa (2009), A lambda calculus characterization of MSO definable tree transductions, The Bulletin of Symbolic Logic, 15 (2): 250-251.
• [27] Makoto Kanazawa (2011), Parsing and Generation as Datalog Query Evaluation, Technical report, National Institute of Informatics.
• [28] Jérôme Kirman and Sylvain Salvati (2013), On the Complexity of Free Word Orders, in Proceedings of the 17th and 18th International Conferences on Formal Grammar, FG 2012, Opole, Poland, August 2012, FG 2013, Düsseldorf, Germany, August 2013, Revised Selected Papers, volume 8036 of Lecture Notes in Computer Science, pp. 209-224, Springer.
• [29] Gregory M. Kobele and Sylvain Salvati (2013), The IO and OI Hierarchies Revisited, in Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 2013, Part II), volume 7966 of Lecture Notes in Computer Science, pp. 336-348, Springer.
• [30] Hans-Peter Kolb, Jens Michaelis, Uwe Mönnich, and Frank Morawietz (2003), An operational and denotational approach to non-context-freeness, Theoretical Computer Science, 293 (2): 261-289.
• [31] Markus Kracht (1995), Syntactic codes and grammar refinement, Journal of Logic, Language, and Information, 4 (1): 41-60.
• [32] Richard Montague (1974), English as a Formal Language, in Richmond H. Thomason, editor, Formal philosophy: Selected Papers of Richard Montague, Yale University Press, New Haven.
• [33] Frank Morawietz (2003), Two-Step Approaches to Natural Language Formalism, number 64 in Studies in Generative Grammar, De Gruyter.
• [34] Geoffrey K. Pullum (2007), The evolution of model-theoretic frameworks in linguistics, in Proceedings of the ESSLLI 2007 Workshop on Model-Theoretic Syntax, volume 10, pp. 1-10.
• [35] Geoffrey K. Pullum and Barbara C. Scholz (2001), On the distinction between model-theoretic and generative-enumerative syntactic frameworks, in Proceedings of the International Conference on Logical Aspects of Computational Linguistics, volume Complete the number of volume of Complete the title of the series, pp. 17-43, Springer.
• [36] Geoffrey K. Pullum and Barbara C. Scholz (2005), Contrasting applications of logic in natural language syntactic description, in Logic, methodology and philosophy of science: Proceedings of the twelfth international congress, pp. 481-503.
• [37] Michael O. Rabin (1969), Decidability of Second-Order Theories and Automata on Infinite Trees, Transaction of the American Mathematical Society, 141: 1-35.
• [38] James Rogers (1996), A model-theoretic framework for theories of syntax, in Proceedings of the 34th annual meeting of the Association for Computational Linguistics, pp. 10-16, Association for Computational Linguistics.
• [39] James Rogers (1998), A descriptive approach to language-theoretic complexity, Studies in Logic, Language & Information, CSLI Publications, distributed by the University of Chicago Press.
• [40] James Rogers (2003a), Syntactic Structures as Multi-Dimensional Trees, Research on Language and Computation, 1 (3-4): 265-305.
• [41] James Rogers (2003b), wMSO theories as grammar formalisms, Theoretical Computer Science, 293 (2): 291-320.
• [42] John Robert Ross (1967), Constraints on variables in syntax, Ph.D. thesis, Massachusetts Institute of Technology.
• [43] Sylvain Salvati (2005), Problèmes de filtrage et problèmes d’analyse pour les grammaires catégorielles abstraites, Ph.D. thesis, Institut National Polytechnique de Lorraine.
• [44] Sylvain Salvati (2007), Encoding second order string ACG with Deterministic Tree Walking Transducers, in Shuly Wintner, editor, Proceedings of the 11th Conference on Formal Grammar (FG 2006), FG Online Proceedings, pp. 143-156, CSLI Publications.
• [45] Sylvain Salvati (2009), A Note on the Complexity of Abstract Categorial Grammars, in Marcus Kracht, Gerald Penn, and Ed Stabler, editors, The Mathematics of Language, 10th and 11th Biennial Conference, MOL 10, Los Angeles, CA, USA, July 28-30, 2007, and MOL 11, Bielefeld, Germany, August 20-21, 2009, Revised Selected Papers, pp. 266-271.
• [46] Sylvain Salvati (2010), On the membership problem for non-linear ACGs, Journal of Logic Language and Information, 19 (2): 163-183.
• [47] Stuart M. Shieber (1985), Evidence Against the Context-Freeness of Natural Language, Linguistics and Philosophy, 8: 333-343.
• [48] François Thomasset and Éric Villemonte De La Clergerie (2005), Comment obtenir plus des Méta-Grammaires, in Proceedings of TALN’05, ATALA, Dourdan, France.
• [49] David J. Weir (1988), Characterizing mildly context-sensitive grammar formalisms, Ph.D. thesis, University of Pennsylvania, Philadephia, PA.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).