Studia Logica 104 (3):455-486 (2016)

In the propositional modal treatment of two-variable first-order logic equality is modelled by a ‘diagonal’ constant, interpreted in square products of universal frames as the identity relation. Here we study the decision problem of products of two arbitrary modal logics equipped with such a diagonal. As the presence or absence of equality in two-variable first-order logic does not influence the complexity of its satisfiability problem, one might expect that adding a diagonal to product logics in general is similarly harmless. We show that this is far from being the case, and there can be quite a big jump in complexity, even from decidable to the highly undecidable. Our undecidable logics can also be viewed as new fragments of first-order logic where adding equality changes a decidable fragment to undecidable. We prove our results by a novel application of counter machine problems. While our formalism apparently cannot force reliable counter machine computations directly, the presence of a unique diagonal in the models makes it possible to encode both lossy and insertion-error computations, for the same sequence of instructions. We show that, given such a pair of faulty computations, it is then possible to reconstruct a reliable run from them.
Keywords Two-variable first-order logic  Equality  Products of modal logics  Minsky machines  Lossy and insertion-error computations
Categories (categorize this paper)
DOI 10.1007/s11225-015-9647-7
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,355
Through your library

References found in this work BETA

Modal Logic.Patrick Blackburn, Maarten de Rijke & Yde Venema - 2001 - Studia Logica 76 (1):142-148.
Two-Dimensional Modal Logic.Krister Segerberg - 1973 - Journal of Philosophical Logic 2 (1):77 - 96.
Products of Modal Logics, Part 1.D. Gabbay & V. Shehtman - 1998 - Logic Journal of the IGPL 6 (1):73-146.
On Languages with Two Variables.Michael Mortimer - 1975 - Mathematical Logic Quarterly 21 (1):135-140.
Hybrid Languages.Patrick Blackburn & Jerry Seligman - 1995 - Journal of Logic, Language and Information 4 (3):251-272.

View all 19 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Decidable and Undecidable Logics with a Binary Modality.ágnes Kurucz, István Németi, Ildikó Sain & András Simon - 1995 - Journal of Logic, Language and Information 4 (3):191-206.
Deciding Regular Grammar Logics with Converse Through First-Order Logic.Stéphane Demri & Hans De Nivelle - 2005 - Journal of Logic, Language and Information 14 (3):289-329.
Products of Modal Logics, Part 1.D. Gabbay & V. Shehtman - 1998 - Logic Journal of the IGPL 6 (1):73-146.
Decidable Fragments of First-Order Modal Logics.Frank Wolter & Michael Zakharyaschev - 2001 - Journal of Symbolic Logic 66 (3):1415-1438.
Failure of Interpolation in Combined Modal Logics.Maarten Marx & Carlos Areces - 1998 - Notre Dame Journal of Formal Logic 39 (2):253-273.
Toward Model-Theoretic Modal Logics.Minghui Ma - 2010 - Frontiers of Philosophy in China 5 (2):294-311.


Added to PP index

Total views
28 ( #410,694 of 2,519,516 )

Recent downloads (6 months)
1 ( #407,153 of 2,519,516 )

How can I increase my downloads?


My notes