Martin Otto: PUBLICATIONS


Monograph

M. Otto, Bounded Variable Logics and Counting - A Study in Finite Models,
Lecture Notes in Logic volume 9, Springer 1997, IX+183 pages.
Abstract BibTeX entry


Contributions to Books and Collections

M. Otto, Model Theoretic Methods For Fragments of FO And Special Classes Of (Finite) Structures,
In: Finite and Algorithmic Model Theory, J. Esparza, C. Michaux, C. Steinhorn (eds),
LMS Lecture Notes Series, vol. 379, Cambridge University Press, 2011, pp. 271-341.

V. Goranko and M. Otto, Model Theory of Modal Logics,
in: Handbook of Modal Logic, edited by P. Blackburn, F. Wolter, and J. van Benthem, Elsevier 2006, pp. 255-325.
BibTeX entry

M. Otto, Bisimulation Invariance and Finite Structures,
in: Lecture Notes in Logic, Logic Colloquium 02, edited by Z. Chatzidakis, P. Koepke, and W. Pohlers, ASL 2006, pp. 276-298. Abstract BibTeX entry

E. Hoogland, M. Marx, and M. Otto, Beth Definability for the Guarded Fragment,
in: JFAK. Essays Dedicated to Johan van Benthem on the Occasion of his 50th Birthday, edited by J. Gebrandy, M. Marx, M. de Rijke and Y. Venema, CD-ROM, Amsterdam University Press 1999. Abstract



Publications in Journals and Volumes of Selected Papers

[J 22]
Highly acyclic groups, hypergraph covers and the guarded fragment,
Journal version of LICS 2010 paper, JACM, 2012.
JACM, 59:1, Article No 5, February 2012. Abstract
BibTeX entry

[J 21]
A. Dawar and M. Otto, Modal Characterisation Theorems over Special Classes of Frames,
Annals of Pure and Applied Logic, volume 161, 2009, pp.~1-42. Abstract
BibTeX entry

[J 20]
M. Otto, Modal and Guarded Characterisation Theorems over Finite Transition Systems,
Annals of Pure and Applied Logic, volume 130, 2004, pp.~173-205. Abstract
BibTeX entry

[J 19]
I. Hodkinson and M. Otto, Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures,
Bulletin of Symbolic Logic, volume 9, 2003, pp. 387-405.
Abstract BibTeX entry

[J 18]
E. Grädel, C. Hirsch and M. Otto, Back and Forth Between Guarded and Modal Logics,
ACM Transactions on Computational Logic, volume 3, 2002, pp. 418-463.
Abstract BibTeX entry

[J 17]
M. Otto, An interpolation theorem,
Bulletin of Symbolic Logic, volume 6, 2000, pp. 447-462.
Abstract BibTeX entry

[J 16]
M. Otto, Two-Variable First-Order Logic over Ordered Domains,
Journal of Symbolic Logic, volume 66, 2001, pp. 685-702.
Abstract BibTeX entry

[J 15]
M. Otto, Epsilon-Logic is More Expressive Than First-Order Logic over Finite Structures,
Journal of Symbolic Logic, volume 65, 2000, pp. 1749-1757.
Abstract BibTeX entry

[J 14]
F. Neven, M. Otto, J. Tyszkiewicz, and J. Van den Bussche, Adding FOR-Loops to First-Order Logic, Information and Computation, volume 168, 2001, pp. 156-186.
Abstract BibTeX entry

[J 13]
M. Otto, Bounded-Variable Logics: Two, Three, and More,
Archive for Mathematical Logic, volume 38, 1999, pp. 235-256.
Abstract BibTeX entry

[J 12]
M. Otto, Bisimulation-Invariant Ptime and Higher-Dimensional mu-Calculus,
Theoretical Computer Science, volume 224, 1999, pp. 237-265.
Abstract BibTeX entry

[J 11]
E. Grädel, M. Otto, and E. Rosen, Undecidability Results on Two-Variable Logics, Archive of Mathematical Logic, volume 38, 1999, pp. 313-354.
Abstract BibTeX entry

