Mobile Version

Forthcoming Events

New events will be posted here as soon as details become known.

Here are almost all of my publications. Please email me r.hirsch@ucl.ac.uk if you spot any errors in this listing, or any errors in the papers.

R.Hirsch. An axiomatisation of two dimensional Minkowski spacetime. Arxiv version.
R. Hirsch and B. McLean. EXPTIME-hardness of higher-dimensional Minkowski spacetime. AIML 2022. Arxiv version.
R Hirsch and J Semrl. Lattices and Semilattices in Relational Semigroups with Ordinary
Composition. LICS 2021. Arxiv version.
R Hirsch, I Hodkinson and M Jackson. Undecidability of algebras of binary relations. Chapter in "Hajnal Andréka and István Németi on Unity of Science: From Computing to Relativity Theory Through Algebraic Logic", in the series "Outstanding Contributions to Logic", Springer, 2020. Draft version.
R. Hirsch and B. McLean. The Temporal Logic of Minkowski Spacetime. Chapter in “Alasdair Urquhart on nonclassical and algebraic logic and complexity of proofs”, in the series "Outstanding Contributions to Logic", Springer, 2020. Arxiv version.
R Hirsch and T Stokes. Axioms for signatures with domain and demonic composition. Algebra Universalis 82:24, 2021
R Hirsch, S Mikulas and T Stokes. The algebra of non-deterministic programs: demonic operations, orders and axioms. Arxiv.
R Hirsch and J Semrl. Finite Representability of Semigroups with Demonic Refinement. On Arxiv.
R.Hirsch. Note on Marxism, logic and the rate of profit. On Arxiv.
R Hirsch and R Egrot. First order axiomatisations of representable relation algebras need formulas of arbitrary quantifier depth. Journal of Symbolic Logic, 87(3): 1283--1300, 2022. Preprint on Arxiv.
R Hirsch and R Egrot. Seurat games on Stockmeyer graphs. On Arxiv. Forthcoming, Journal of Graph Theory, 2021.
R. Hirsch and B. McLean. The temporal logic of two dimensional Minkowski spacetime with slower-than-light accessibility is decidable. Advances in Modal Logic 2018.
R. Hirsch. Decidability of Equational Theories for Subsignatures of Relation Algebra. In: Desharnais J., Guttmann W., Joosten S. (eds) Relational and Algebraic Methods in Computer Science. RAMiCS 2018. Lecture Notes in Computer Science, vol 11194. Springer, Cham, 2018.
R. Hirsch and B. McLean. Disjoint-union partial algebras. Logical Methods in Computer Science, 13(2):1-31, 2017. On ArXiv.
R. Hirsch, M. Jackson and T. Kowalski. Algebraic foundations for qualitative calculi and networks, Theoretical Computer Science Journal doi.org/10.1016/j.tcs.2019.02.033 2019. On ArXiv.
R. Hirsch and M. Reynolds. The temporal logic of two dimensional Minkowski spacetime is decidable. Journal of Symbolic Logic, 2018. On ArXiv.
J. Alm, R. Hirsch and R. Maddux. There is no finite-variable equational axiomatization of representable relation algebras over weakly representable relation algebras, Review of Symbolic Logic, 2016. Arxiv version.
R. Egrot and R. Hirsch. Meet-completions and ordered domain algebras. Logic Journal of the IGPL, 23(4):584-600, doi:10.1093/jigpal/jzv018, 2015. Arxiv preprint.
R. Hirsch, M. Jackson and S. Mikulas. The algebra of functions. Arxiv. The algebra of functions with Antidomain and range appears in Journal of Pure and Applied Algebra, 2016.
R. Hirsch and T. Sayed Ahmed. The neat embedding property for algebras other than cylindric algebras and for infinite dimensions. In Journal of Symbolic Logic.Volume 79(1), pp 208-222, 2014. Preprint.
R. Hirsch and L. Dodd. Improved lower bounds on the size of the smallest solution to a graph colouring problem, with an application to relation algebra. JORMICS v. 2, pp 18-26, 2013. Here is a preprint.
R. Hirsch and S. Mikulas. Ordered domain algebras. Journal of Applied Logic, 10.1016/j.jal.2013.04.002/ vol 11(3), pp 253-362, 2013. Preprint.
R Egrot and R Hirsch. Completely Representable Lattices. Algebra Universalis vol. 67, pp 205-217, 2012, DOI 10.1007/s00012-012-0181-4. A preprint.
R Hirsch and I Hodkinson. Completions and Complete Representations. Chapter in "Cylindric-type algebras and algebraic logic", vol. 22 in Bolyai Mathematical Studies Series, Springer, 2013.
R. Hirsch and M. Jackson. Some Undecidable Problems on Representability as Binary Relations. In Journal of Symbolic Logic.Volume 77(4), pp 1211-1244, 2012
R. Hirsch and S. Mikulas. Positive fragments of relevance logic and algebras of binary relations, 2010. Review of Symbolic Logic, volume 4, issue 01, pp. 81-105. Online version available here, (doi:10.1017/S1755020310000249, Cambridge University Press).
R. Hirsch and S. Mikulas. Axiomatizability of Representable Domain Algebras, Journal of Logic and Algebraic Programming, doi 10.1016/j.jlap.2010.07.019, 2011. A preprint.
R Hirsch and E Tzanis. Complexity of logics with bounded modalities, 2009.
R. Hirsch, I. Hodkinson and R. Maddux. Weak representations of relation algebras and relational bases, in Journal of Symbolic Logic, vol. 76(3), 2011. A preprint.
R. Hirsch and I. Hodkinson , Strongly Representable Atom Structures of Cylindric Algebras. vol. 84, number 3, pp 811-828, Journal of Symbolic Logic, 2009.
R.Hirsch and N. Gkorogiannis, The complexity of the warranted formula problem in propositional argumentation. In the Journal of Logic and Computation, OUP, vol.20 (2) pp 481-499, 2009. doi: 10.1093/logcom/exp074
L. Hirsch, R. Hirsch and M. Saeedi Evolving Lucene Search Queries for Text Classification, Proceedings of GECCO 2007.
R. Hirsch and S. Mikulas. Semilattice Ordered Monoids. This is draft copy. The original publication is available at www.springerlink.com vol. 57, pp 333-370, Algebra Universalis, 2007.
R.Hirsch. Relation algebra reducts of cylindric algebras and complete representations. Journal of Symbolic Logic, vol. 72(2), pp 673-703, 2007. Erratum Journal of Symbolic Logic, vol. 78(4), pp 1345-1346, 2013.
R.Hirsch. Peirce Algebras and Boolean Modules . Journal of Logic and Computation, vol. 17, pp 252-283, 2007. A draft version of this paper is available here .
DJ Hulme, R Hirsch, B Buxton and RB Lotto, (2007) . A new reduction from 3SAT to n-partite graphs. IEEE, 2007.
R. Hirsch and I. Hodkinson Games in algebraic logic: axiomatisations and beyond.
Proceedings of "Foundations of the Formal Sciences V: Infinite Games", Bonn November 2004, Bold, Lowe, Rasche, van Bentham (Eds), 2004. To appear in Studies in Logic , Vol. 11, College Publications, 2007.
L. Hirsch, R. Hirsch and M. Saeedi Evolving text classification rules with genetic programming. Applied Artificial Intelligence Journal, vol. 19 no. 7, pp 659-676, 2005.
R.Hirsch. The class of representable ordered monoids has a recursively enumerable, universal axiomatisation but it is not finitely axiomatisable
Logic Journal of the IGPL (OUP), vol. 13 no. 2, pp 159-171, 2005.
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. NB Murray Neuzerling has alerted us to an error in the proof of Lemma 15. Currently the complexity of Gen-SAT for algebra #13 is not known.
R. Hirsch and I. Hodkinson. Relation Algebras by Games. Volume 147 in Studies in Logic and the Foundations of Mathematics series, published by Elsevier Science, North-Holland, 2002. Errata. Status of open problems listed in the book.
R. Hirsch, I. Hodkinson and A Kurucz. Every logic between K³and S5³ is undecidable and non-finitely axiomatisable This is a draft manuscript. A revised version called "On modal logics between K³ and S5³" appears in the Journal of Symbolic Logic, volume 67, number 1, pages 221-234, 2002.
R. Hirsch and I. Hodkinson. Strongly representable atom structures In the Proceedings of the American Mathematical Society , vol. 130, pp 1819-1831, 2002.
R. Hirsch, I. Hodkinson and R. Maddux. On the number of variables required for proofs.
In the Journal of Symbolic Logic , volume 67, number 1, pp 197--213, 2002.
R. Hirsch, I. Hodkinson and R. Maddux. Provability with finitely many variables.
In the Bulletin of Symbolic Logic, volume 8, number 3, pp 348-379, 2002
R. Hirsch and I. Hodkinson. Relation algebras from cylindric algebras, I
In Annals of Pure and Applied Logic , vol. 112, pp 225-266, 2001.
R. Hirsch and I. Hodkinson. Relation algebras from cylindric algebras, II
In Annals of Pure and Applied Logic , vol. 112, pp 267-297, 2001.
R. Hirsch and I. Hodkinson. Synthesising axioms by games.
In JFAK - a CD ROM of essays dedicated to Johan van Benthem on the occasion of his 50th birthday.
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 and I. Hodkinson. Connections between cylindric algebras and relation algebras.
Chapter 14 in Relational Methods in Computer Science Applications, (pages 239-246) which is published in volume 65 of Springer Physica Verlag series Studies in Fuzziness and Soft Computing , 2001.
R. Hirsch and I. Hodkinson. Relation algebras with n-dimensional bases
A revised version appears in the Annals of Pure and Applied Logic ( vol. 101 pp 227-274, 2000, pub. Elsevier) but for copyright reasons this version cannot be posted here.
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.
R. Hirsch, I. Hodkinson, Maarten Marx, Szabolcs Mikulas, and Mark Reynolds. Appendix to `A modal logic of relations' by Venema & Marx. In Logic at work - Essays dedicated to the memory of Helena Rasiowa, Studia Logica library, pages 158-167, Kluwer academic publishers, Dordrecht, 1998.
R. Hirsch and I. Hodkinson. Games in algebraic logic.
Presented at the Amsterdam Colloquium , December 1997, organised by the Institute for Logic, Language and Computation.
R. Hirsch and I. Hodkinson. Axiomatising various classes of relation and cylindric algebras.
In Proc. Workshop on Logic, Language, Information, and Computation , Recife, July 1995. Also appears in Wollic95 Special Issue of the Journal of the Interest Group in Pure and Applied LogicsVol. 5, No. 2, pp 209 - 229, 1997.
R. Hirsch and I. Hodkinson. Step by step - building representations in algebraic logic.
In the Journal of Symbolic Logic , volume 62, number 1, pages 225 - 279, March 1997. Includes game-theoretic characterisation of representations of relation algebras and a first-order characterisation of RRA.
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 and I. Hodkinson. Complete representations in algebraic logic.
In the Journal of Symbolic Logic , volume 62, number 3, pages 816-847, September 1997. Includes proof that the completely representable relation algebras do not form an elementary class, and the same result for cylindric algebras of any fixed dimension.
R. Hirsch. Mathematics - the pure science?
In Science and Society Spring 1996 issue, Vol. 60, No. 1, pp58 -79. I have changed my views on some of this, it is a requirement that if you read this, you also read my note on Marxism, logic and the rate of profit (above).
R. Hirsch. Relation algebras of intervals In Artificial Intelligence Journal, vol. 83, pp 1-29, 1996. Diagrams are missing.
R. Hirsch. Intractability in the Allen and Koomen planner.
In Computational Intelligence , vol. 11, no. 4, pp 553-564, November 1995.
R. Hirsch. Completely representable relation algebras.
In the Bulletin of the Interest Group in Pure and Applied Logics ( IGPL ), pp77 -92, volume 3, number 1, March 1995.
R. Hirsch. Relation algebras of intervals.
My thesis has three sections: Relation Algebra; Intervals; Applications in Planning. Diagrams are missing.
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)

This page was last modified on 02 Apr 2025 and is maintained by Robin Hirsch

Computer Science Department

University College London

Gower Street

London

WC1E 6BT

+44 (0)20 7679 7214