Narcissists Are Easy, Stepmothers Are Hard

Gorin D, Schröder L (2012)


Publication Language: English

Publication Type: Conference contribution, Original article

Publication year: 2012

Journal

Publisher: Springer-verlag

Edited Volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Series: Lecture Notes in Computer Science

City/Town: Berlin

Book Volume: 7213

Pages Range: 240-254

Conference Proceedings Title: Foundations of Software Science and Computational Structures Foundations of Software Science and Computational Structures

Event location: Tallinn

ISBN: 978-3-642-28728-2

DOI: 10.1007/978-3-642-28729-9_16

Abstract

Modal languages are well-known for their robust decidability and relatively low complexity. However, as soon as one adds a self-referencing construct, like hybrid logic's down-arrow binder, to the basic modal language, decidability is lost, even if one restricts binding to a single variable. Here, we concentrate on the latter case and investigate the logics obtained by restricting the nesting depth of modalities between binding and use. In particular, for distances strictly below 3 we obtain well-behaved logics with a relatively high descriptive power. We investigate the fragment with distance 1 in the framework of coalgebraic modal logic, for which we provide very general decidability and complexity results. For the fragment with distance 2 we focus on the case of Kripke semantics and obtain optimum complexity bounds (no harder than the base logic). We show that this fragment is expressive enough to accommodate the guarded fragment over the correspondence language. © 2012 Springer-Verlag Berlin Heidelberg.

Authors with CRIS profile

Related research project(s)

How to cite

APA:

Gorin, D., & Schröder, L. (2012). Narcissists Are Easy, Stepmothers Are Hard. In Foundations of Software Science and Computational Structures Foundations of Software Science and Computational Structures (pp. 240-254). Tallinn: Berlin: Springer-verlag.

MLA:

Gorin, Daniel, and Lutz Schröder. "Narcissists Are Easy, Stepmothers Are Hard." Proceedings of the 15th International Conference on Foundations of Software Science and Computational Structures Foundations of Software Science and Computational Structures, FOSSACS 2012, Tallinn Berlin: Springer-verlag, 2012. 240-254.

BibTeX: Download