Publications

2002

• E. Grädel, C. Hirsch, and M. Otto. Back and Forth Between Guarded and Modal Logics. ACM Transactions on Computational Logics, vol. 3(3), pp. 418 – 463, 2002.                                 
  Abstract   BibTeX

  Guarded fixed-point logic $\mu$GF extends the guarded fragment by means of least and greatest fixed points, and thus plays the same role within the domain of guarded logics as the modal $\mu$-calculus plays within the modal domain. We provide a semantic characterization of $\mu$GF within an appropriate fragment of second-order logic, in terms of invariance under guarded bisimulation. The corresponding characterization of the modal $\mu$-calculus, due to Janin and Walukiewicz, is lifted from the modal to the guarded domain by means of model theoretic translations. Guarded second-order logic, the fragment of second-order logic which is introduced in the context of our characterization theorem, captures a natural and robust level of expressiveness with several equivalent characterizations. For a wide range of issues in guarded logics it may take up a role similar to that of monadic second-order in relation to modal logics. At the more general methodological level, the translations between the guarded and modal domains make the intuitive analogy between guarded and modal logics available as a tool in the further analysis of the model theory of guarded logics.

  @article{GrHiOt00a,
       author = {Erich Gr{\"a}del and Colin Hirsch and Martin Otto},
       journal = {ACM Transactions on Computational Logics},
       note = {See also: conference version \cite{GrHiOt00}},
       number = {3},
       pages = {418 -- 463},
       title = {{Back and Forth Between Guarded and Modal Logics}},
       url = {http://www.logic.rwth-aachen.de/pub/graedel/GrHiOt-tocl02.ps},
       volume = {3},
       year = {2002},
  }
  

• C. Hirsch. Guarded Logics: Algorithms and Bisimulation. PhD thesis, RWTH Aachen, 2002.             
  BibTeX

  @phdthesis{HirschThesis,
       author = {Colin Hirsch},
       school = {RWTH Aachen},
       title = {{Guarded Logics: Algorithms and Bisimulation}},
       url = {http://www.logic.rwth-aachen.de/pub/hirsch/hirsch.pdf},
       year = {2002},
  }
  

2001

• C. Hirsch and R. Fleischer. Graph Drawings and Its Applications. In Drawing Graphs – Methods and Models (M. Kaufmann and D. Wagner, Eds.), LNCS, pp. 1–22. Springer, 2001.             
  BibTeX

  @incollection{HiFl01,
       author = {Colin Hirsch and R. Fleischer},
       booktitle = {{Drawing Graphs -- Methods and Models}},
       chapter = {1},
       editor = {M. Kaufmann and D. Wagner},
       pages = {1--22},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{Graph Drawings and Its Applications}},
       year = {2001},
  }
  

2000

• E. Grädel, C. Hirsch, and M. Otto. Back and Forth Between Guarded and Modal Logics. In Proceedings of 15th IEEE Symposium on Logic in Computer Science LICS 2000, pp. 217–228, Santa Barbara, 2000.                                 
  Abstract   BibTeX

  We propose a second-order extension for the guarded fragment showing that several canonical extensions are in fact equivalent. Then we ask the question in how far results from the modal world can be brought into the world of guarded logics. We give a transformation from first-order structures to Kripke type transition systems. This is used here to transform a theorem due to Janin and Walukiewicz about the expressive completeness of fixed-point logic in the context of bisimulation invariance.

  @inproceedings{GrHiOt00,
       address = {Santa Barbara},
       author = {Erich Gr{\"a}del and Colin Hirsch and Martin Otto},
       booktitle = {{Proceedings of 15th IEEE Symposium on Logic in Computer Science LICS 2000}},
       note = {See also: journal version \cite{GrHiOt00a}},
       pages = {217--228},
       title = {{Back and Forth Between Guarded and Modal Logics}},
       url = {http://www.logic.rwth-aachen.de/pub/graedel/GrHiOt-lics00.ps},
       year = {2000},
  }
  

• C. Hirsch and S. Tobies. A Tableau Algorithm for the Clique Guarded Fragment. In Proceedings of the Workshop Advances in Modal Logic AiML 2000, Leipzig, Germany, 2000.             
  BibTeX

  @inproceedings{HT00,
       address = {Leipzig, Germany},
       author = {Colin Hirsch and S.~Tobies},
       booktitle = {{Proceedings of the Workshop Advances in Modal Logic {AiML 2000}}},
       title = {{A Tableau Algorithm for the Clique Guarded Fragment}},
       url = {http://www.logic.rwth-aachen.de/pub/hirsch/hito00.ps.gz},
       year = {2000},
  }
  

1998

• E. Grädel, Y. Gurevich, and C. Hirsch. The complexity of query reliability. In 17th ACM Symposium on Principles of Database Systems PODS `98, Seattle. ACM Press, 1998.             
  BibTeX

  @inproceedings{GrGuHi98,
       author = {Erich Gr{\"a}del and Yuri Gurevich and Colin Hirsch},
       booktitle = {{17th ACM Symposium on Principles of Database Systems PODS `98, Seattle}},
       publisher = {ACM Press},
       title = {{The complexity of query reliability}},
       url = {http://www.logic.rwth-aachen.de/pub/graedel/GrGuHi-pods98.ps},
       year = {1998},
  }
  

• C. Hirsch. The Reliability of Database Queries. Diploma thesis, RWTH-Aachen, 1998.             
  BibTeX

  @misc{Hi98,
       author = {Colin Hirsch},
       howpublished = {Diploma thesis, RWTH-Aachen},
       title = {{The Reliability of Database Queries}},
       year = {1998},
  }