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