Gamma-Reduction in Type Theory of Acyclic Recursion

• Autorzy: Loukanova Roussanka

Identyfikatory

DOI

10.3233/FI-2019-1867

• Języki publikacji: EN

Abstrakty

EN

In this article, we introduce Moschovakis higher-order type theory of acyclic recursion L^λ_ar. We present the potentials of L^λ_ar for incorporating different reduction systems in L^λ_ar, with corresponding reduction calculi. At first, we introduce the original reduction calculus of L^λ_ar, which reduces L^λ_ar-terms to their canonical forms. This reduction calculus determines the relation of referential, i.e., algorithmic, synonymy between L^λ_ar-terms with respect to a chosen semantic structure. Our contribution is the definition of a (γ) rule and extending the reduction calculus of L^λ_ar and its referential synonymy to γ-reduction and γ-synonymy, respectively. The γ-reduction is very useful for simplification of terms in canonical forms, by reducing subterms having superfluous λ-abstraction and corresponding functional applications. Typically, such extra λ abstractions can be introduced by the λ-rule of the reduction calculus of L^λ_ar.

Słowa kluczowe

EN

algorithms; type theory recursion; acyclic recursion; reduction calculi; gamma-reduction; canonical form

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 170, nr 4
• Strony: 367--411
• Opis fizyczny: Bibliogr. 24 poz., tab.

Twórcy

autor

Loukanova Roussanka

• Department of Mathematics, Stockholm University, Stockholm, Sweden

Bibliografia

