Robin Hirsch's articles on Complexity and Expressive Power

• R. Hirsch. Intractability in the Allen and Koomen planner.
  In Computational Intelligence , vol. 11, no. 4, pp 553-564, November 1995.
• R. Hirsch. Expressive power and complexity in algebraic logic.
  In the Journal of Logic and Computation , volume 7, number 3, pages 309 - 351, OUP, June 1997.
• R. Hirsch. From points to intervals
  In the Journal of Applied Non-Classical Logic , volume 4 number 1, pp 7 - 27, 1994. (The postscript version here has diagrams missing)
• R. Hirsch. Relation algebras of intervals
  In Artificial Intelligence Journal, vol. 83, pp 1-29, 1996. Diagrams are missing.
• R. Hirsch and I. Hodkinson. Representability is not decidable for finite relation algebras.
  In the Transactions of the American Mathematical Society (vol. 353 number 4, 2001, pages 1387-1401).  Reduces the tiling problem to the representation problem for finite relation algebras.
• R. Hirsch. Tractable approximations for temporal constraint handling
  In Artificial Intelligence Journal, vol. 116, pp 287-295, 2000.
• R.Hirsch. A finite relation algebra with undecidable network satisfaction problem
  In the Bulletin of the Interest Group in Pure and Applied Logics volume 7, number 4, pages 547-554, 1999.
• M. Cristiani and R. Hirsch. The complexity of the constraint satisfaction problem for small relation algebras
  PDF version.  In Artificial Intelligence Journal , volume 156, pages 177-196, 2004.
• R.Hirsch and N. Gkorogiannis, Complexity of Argumentation.   A draft manuscript proving that the Warranted Argument Problem for propositional logic is PSPACE-complete, 2008