[J 10]
E. Grädel and M. Otto, On logics with two variables,
Theoretical Computer Science, volume 224, 1999, pp. 73-113.
Abstract BibTeX entry

[J 9]
M. Otto, The Logic of Explicitly Representation-Invariant Circuits, Selected Papers of CSL `96, D. van Dalen and M. Bezem (ed.), Lecture Notes in Computer Science, volume 1258, Springer 1997, pp. 369-384.
BibTeX entry, for abstract see extended version

[J 8]
M. Otto, Canonization for Two Variables and Puzzles on the Square, Annals of Pure and Applied Logic, volume 85, 1997, pp. 243-282.
Abstract BibTeX entry

[J 7]
M. Otto and J. Van den Bussche, First-Order Queries on Databases Embedded in an Infinite Structure, Information Processing Letters, volume 60, 1996, pp. 37-41.
Abstract BibTeX entry

[J 6]
M. Otto, The Expressive Power of Fixed-Point Logic with Counting, Journal of Symbolic Logic, volume 61, 1996, pp. 147-176.
Abstract BibTeX entry

[J 5]
M. Otto, A Note on the Number of Monadic Quantifiers in Monadic Sigma_1^1, Information Processing Letters, volume 53, 1995, pp. 337-339.
Abstract BibTeX entry

[J 4]
E. Grädel and M. Otto, Inductive Definability with Counting on Finite Structures, Selected Papers, 6th Workshop on Computer Science Logic CSL `92, San Miniato 1992, Lecture Notes in Computer Science No. 702, Springer 1993, pp. 231-247.
Abstract BibTeX entry

[J 3]
M. Otto, EM Functors for a Class of Generalized Quantifiers,
Archive for Mathematical Logic volume 31, 1992, pp. 355-371. BibTeX entry

[J 2]
M. Otto, Automorphism Properties of Stationary Logic,
Journal of Symbolic Logic volume 57, 1992, pp. 231-237. BibTeX entry

[J 1]
M. Otto, A Reduction Scheme for Phase Spaces with Almost-Kähler Symmetry -- Regularity Results for Momentum Level Sets,
Journal of Geometry and Physics volume 4, 1987, pp. 101-118. BibTeX entry



Proceedings of Refereed Conferences

[P 17]
M. Otto. Highly Acyclic Groups, Hypergraph Covers and the Guarded Fragment, Proceedings of Logic in Computer Science, LICS 2010
Abstract BibTeX entry

[P 17]
V. Barany, G. Gottlob and M. Otto. Querying the Guarded Fragment, Proceedings of Logic in Computer Science, LICS 2010
Abstract BibTeX entry

[P 17]
A. Blumensath, M. Otto and M. Weyer. Boundedness of Monadic Second-Order Logic over Finite Words, Proceedings of 36th International Colloquium on Automata, Languages and Programming ICALP 2009, LNCS 5556, pp 67-78.
Abstract BibTeX entry

[P 16]
R. Piro and M. Otto. A Lindström Characterisation of the Guarded Fragment and of Modal Logic With a Global Modality, Advances in Model Logic 7, AiML 2008, C. Areces and R. Goldblatt (eds), pp pp. 273-288.
Abstract BibTeX entry

[P 15]
S. Kreutzer, M. Otto and N. Schweikardt. Boundedness of Monadic FO over Acyclic Structures, Proceedings of 34th International Colloquium on Automata, Languages and Programming ICALP 2007, LNCS 4596, pp 571-582.
Abstract BibTeX entry

[P 14]
M. Otto, The Boundedness Problem for Monadic Universal First-Order Logic, Proceedings of 21st IEEE Symposium on Logic in Computer Science LICS 2006, pp 37-46.
Abstract BibTeX entry

[P 13]
A. Dawar and M. Otto, Modal Characterisation Theorems over Special Classes of Frames, Proceedings of 20th IEEE Symposium on Logic in Computer Science LICS 2005, pp 21-30.
Abstract BibTeX entry