• [1] Moschovakis YN. Sense and denotation as algorithm and value. In: Oikkonen J, Väänänen J (eds.), Logic Colloquium ’90: ASL Summer Meeting in Helsinki, volume Volume 2 of Lecture Notes in Logic, pp. 210-249. Springer-Verlag, Berlin, 1993. URL https://projecteuclid.org/euclid.lnl/1235423715.
• [2] Moschovakis YN. The logic of functional recursion. In: ML DC, K D, D M, van Benthem J (eds.), Logic and Scientific Methods, volume 259, pp. 179-207. Springer, Dordrecht, 1997. URL https://doi.org/10.1007/978-94-017-0487-8_10.
• [3] Moschovakis YN. A Logical Calculus of Meaning and Synonymy. Linguistics and Philosophy, 2006. 29(1):27-89. doi:10.1007/s10988-005-6920-7. URL https://doi.org/10.1007/s10988-005-6920-7.
• [4] Gallin D. Intensional and Higher-Order Modal Logic: With Applications to Montague Semantics. North-Holland, 1975. ISBN 9781483274737.
• [5] Montague R. The Proper Treatment of Quantification in Ordinary English. In: Hintikka J, Moravcsik J, Suppes P (eds.), Approaches to Natural Language: Proceedings of the 1970 Stanford Workshop on Grammar and Semantics, pp. 221-242. Springer Netherlands, Dordrecht. ISBN 978-94-010-2506-5, 1973. doi:10.1007/978-94-010-2506-5_10. URL https://doi.org/10.1007/978-94-010-2506-5_10.
• [6] Hurkens AJC, McArthur M, Moschovakis YN, Moss LS, Whitney GT. The logic of recursive equations. Journal of Symbolic Logic, 1998. 63(2):451478. doi:10.2307/2586843. URL https://doi.org/10.2307/2586843.
• [7] Van Lambalgen M, Hamm F. The Proper Treatment Of Events. Explorations in Semantics. Wiley-Blackwell, Oxford, 2004. ISBN 978-1-405-11212-3.
• [8] Loukanova R. Reference, Co-reference and Antecedent-anaphora in the Type Theory of Acyclic Recursion. In: Bel-Enguix G, Jiménez-López MD (eds.), Bio-Inspired Models for Natural and Formal Languages, pp. 81-102. Cambridge Scholars Publishing. ISBN 1-4438-2725-8 (10), 978-1-4438-2725-6 (13), 2011.
• [9] Loukanova R. Semantics with the Language of Acyclic Recursion in Constraint-Based Grammar. In: Bel-Enguix G, Jiménez-López MD (eds.), Bio-Inspired Models for Natural and Formal Languages, pp. 103-134. Cambridge Scholars Publishing. ISBN 1-4438-2725-8 (10), 978-1-4438-2725-6 (13), 2011.
• [10] Loukanova R. Algorithmic Semantics of Ambiguous Modifiers by the Type Theory of Acyclic Recursion. In: Web Intelligence and Intelligent Agent Technology, IEEE/WIC/ACM International Conference, volume 3. IEEE Computer Society, Los Alamitos, CA, USA. ISBN 978-1-4673-6057-9, 2012 pp. 117-121. URL http://doi.ieeecomputersociety.org/10.1109/WI-IAT.2012.246.
• [11] Loukanova R. Semantic Information with Type Theory of Acyclic Recursion. In: Huang R, Ghorbani AA, Pasi G, Yamaguchi T, Yen NY, Jin B (eds.), Active Media Technology - 8th International Conference, AMT 2012, Macau, China, December 4-7, 2012. Proceedings, volume 7669 of Lecture Notes in Computer Science. Springer. ISBN 978-3-642-35235-5, 2012 pp. 387-398. URL https://doi.org/10.1007/978-3-642-35236-2_39.
• [12] Loukanova R. Algorithmic Granularity with Constraints. In: Imamura K, Usui S, Shirao T, Kasamatsu T, Schwabe L, Zhong N (eds.), Brain and Health Informatics, volume 8211 of Lecture Notes in Computer Science, pp. 399-408. Springer International Publishing. ISBN 978-3-319-02752-4, 2013. URL https://doi.org/10.1007/978-3-319-02753-1_40.
• [13] Loukanova R. Algorithmic Semantics for Processing Pronominal Verbal Phrases. In: Larsen HL, Martin-Bautista MJ, Vila MA, Andreasen T, Christiansen H (eds.), Flexible Query Answering Systems, volume 8132 of Lecture Notes in Computer Science, pp. 164-175. Springer Berlin Heidelberg. ISBN 978-3-642-40768-0, 2013. URL https://doi.org/10.1007/978-3-642-40769-7_15.
• [14] Loukanova R. A Predicative Operator and Underspecification by the Type Theory of Acyclic Recursion. In: Duchier D, Parmentier Y (eds.), Constraint Solving and Language Processing, volume 8114 of Lecture Notes in Computer Science, pp. 108-132. Springer Berlin Heidelberg. ISBN 978-3-642-41577-7, 2013. URL https://doi.org/10.1007/978-3-642-41578-4_7.
• [15] Loukanova R. Computational Syntax-Semantics Interface with Type-Theory of Acyclic Recursion for Underspecified Semantics. In: Osswald R, Retoré C, Sutton P (eds.), IWCS 2019 Workshop on Computing Semantics with Types, Frames and Related Structures. Proceedings of the Workshop. The Association for Computational Linguistics (ACL), Gothenburg, Sweden. ISBN 978-989-758-350-6, 2019 pp. 37-48. URL https://www.aclweb.org/anthology/W19-1005.
• [16] Loukanova R. Binding Operators in Type-Theory of Algorithms for Algorithmic Binding of Functional Neuro-Receptors. In: Ganzha M, Maciaszek L, Paprzycki M (eds.), Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, volume 11 of Annals of Computer Science and Information Systems. Polish Information Processing Society. ISBN 978-83-946253-9-9, 2017 pp. 57-66. URL https://doi.org/10.15439/2017F465.
• [17] Muskens R. Meaning and Partiality. Studies in Logic, Language and Information. CSLI Publications, Stanford, California, 1995. ISBN 1881526798 (9781881526797).
• [18] Loukanova R. Modeling Context Information for Computational Semantics with the Language of Acyclic Recursion. In: Pérez JB, Corchado JM, Moreno M, Julián V, Mathieu P, Canada-Bago J, Ortega A, Fernández-Caballero A (eds.), Highlights in Practical Applications of Agents and Multiagent Systems, volume 89 of Advances in Intelligent and Soft Computing, pp. 265-274. Springer. ISBN 978-3-642-19916-5, 2011. doi:10.1007/978-3-642-19917-2_32. URL https://doi.org/10.1007/978-3-642-19917-2_32.
• [19] Russell B. On Denoting. Mind, 1905. 14(56):479-493. URL http://www.jstor.org/stable/2248381.
• [20] Henkin L. Completeness in the Theory of Types. Journal of Symbolic Logic, 1950. 15(2):81-91. URL https://projecteuclid.org/euclid.jsl/1183730860.
• [21] Mostowski A. On a generalization of quantifiers. Fundamenta Mathematicae, 1957. 1(44):12-36. doi:10.4064/fm-44-1-12-36. URL https://doi.org/10.4064/fm-44-1-12-36.
• [22] Loukanova R. Generalized Quantification in Situation Semantics. In: Gelbukh A (ed.), Computational Linguistics and Intelligent Text Processing, volume 2276 of Lecture Notes in Computer Science, pp. 46-57. Springer Berlin / Heidelberg. ISBN 3-540-43219-1, 2002. URL https://doi.org/10.1007/3-540-45715-1_4.
• [23] Loukanova R. Quantification and Intensionality in Situation Semantics. In: Gelbukh A (ed.), Computational Linguistics and Intelligent Text Processing, volume 2276 of Lecture Notes in Computer Science, pp. 32-45. Springer Berlin / Heidelberg. ISBN 3-540-43219-1, 2002. URL https://doi.org/10.1007/3-540-45715-1_3.
• [24] Loukanova R. Typed Theory of Situated Information and its Application to Syntax-Semantics of Human Language. In: Christiansen H, Jiménez-López MD, Loukanova R, Moss LS (eds.), Partiality and Underspecification in Information, Languages, and Knowledge, pp. 151-188. Cambridge Scholars Publishing. ISBN 1-4438-7947-9 (10), 978-1-4438-7947-7 (13), 2017.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).