Abstract
In the propositional modal (and algebraic) treatment of two-variable first-order logic equality is modelled by a ‘diagonal’ constant, interpreted in square products of universal frames as the identity (also known as the ‘diagonal’) 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alur R., Henzinger T.: A really temporal logic. Journal of ACM 41, 181–204 (1994)
Berger, R., The undecidability of the domino problem. Memoirs of the AMS 66, 1966.
Blackburn P., de Rijke M., Venema Y.: Modal Logic. Cambridge University Press, Cambridge (2001)
Blackburn P., Seligman J.: Hybrid languages. Journal of Logic, Language and Information 4, 251–272 (1995)
Chagrov, A., Zakharyaschev, M., Modal Logic, vol. 35 of Oxford Logic Guides, Clarendon Press, Oxford, 1997.
Fine K.: Logics containing K4, part II. Journal of Symbolic Logic 50, 619–651 (1985)
Gabbay, D., Kurucz A., Wolter F., and Zakharyaschev M., Many-Dimensional Modal Logics: Theory and Applications, vol. 148, Studies in Logic and the Foundations of Mathematics, Elsevier, Amsterdam, 2003.
Gabbay D., Shehtman V.: Products of modal logics. Part I. Logic Journal of the IGPL 6, 73–146 (1998)
Gabbay D., Shehtman V.: Products of modal logics. Part II. Logic Journal of the IGPL 2, 165–210 (2000)
Gabelaia D., Kurucz A., Wolter F., Zakharyaschev M.: Products of ‘transitive’ modal logics. Journal of Symbolic Logic 70, 993–1021 (2005)
Gödel K.: Zum Entscheidungsproblem des logischen Funktionenkalküls. Monatshefte fur Mathematik und Physik 40, 433–443 (1933)
Goldfarb W.: The unsolvability of the Gödel class with identity. Journal Symbolic Logic 49, 1237–1252 (1984)
Göller, S., J. C. Jung, and M. Lohrey, The complexity of decomposing modal and first-order theories, in IEEE Proceedings of the LICS 2012, 2012, pp. 325–334.
Grädel E., Kolaitis P., Vardi M.: On the decision problem for two-variable first order logic. Bulletin of Symbolic Logic 3, 53–69 (1997)
Gutiérrez-Basulto, V., J. C. Jung, and T. Schneider, Lightweight description logics and branching time: A troublesome marriage, in Proceedings of the KR 2014, AAAI Press, Cambridge, 2014.
Halmos P.: Algebraic Logic. Chelsea Publishing Company, New York (1962)
Hampson C., Kurucz A.: Undecidable propositional bimodal logics and one-variable first-order linear temporal logics with counting. ACM Transactions on Computational Logic 16(3), 27:1–27:36 (2015)
Henkin H., Monk J. D., Tarski A.: Cylindric Algebras, Part II. North Holland, (1985)
Kikot S.: Axiomatization of modal logic squares with distinguished diagonal. Mathematical Notes 88, 238–250 (2010)
Kuhn S. T.: Quantifiers as modal operators. Studia Logica 39, 145–158 (1980)
Kurucz, A., Combining modal logics, in P. Blackburn, J. van Benthem, and F.Wolter (eds.), Handbook of Modal Logic, vol. 3 of Studies in Logic and Practical Reasoning, Elsevier, Amsterdam, 2007, pp. 869–924.
Kurucz A., Products of modal logics with diagonal constant lacking the finite model property, in S. Ghilardi, and R. Sebastiani, (eds.), Procs. FroCoS-2009, vol. 5749 of LNCS, Springer, New York, 2009, pp. 279–286.
Kurucz, A., Representable cylindric algebras and many-dimensional modal logics, in H. Andréka, M. Ferenczi, and I. Németi (eds.), Cylindric-like Algebras and Algebraic Logic, vol. 22 of Bolyai Society Mathematical Studies, Springer, 2013, pp. 185–203.
Marx M.: Complexity of products of modal logics. Journal of Logic and Computation 9, 197–214 (1999)
Marx M., Reynolds M.: Undecidability of compass logic. Journal of Logic and Computation 9, 897–914 (1999)
Mayr, R., Undecidable problems in unreliable computations, in G. H. Gonnet, D. Panario, and A. Viola (eds.), Proceedings of the LATIN-2000, vol. 1776 of LNCS, Springer, New York, 2000, pp. 377–386.
Minsky M.: Finite and infinite machines. Prentice-Hall, Upper Saddle River (1967)
Mortimer M.: languages with two variables. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 21, 135–140 (1975)
knine, J., and J. Worrell, On metric temporal logic and faulty Turing machines, in L. Aceto, and A. Ingólfsdóttir (eds.), Procs. FOSSACS-2006, vol. 3921 of LNCS, Springer, New York, 2006, pp. 217–230.
Quine, W. V., Algebraic logic and predicate functors, in R. Rudner, and I. Scheffer (eds.), Logic and Art: Essays in Honor of Nelson Goodman, Bobbs-Merrill, 1971. Reprinted with amendments in The Ways of Paradox and Other Essays, 2nd edition, Harvard University Press, Cambridge, Massachussetts, 1976.
Reynolds M.: decidable temporal logic of parallelism. Notre Dame Journal of Formal Logic 38, 419–436 (1997)
Reynolds M., Zakharyaschev M.: On the products of linear modal logics. Journal of Logic and Computation 11, 909–931 (2001)
Schmidt, R., and D. Tishkovsky, Combining dynamic logic with doxastic modal logics, in P. Balbiani, N.-Y. Suzuki, F.Wolter, and M. Zakharyaschev (eds.), Advances in Modal Logic, vol. 4, King’s College Publications, London, 2003, pp. 371–391.
Scott D.: A decision method for validity of sentences in two variables. Journal of Symbolic Logic 27, 477 (1962)
Segerberg K.: Modal logics with linear alternative relations. Theoria 36, 301–322 (1970)
Segerberg K.: Two-dimensional modal logic. Journal of Philosophical Logic 2, 77–96 (1973)
Shehtman V.: Two-dimensional modal logics. Mathematical Notices of the USSR Academy of Sciences 23, 417–424 (1978) (Translated from Russian)
Shehtman V.: On squares of modal logics with additional connectives. Proceedings of the Steklov Institute of Mathematics 274, 317–325 (2011)
Spaan, E., Complexity of Modal Logics, Ph.D. thesis, Universiteit van Amsterdam, 1993.
Tobies S., Complexity results and practical algorithms for logics in knowledge representation, Ph.D. thesis, Aachen, Technische Hochschule, 2001.
Venema, Y., Many-Dimensional Modal Logics, Ph.D. thesis, Universiteit van Amsterdam, 1991.
Wajsberg M.: Ein erweiterter Klassenkalkül. Monatsh Mathematical Physics 40, 113–126 (1933)
Wolter F.: The product of converse PDL and polymodal K. Journal of Logic and Computation 10, 223–251 (2000)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0), which permits use, duplication, adaptation, distribution, and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Hampson, C., Kikot, S. & Kurucz, A. The Decision Problem of Modal Product Logics with a Diagonal, and Faulty Counter Machines. Stud Logica 104, 455–486 (2016). https://doi.org/10.1007/s11225-015-9647-7
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11225-015-9647-7