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.
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.
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.
Vince Bárány, Balder ten Cate & Luc Segoufin (2015):
Guarded Negation.
J. ACM 62(3),
pp. 22,
doi:10.1145/2701414.
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.
Patrick Blackburn, Johan van Benthem & Frank Wolter (2006):
Handbook of Modal Logic.
Elsevier Science Inc.,
New York.
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.
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.
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.
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.
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.
Erich Grädel (1999):
On The Restraining Power of Guards.
J. Symb. Log. 64(4),
pp. 1719–1742,
doi:10.2307/2586808.
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.
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.
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.
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.
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.
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.
Y. Kazakov (2006):
Saturation-based decision procedures for extensions of the guarded fragment.
Universität des Saarlandes,
Saarbrücken, Germany.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Martin Otto (2001):
Two Variable First-Order Logic over Ordered Domains.
J. Symb. Log. 66(2),
pp. 685–702,
doi:10.2307/2695037.
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.
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.
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.
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.
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.
William C. Purdy (1996):
Fluted Formulas and the Limits of Decidability.
J. Symb. Log. 61(2),
pp. 608–620,
doi:10.2307/2275678.
William C. Purdy (1999):
Quine's 'Limits of Decision'.
J. Symb. Log. 64(4),
pp. 1439–1466,
doi:10.2307/2586789.
William C. Purdy (2002):
Complexity and Nicety of Fluted Logic.
Studia Logica 71(2),
pp. 177–198,
doi:10.1023/A:1016596721799.
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.
W. V. Quine (1976):
The variable.
In: The Ways of Paradox,
revised and enlarged edition.
Harvard University Press,
pp. 272–282.
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.
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.
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.
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.
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.
Luc Segoufin & Balder ten Cate (2013):
Unary negation.
Logical Methods in Computer Science 9(3),
doi:10.2168/LMCS-9(3:25)2013.
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.
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.
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.
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.
Boris A. Trakhtenbrot (1953):
On recursive separability.
Doklady Akademii Nauk SSSR 88(6),
pp. 953–956.
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.
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.