[P 12]
E. Kieronski and M. Otto, Small Substructures and Decidability Issues for Two-Variable First-Order Logic, Proceedings of 20th IEEE Symposium on Logic in Computer Science LICS 2005, pp 448-457.
Abstract BibTeX entry

[P 11]
M. Otto, Modal and Guarded Characterisation Theorems over Finite Transition Systems, Proceedings of 17th IEEE Symposium on Logic in Computer Science LICS 2002, pp 371-380.
Also see full version with Abstract BibTeX entry

[P 10]
E. Grädel and C. Hirsch and M. Otto, Back and Forth Between Guarded and Modal Logics, Proceedings of 15th IEEE Symposium on Logic in Computer Science LICS 2000, Santa Barbara, pp. 217-228. Abstract BibTeX entry
Also see journal version

[P 9]
M. Otto, Eliminating Recursion in the mu-Calculus, Proceedings of STACS'99, Lecture Notes in Computer Science No. 1563, Springer 1999, pp. 531-540.
Abstract BibTeX entry

[P 8]
F. Neven, M. Otto, J. Tyszkiewicz, and J. Van den Bussche, Adding FOR-Loops to First-Order Logic, Proceedings of ICDT'99, Lecture Notes in Computer Science No. 1540, Springer 1999, pp. 58-69.
Abstract BibTeX entry Journal version

[P 7]
E. Hoogland, M. Marx, and M. Otto, Beth Definability for the Guarded Fragment, Proceedings of LPAR'99, LNAI, vol. 1705, Springer 1999, pp. 273-285.
Abstract BibTeX entry See also in: JFAK

[P 6]
P. Kolaitis and M. Otto, On the Boundedness Problem for Two-Variable First-Order Logic, Proceedings of 13th IEEE Symposium on Logic in Computer Science LICS `98, 1998, pp. 513-524.
Abstract BibTeX entry

[P 5]
M. Otto, Capturing Bisimulation-Invariant Ptime, Proceedings of 4th Symposium on Logical Foundations of Computer Science, LFCS `97, Lecture Notes in Computer Science No. 1234, Springer 1997, 294-305.
BibTeX entry Journal version


[P 4]
E. Grädel, M. Otto, and E. Rosen, Two-Variable Logic with Counting is Decidable, Proceedings of 12th IEEE Symposium on Logic in Computer Science LICS `97, Warsaw, pp. 306-317.
Abstract BibTeX entry

[P 3]
E. Grädel, M. Otto, and E. Rosen, Undecidability Results on Two-Variable Logics, Proceedings of 14th Symposium on Theoretical Aspects of Computer Science STACS `97 Lecture Notes in Computer Science No. 1200, Springer 1997, pp. 249-260.
Abstract BibTeX entry Journal version

[P 2]
M. Otto, Ptime Canonization for Two Variables with Counting, Proceedings of 10th IEEE Symposium on Logic in Computer Science LICS `95, San Diego, pp. 342-352.
Abstract BibTeX entry Journal version

[P 1]
M. Otto, Generalized Quantifiers for Simple Properties, Proceedings of 9th IEEE Symposium on Logic in Computer Science LICS `94, Paris, pp. 30-39.
Abstract BibTeX entry



Miscellaneous

M. Otto, Elementary Proof of the van Benthem - Rosen Characterisation Theorem , revised 2004, TUD online preprint no.2342 , May 2004, 11 pages. Abstract BibTeX entry

M. Otto , Ehrenfeucht-Mostowski Konstruktionen in Erweiterungslogiken, Doctoral dissertation (German), Freiburg University, 1990, 94 pages.
BibTeX entry

M. Otto, Bounded Variable Logics and Counting - A Study in Finite Models, Habilitationsschrift (English), RWTH Aachen, 1995, 190 pages.
Abstract BibTeX entry Monograph

M. Otto, Symmetry and First-Order: Explicitly Representation-Invariant Circuits, (32 pages), unpublished, 1994.
Abstract BibTeX entry Journal version



Back to my homepage

January 2004, M. Otto