On regular languages over power sets

• Autorzy: Fernando T.

Identyfikatory

DOI

10.15398/jlm.v4i1.103

• Języki publikacji: EN

Abstrakty

EN

The power set of a finite set is used as the alphabet of a string interpreting a sentence of Monadic Second-Order Logic so that the string can be reduced (in a straightforward way) to the symbols occurring in the sentence. Simple extensions to regular expressions are described matching the succinctness of Monadic Second-Order Logic. A link to Goguen and Burstall’s notion of an institution is forged, and applied to conceptions within natural language semantics of time based on change.

Słowa kluczowe

EN

regular language; power set; MSO; Monadic Second-Order; institution

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Journal of Language Modelling
• Rocznik: 2016
• Tom: Vol. 4, No. 1
• Strony: 29--56
• Opis fizyczny: Bibliogr. 21 poz., tab.

Twórcy

autor

Fernando T.

• Trinity College Dublin, Ireland

Bibliografia

• [1] James F. Allen (1983), Maintaining knowledge about temporal intervals, Communications of the ACM, 26 (11): 832-843.
• [2] Kenneth R. Beesley and Lauri Karttunen (2003), Finite State Morphology, CSLI Publications, Stanford.
• [3] Torben Braüner (2014), Hybrid Logic, The Stanford Encyclopedia of Philosophy, http://plato.stanford.edu/archives/spr2014/entries/logic-hybrid/.
• [4] David R. Dowty (1979), Word Meaning and Montague Grammar, Reidel, Dordrecht.
• [5] Andrzej Ehrenfeucht and Paul Zeiger (1976), Complexity measures for regular expressions, J. Comput. Syst. Sci., 12 (2): 134-146.
• [6] Tim Fernando (2004), A finite-state approach to events in natural language semantics, Journal of Logic and Computation, 14 (1): 79-92.
• [7] Tim Fernando (2011), Finite-state representations embodying temporal relations, in Proceedings 9th International Workshop on Finite State Methods and Natural Language Processing, pp. 12-20.
• [8] Tim Fernando (2014), Incremental semantic scales by strings, in Proceedings EACL 2014 Workshop on Type Theory and Natural Language Semantics (TTNLS), pp. 63-71.
• [9] Tim Fernando (2015), The semantics of tense and aspect: A finite-state perspective, in S. Lappin and C. Fox, editors, Handbook of Contemporary Semantic Theory, pp. 203-236, Wiley-Blackwell, second edition.
• [10] Wouter Gelade and Frank Neven (2012), Succinctness of the komplement and negation of regular expressions, ACM Trans. Comput. Log., 13 (1): 4.1-4.19.
• [11] Joseph Goguen and Rod Burstall (1992), Institutions: Abstract model theory for specification and programming, J. ACM, 39 (1): 95-146.
• [12] Erich Grädel (2007), Finite model theory and descriptive complexity, in Finite Model Theory and Its Applications, pp. 125-230, Springer.
• [13] Markus Holzer and Martin Kutrib (2010), The complexity of regular(-like) expressions, in Developments in Language Theory, pp. 16-30, Springer.
• [14] Mans Hulden (2009), Regular expressions and predicate logic in finite-state language processing, in Finite-State Methods and Natural Language Processing, pp. 82-97, IOS Press.
• [15] Hans Kamp and Uwe Reyle (1993), From Discourse to Logic, Kluwer Academic Publishers, Dordrecht.
• [16] Ronald M. Kaplan and Martin Kay (1994), Regular models of phonological rule systems, Computational Linguistics, 20 (3): 331-378.
• [17] Leonid Libkin (2010), Elements of Finite Model Theory, Springer.
• [18] Marc Moens and Mark Steedman (1988), Temporal ontology and temporal reference, Computational Linguistics, 14 (2): 15-28.
• [19] Arthur N. Prior (1967), Past, Present and Future, Clarendon Press, Oxford.
• [20] Hans Reichenbach (1947), Elements of Symbolic Logic, London, Macmillan.
• [21] Anssi Yli-Jyrä and Kimmo Koskenniemi (2004), Compiling contextual restrictions on strings into finite-state automata, in Proceedings of the Eindhoven FASTAR Days.

Uwagi

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