References

1. Hajnal Andréka, Johan van Benthem & Istvan Németi (1998): Modal Languages and Bounded Fragments of Predicate Logic. Journal of Philosophical Logic 27, pp. 217–274, doi:10.1023/A:1004275029985.
2. Hajnal Andréka, Ian M. Hodkinson & István Németi (1999): Finite Algebras of Relations Are Representable on Finite Sets. J. Symb. Log. 64(1), pp. 243–267, doi:10.2307/2586762.
3. Vince Bárány & Mikołaj Bojańczyk (2012): Finite satisfiability for guarded fixpoint logic. Inf. Process. Lett. 112(10), pp. 371–375, doi:10.1016/j.ipl.2012.02.005.
4. Vince Bárány, Balder ten Cate & Luc Segoufin (2015): Guarded Negation. J. ACM 62(3), pp. 22, doi:10.1145/2701414.
5. Vince Bárány, Georg Gottlob & Martin Otto (2014): Querying the Guarded Fragment. Logical Methods in Computer Science 10(2), doi:10.2168/LMCS-10(2:3)2014.
6. Patrick Blackburn, Johan van Benthem & Frank Wolter (2006): Handbook of Modal Logic. Elsevier Science Inc., New York.
7. Mikołaj Bojańczyk, Claire David, Anca Muscholl, Thomas Schwentick & Luc Segoufin (2011): Two-variable logic on data words. ACM Trans. Comput. Log. 12(4), pp. 27, doi:10.1145/1970398.1970403.
8. Witold Charatonik & Piotr Witkowski (2015): Two-variable Logic with Counting and a Linear Order. In: Computer Science Logic, LIPIcs 41. SchloßDagsuhl - Leibniz-Zentrum für Informatik, pp. 631–647, doi:10.4230/LIPIcs.CSL.2015.631.
9. Michael J. Fischer & Richard E. Ladner (1979): Propositional Dynamic Logic of Regular Programs. J. Comput. Syst. Sci. 18(2), pp. 194–211, doi:10.1016/0022-0000(79)90046-1.
10. Dov M Gabbay (1981): An irreflexivity lemma with applications to axiomatizations of conditions on tense frames. In: Aspects of philosophical logic. Springer, pp. 67–89, doi:10.1007/978-94-009-8384-7_3.
11. Harald Ganzinger, Christoph Meyer & Margus Veanes (1999): The Two-Variable Guarded Fragment with Transitive Relations. In: 14th Annual IEEE Symposium on Logic in Computer Science, Trento, Italy, July 2-5, 1999, pp. 24–34, doi:10.1109/LICS.1999.782582.
12. Erich Grädel (1999): On The Restraining Power of Guards. J. Symb. Log. 64(4), pp. 1719–1742, doi:10.2307/2586808.
13. Erich Grädel, Phokion Kolaitis & Moshe Vardi (1997): On the decision problem for two-variable first-order logic. Bulletin of Symbolic Logic 3(1), pp. 53–69, doi:10.2307/421196.
14. Erich Grädel, Martin Otto & Eric Rosen (1997): Two-Variable Logic with Counting is Decidable. In: Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland, June 29 - July 2, 1997, pp. 306–317, doi:10.1109/LICS.1997.614957.
15. Erich Grädel, Martin Otto & Eric Rosen (1999): Undecidability results on two-variable logics. Arch. Math. Log. 38(4-5), pp. 313–354, doi:10.1007/s001530050130.
16. Erich Grädel & Igor Walukiewicz (1999): Guarded Fixed Point Logic. In: 14th Annual IEEE Symposium on Logic in Computer Science, Trento, Italy, July 2-5, 1999, pp. 45–54, doi:10.1109/LICS.1999.782585.
17. Yazmin Angélica Ibáñez-García, Carsten Lutz & Thomas Schneider (2014): Finite Model Reasoning in Horn Description Logics. In: Principles of Knowledge Representation and Reasoning: Proceedings of the 14th International Conference, KR 2014, Vienna, Austria, July 20-24, 2014. Available at http://www.aaai.org/ocs/index.php/KR/KR14/paper/view/7927.
18. A.S. Kahr, E.F. Moore & H. Wang (1962): Entscheidungsproblem reduced to the case. Proc. Nat. Acad. Sci. U.S.A. 48, pp. 365–377, doi:10.1073/pnas.48.3.365.
19. Y. Kazakov (2006): Saturation-based decision procedures for extensions of the guarded fragment. Universität des Saarlandes, Saarbrücken, Germany.
20. Emanuel Kieroński (2003): The Two-Variable Guarded Fragment with Transitive Guards Is 2EXPTIME-Hard. In: Foundations of Software Science and Computational Structures, 6th International Conference, FOSSACS 2003, Warsaw, Poland, April 7-11, 2003, Proceedings, pp. 299–312, doi:10.1007/3-540-36576-1_19.
21. Emanuel Kieroński (2005): Results on the Guarded Fragment with Equivalence or Transitive Relations. In: Computer Science Logic, 19th International Workshop, CSL 2005, 14th Annual Conference of the EACSL, Oxford, UK, August 22-25, 2005, Proceedings, pp. 309–324, doi:10.1007/11538363_22.
22. Emanuel Kieroński (2011): Decidability Issues for Two-Variable Logics with Several Linear Orders. In: Computer Science Logic, 25th International Workshop / 20th Annual Conference of the EACSL, CSL 2011, September 12-15, 2011, Bergen, Norway, Proceedings, pp. 337–351, doi:10.4230/LIPIcs.CSL.2011.337.
23. Emanuel Kieroński, Jakub Michaliszyn, Ian Pratt-Hartmann & Lidia Tendera (2014): Two-variable first-order logic with equivalence closure. SIAM Journal of Computing 43(3), pp. 1012–1063, doi:10.1137/120900095.
24. Emanuel Kieroński & M. Otto (2005): Small Substructures and Decidability Issues for First-Order Logic with Two Variables. In: 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 26-29 June 2005, Chicago, IL, USA, Proceedings, pp. 448–457, doi:10.1109/LICS.2005.49.
25. Emanuel Kieroński, Ian Pratt-Hartmann & Lidia Tendera (2015): Equivalence closure in the two-variable guarded fragment. Journal of Logic and Computation, doi:10.1093/logcom/exv075.
26. Emanuel Kieroński & L. Tendera (2009): On Finite Satisfiability of Two-Variable First-Order Logic with Equivalence Relations. In: Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11-14 August 2009, Los Angeles, CA, USA, pp. 123–132, doi:10.1109/LICS.2009.39.
27. Emanuel Kieroński & Lidia Tendera: Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants. Available at https://arxiv.org/abs/1611.03267. Submitted.
28. Emanuel Kieroński & Lidia Tendera (2007): On Finite Satisfiability of the Guarded Fragment with Equivalence or Transitive Guards. In: Logic for Programming, Artificial Intelligence, and Reasoning, 14th International Conference, LPAR 2007, Yerevan, Armenia, October 15-19, 2007, Proceedings, pp. 318–332, doi:10.1007/978-3-540-75560-9_24.
29. S. Rao Kosaraju (1982): Decidability of Reachability in Vector Addition Systems (Preliminary Version). In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pp. 267–281, doi:10.1145/800070.802201.
30. Carsten Lutz, Ulrike Sattler & Lidia Tendera (2005): The complexity of finite model reasoning in description logics. Inf. Comput. 199(1-2), pp. 132–171, doi:10.1016/j.ic.2004.11.002.
31. Jakub Michaliszyn (2009): Decidability of the Guarded Fragment with the Transitive Closure. In: Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part II, pp. 261–272, doi:10.1007/978-3-642-02930-1_22.
32. Jakub Michaliszyn, Jan Otop & Piotr Witkowski (2012): Satisfiability vs. Finite Satisfiability in Elementary Modal Logics. In: Marco Faella & Aniello Murano: Proceedings Third International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2012, Napoli, Italy, September 6-8, 2012., EPTCS 96, pp. 141–154, doi:10.4204/EPTCS.96.11.
33. M. Mortimer (1975): On languages with two variables. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 21, pp. 135–140, doi:10.1002/malq.19750210118.
34. Martin Otto (2001): Two Variable First-Order Logic over Ordered Domains. J. Symb. Log. 66(2), pp. 685–702, doi:10.2307/2695037.
35. Martin Otto (2004): Modal and guarded characterisation theorems over finite transition systems. Ann. Pure Appl. Logic 130(1-3), pp. 173–205, doi:10.1016/j.apal.2004.04.003.
36. Leszek Pacholski, Wieslaw Szwast & Lidia Tendera (1997): Complexity of Two-Variable Logic with Counting. In: Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland, June 29 - July 2, 1997, pp. 318–327, doi:10.1109/LICS.1997.614958.
37. Ian Pratt-Hartmann (2005): Complexity of the Two-Variable Fragment with Counting Quantifiers. Journal of Logic, Language and Information 14(3), pp. 369–395, doi:10.1007/s10849-005-5791-1.
38. Ian Pratt-Hartmann (2007): Complexity of the Guarded Two-variable Fragment with Counting Quantifiers. J. Log. Comput. 17(1), pp. 133–155, doi:10.1093/logcom/exl034.
39. Ian Pratt-Hartmann, Wieslaw Szwast & Lidia Tendera (2016): Quine's Fluted Fragment is Non-Elementary. In: 25th EACSL Annual Conference on Computer Science Logic, CSL 2016, August 29 - September 1, 2016, Marseille, France, pp. 39:1–39:21, doi:10.4230/LIPIcs.CSL.2016.39.
40. William C. Purdy (1996): Fluted Formulas and the Limits of Decidability. J. Symb. Log. 61(2), pp. 608–620, doi:10.2307/2275678.
41. William C. Purdy (1999): Quine's 'Limits of Decision'. J. Symb. Log. 64(4), pp. 1439–1466, doi:10.2307/2586789.
42. William C. Purdy (2002): Complexity and Nicety of Fluted Logic. Studia Logica 71(2), pp. 177–198, doi:10.1023/A:1016596721799.
43. W. V. Quine (1969): On the limits of decision. In: Proceedings of the 14th International Congress of Philosophy III. University of Vienna, pp. 57–62.
44. W. V. Quine (1976): The variable. In: The Ways of Paradox, revised and enlarged edition. Harvard University Press, pp. 272–282.
45. Michael O. Rabin (1969): Decidability of Second-Order Theories and Automata on Infinite Trees. Transactions of the American Mathematical Society 141, pp. pp. 1–35, doi:10.1090/S0002-9947-1969-0246760-1.
46. Riccardo Rosati (2008): Finite Model Reasoning in DL-Lite. In: Sean Bechhofer, Manfred Hauswirth, Jörg Hoffmann & Manolis Koubarakis: The Semantic Web: Research and Applications, 5th European Semantic Web Conference, ESWC 2008, Tenerife, Canary Islands, Spain, June 1-5, 2008, Proceedings, Lecture Notes in Computer Science 5021. Springer, pp. 215–229, doi:10.1007/978-3-540-68234-9_18.
47. Sebastian Rudolph (2016): The Curse of Finiteness: Undecidability of Database-Inspired Reasoning Problems in Very Expressive Description Logics. In: Maurizio Lenzerini & Rafael Peñaloza: Proceedings of the 29th International Workshop on Description Logics, Cape Town, South Africa, April 22-25, 2016., CEUR Workshop Proceedings 1577. CEUR-WS.org. Available at http://ceur-ws.org/Vol-1577.
48. Sebastian Rudolph & Birte Glimm (2010): Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!. J. Artif. Intell. Res. (JAIR) 39, pp. 429–481, doi:10.1613/jair.3029.
49. Thomas Schwentick & Thomas Zeume (2012): Two-Variable Logic with Two Order Relations. Logical Methods in Computer Science 8(1), doi:10.2168/LMCS-8(1:15)2012.
50. Luc Segoufin & Balder ten Cate (2013): Unary negation. Logical Methods in Computer Science 9(3), doi:10.2168/LMCS-9(3:25)2013.
51. Wiesław Szwast & Lidia Tendera (2001): On the Decision Problem for the Guarded Fragment with Transitivity. In: 16th Annual IEEE Symposium on Logic in Computer Science, Boston, Massachusetts, USA, June 16-19, 2001, Proceedings, pp. 147–156, doi:10.1109/LICS.2001.932491.
52. Wiesław Szwast & Lidia Tendera (2013): \voidb@x FO2 with one transitive relation is decidable. In: 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany, pp. 317–328, doi:10.4230/LIPIcs.STACS.2013.317.
53. Boris A. Trakhtenbrot (1950): Impossibility of an algorithm for the decision problem in finite classes. Doklady Akademii Nauk SSSR 70, pp. 569–572. English translation in Tra63.
54. Boris A. Trakhtenbrot (1950): Impossibility of an algorithm for the decision problem in finite classes. American Mathematical Society Translations 23, pp. 1–6, doi:10.1090/trans2/023/01.
55. Boris A. Trakhtenbrot (1953): On recursive separability. Doklady Akademii Nauk SSSR 88(6), pp. 953–956.
56. A. M. Turing (1937): On computable numbers, with an application to the \voidb@x Entscheidungsproblem. Proc. London Math. Soc. 42, pp. 230–265, doi:10.1112/plms/s2-42.1.230. Correction in vol. 43, pp. 544-546.
57. Moshe Y. Vardi (1996): Why is Modal Logic So Robustly Decidable?. In: Descriptive Complexity and Finite Models, Proceedings of a DIMACS Workshop 1996, Princeton, New Jersey, USA, January 14-17, 1996, pp. 149–184. Available at http://dimacs.rutgers.edu/Volumes/Vol31.html.

Comments and questions to: eptcs@eptcs.org

For website issues: webmaster@eptcs.org