Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
29--56
Opis fizyczny
Bibliogr. 21 poz., tab.
Twórcy
autor
- 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-82074569-cd6f-4e9c-9529-ac7be4d828eb