Homepage of Martin Otto

Selected Papers List of Publications
Selected Talks Curriculum Vitae
Research: AMT Teaching the end

Professor in Mathematics

Logic and Mathematical Foundations of Computer Science

Logic Group

Mathematics Department (FB 4)
Technische Universität Darmstadt
Schlossgartenstrasse 7
D-64289 Darmstadt

tel: (+49) 06151-1622861 (office)
tel: (+49) 06151-1622863 (secretary's office)
fax: (+49) 06151-1622840
mail: otto [at] mathematik.tu-darmstadt.de

Research Interests:

Current PhD Students:

also among the co-organisers of PhDs in Logic 2016 at TU Darmstadt


For previous years see

2016 (summer term)


Selected Publications and Preprints

See also (fuller) list of publications

In Books:

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

Model Theory of Modal Logic, with V. Goranko.
Final version (May 2006) of chapter (approx. 80 pages) for:
Handbook of Modal Logic, P. Blackburn, J. van Benthem, F. Wolter (eds), Elsevier, 2006.

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.

Bisimulation invariance and finite structures,
Lecture Notes in Logic, Logic Colloquium '02, 2006, pp. 276-298.

The freedoms of (guarded) bisimulation, with Erich Graedel.
In: Johan van Benthem on Logic and Information Dynamics, A. Baltag, S. Smets (eds), Springer 2014, pp. 3-31.

Research Papers:

Finite groupoids, finite coverings and symmetries in finite structures,
preprint, 50 pages, 2015; also see arXiv:1404.4599.

Pebble games and linear equations, with Martin Grohe.
Journal of Symbolic Logic, volume 80(3), 2015, pp. 797-844;
also see arXiv:1204.1990;

Highly acyclic groups, hypergraph covers and the guarded fragment,
revised version 2011, 45 pages. Journal version of LICS 2010 paper, JACM, 2012.
JACM, 59:1, Article No 5, February 2012. Abstract

Decidability results for the boundedness problem, with A. Blumensath and M. Weyer.
Journal version based on results in the ICALP'09 paper, Logical Methods in Computer Science, 10 (3), 2014;
also see arXiv:1406.7684, Abstract

Querying the guarded fragment, with Vince Barany and Georg Gottlob.
Journal version of LICS 2010 paper, Logical Methods in Computer Science,
volume 10 (2), 2014; also see arXiv:1309.5822; Abstract

Expressive completeness through logically tractable models,
Annals of Pure and Applied Logic 164, pp. 1418-1453, 2013. Abstract

Queries with guarded negation, with Vince Barany and Balder ten Cate.
Preprint, 19 pages; also see arXiv:1203.0077;
also (without appendix) as VLDB 2012 paper (PVLDB 5(11):1328-1339, 2012), 12 pages.

Modal characterisation theorems over special classes of frames, with A. Dawar.
Extended journal version LICS 2005 paper, Annals of Pure and Applied Logic, volume 161, 2009, pp. 1-42. Abstract

Small substructures and decidability issues for first-order logic with two variables , with E. Kieronski.
Journal of Symbolic Logic, volume 77(3), 2012, pp. 729-765. Journal version of LICS'05 paper. Abstract

Modal and guarded characterisation theorems over finite transition systems,
Annals of Pure and Applied Logic, volume 130, 2004, pp. 173-205. Abstract

Finite conformal hypergraph covers and Gaifman cliques in finite structures, with I. Hodkinson.
Bulletin of Symbolic Logic, volume 9, 2003, pp. 387-405. Abstract

Back and forth between guarded and modal logics, with E. Grädel and C. Hirsch.
ACM Transactions on Computational Logic, volume 3, 2002, pp. 418-463. Abstract

Two Variable First-Order Logic over Ordered Domains.
Journal of Symbolic Logic, volume 66, 2001, pp. 685-702. Abstract

Epsilon-Logic is More Expressive Than First-Order Logic over Finite Structures.
Journal of Symbolic Logic, volume 65, 2000, pp. 1749-1757. Abstract

An Interpolation Theorem.
Bulletin of Symbolic Logic, volume 6, 2000, pp. 447-462. Abstract

On Logics with Two Variables, with E. Grädel.
Theoretical Computer Science, 224, 1999, pp. 73-113. Abstract

Bisimulation-Invariant Ptime and Higher-Dimensional mu-Calculus.
Theoretical Computer Science, 224, 1999, pp. 237-266. Abstract

Undecidability Results on Two-Variable Logics, with E. Grädel and E. Rosen.
Archive for Mathematical Logic, 38, 1999, pp. 313-345. Abstract

Beth Definability for the Guarded Fragment, with E. Hoogland and M. Marx.
LPAR'99, LNAI, vol. 1705, Springer 1999, pp. 273-285. Abstract
Also in: JFAK, Essays Dedicated to Johan van Benthem on the Occasion of his 50th Birthday.

Eliminating Recursion in the mu-Calculus.
in Proceedings of STACS'99, LNCS 1563, Springer 1999, pp. 531-540. Abstract

On the Boundedness Problem for Two-Variable First-Order Logic, with P. Kolaitis.
LICS'98. Abstract

Elementary proof of the van Benthem - Rosen characterisation theorem,
technical report, TUD online preprint no.2342, 2004, 11 pages. Abstract

Symmetry and First-Order: Explicitly Presentation-Invariant Circuits.
Unpublished extended version of CSL 96 paper, 1994, 32 pages. Abstract

Selected Talks

Invited Talks (Conferences):

Finite Global Realisations of Local Overlap Specifications
Special Session on Computational Logic, DMV-PTM meeting, Poznan 2014.

Bisimulation and Coverings for Graphs and Hypergraphs
5th Indian Conference on Logic and Its Applications, ICLA 2013, Chennai 2013.

The Freedoms of Guarded Bisimulation
Computer Science Logic , Bergen 2011.

Tractable Finite Models
Logic Colloquium, Barcelona 2011.

Expressive Completeness
Advances in Modal Logic 2010, Moscow 2010.

Bisimulation Invariance and Instances of Expressive Completeness
12th International Congress of Logic, Methodology and Philosophy of Science, LMPS, Oviedo 2003.

Invariances, Games, Models, and (Finite) Model Theory in Tractable Fragments of FO
Colloquium Logicum, Muenster 2002.

Tutorials and Survey Talks:

Bisimulation and Games for Graphs and Hypergraphs
Tutorial at Games Winter School, Champery 2013.

Finite model constructions for guarded logics
Finite and Algorithmic Model Theory 2012, Les Houches 2012.

Games and Fragments of FO over Special Classes of (Finite) Structures
mini-course at MATHLOGAPS summer school, Aussois 2007.

Model Theoretic Methods for Special Classes of (Finite) Structures
4 lecture tutorial, Newton Institute Programme on Logic and Algorithms 2006,
Workshop on Finite and Algorithmic Model Theory , Durham 2006.

Logics - Invariances - Games : domain specific algorithmic model theory
Edinburgh 2001.

Seminar/Workshop Talks:

Amalgamation and local-to-finite in the finite with suitable groupoids
New Pathways between Group Theory and Model Theory, Mülheim 2016.

Up to bisimulation -- but keep it finite!
Amsterdam 2015.

Local to Global: Amalgamation and Symmetries in Finite Structures
Leeds Logic Seminar & Algebra, Logic and Algorithms Seminar, Leeds 2015.

Groupoids, Hypergraphs, Symmetries
AlMoTh~2013, TU Berlin 2013.

Tree unfoldings and their finite counterparts
AlMoTh 2012, Ilmenau 2012.

Methods For Deciding Boundedness of Least Fixed Points
Fachgruppentreffen Logik in der Informatik, Frankfurt 2009;
and (edited) Computer Laboratory, Oxford 2009.

Bisimulation Invariance over Transitive Frames
IMCS workshop on Logic and Algorithms, Edinburgh, July 2008.

Extensions of Partial Automorphisms; Hypergraphs and Guarded Logics
Euresco Conference on Symmetries, Ordered Structures, Model Theory and Combinatorics, Hattingen 2003.

Conference Talks:

Groupoids, Hypergraphs, and Symmetries of Finite Structures
LICS~2013, New Orleans 2013.

Highly Acyclic Groups, Hypergraph Covers and GF
LICS 2010, Edinburgh 2010.

Boundedness in Universal First-Order Logic
LICS 2006, Seattle 2006.

General Interest Talks:

Unendlich? infinite?
Fachvortrag zur Hobit 2015, TU Darmstadt 2015.

Controlling Cycles in Finite Hypergraphs
Monday Lecture: Methods for Discrete Structures, Berlin 2011.

Diagonalen, die den Rahmen sprengen
Begleitprogramm zur hessischen Mathe-Olympiade 2010, TU Darmstadt 2010.

Logik und Spiele
Mathematisches Kolloquium TU Darmstadt, February 2004 (in German).

photograph at the top by L. Otto (2013)
photograph below by H. Otto (2009)

January 2016, Martin Otto