Publications
93 results found
Goldblatt R, Hodkinson I, 2023, CANONICITY IN POWER AND MODAL LOGICS OF FINITE ACHRONAL WIDTH, REVIEW OF SYMBOLIC LOGIC, ISSN: 1755-0203
Hirsch R, Hodkinson I, Jackson M, 2021, Undecidability of Algebras of Binary Relations, Outstanding Contributions to Logic, Pages: 267-287
Let S be a signature of operations and relations definable in relation algebra (e.g. converse, composition, containment, union, identity, etc.), let R(S) be the class of all S-structures isomorphic to concrete algebras of binary relations with concrete interpretations for symbols in S, and let F(S) be the class of S-structures isomorphic to concrete algebras of binary relations over a finite base. To prove that membership of R(S) or F(S) for finite S-structures is undecidable, we reduce from a known undecidable problem—here we use the tiling problem, the partial group embedding problem and the partial group finite embedding problem to prove undecidability of finite membership of R(S) or F(S) for various signatures S. It follows that the equational theory of R(S) is undecidable whenever S includes the boolean operators and composition. We give an exposition of the reduction from the tiling problem and the reduction from the group embedding problem, and summarize what we know about the undecidability of finite membership of R(S) and of F(S) for different signatures S.
Goldblatt R, Hodkinson I, 2020, STRONG COMPLETENESS OF MODAL LOGICS OVER 0-DIMENSIONAL METRIC SPACES, Publisher: CAMBRIDGE UNIV PRESS
- Author Web Link
- Cite
- Citations: 1
Hodkinson I, 2020, On the variety generated by completions of representable relation algebras, ALGEBRA UNIVERSALIS, Vol: 81, ISSN: 0002-5240
Hodkinson I, 2020, Non-representable relation algebras from vector spaces, AUSTRALASIAN JOURNAL OF LOGIC, Vol: 17, Pages: 82-109, ISSN: 1448-5052
Goldblatt R, Hodkinson I, 2017, Spatial logic of tangled closure operators and modal mu-calculus, Annals of Pure and Applied Logic, Vol: 168, Pages: 1032-1090, ISSN: 1873-2461
There has been renewed interest in recent years in McKinsey and Tarski’s interpretation of modallogic in topological spaces and their proof that S4 is the logic of any separable dense-in-itselfmetric space. Here we extend this work to the modal mu-calculus and to a logic of tangledclosure operators that was developed by Fernández-Duque after these two languages had beenshown by Dawar and Otto to have the same expressive power over finite transitive Kripke models.We prove that this equivalence remains true over topological spaces.We extend the McKinsey–Tarski topological ‘dissection lemma’. We also take advantageof the fact (proved by us elsewhere) that various tangled closure logics with and without theuniversal modality ∀ have the finite model property in Kripke semantics. These results are usedto construct a representation map (also called a d-p-morphism) from any dense-in-itself metricspace X onto any finite connected locally connected serial transitive Kripke frame.This yields completeness theorems over X for a number of languages: (i) the modal mucalculuswith the closure operator <>; (ii) <> and the tangled closure operators <t> (in fact <t> canexpress <>); (iii) <>, ∀; (iv) <>, ∀, <t>; (v) the derivative operator <d>; (vi) <d> and the associatedtangled closure operators <dt>; (vii) <d>, ∀; (viii) <d>, ∀,<dt>. Soundness also holds, if: (a) forlanguages with ∀, X is connected; (b) for languages with <d>, X validates the well-known axiomG1. For countable languages without ∀, we prove strong completeness. We also show thatin the presence of ∀, strong completeness fails if X is compact and locally connected
Goldblatt R, Hodkinson I, 2017, Tangled closure algebras, Categories and General Algebraic Structures with Applications, Vol: 7, Pages: 9-31, ISSN: 2345-5853
The tangled closure of a collection of subsets of a topological space is the largest subset in which each member of the collection is dense. This operation models a logical 'tangle modality' connective, of significance in finite model theory. Here we study an abstract equational algebraic formulation of the operation which generalises the McKinsey-Tarski theory of closure algebras. We show that any dissectable tangled closure algebra, such as the algebra of subsets of any metric space without isolated points, contains copies of every finite tangled closure algebra. We then exhibit an example of a tangled closure algebra that cannot be embedded into any complete tangled closure algebra, so it has no MacNeille completion and no spatial representation.
Goldblatt R, Hodkinson I, 2017, The finite model property for logics with the tangle modality, Studia Logica, Vol: 106, Pages: 131-166, ISSN: 1572-8730
The tangle modality is a propositional connective that extends basic modallogic to a language that is expressively equivalent over certain classes of finite frames tothe bisimulation-invariant fragments of both first-order and monadic second-order logic.This paper axiomatises several logics with tangle, including some that have the universalmodality, and shows that they have the finite model property for Kripke frame semantics.The logics are specified by a variety of conditions on their validating frames, includinglocal and global connectedness properties. Some of the results have been used to obtaincompleteness theorems for interpretations of tangled modal logics in topological spaces.
Goldblatt R, Hodkinson I, 2016, The Tangled Derivative Logic of the Real Line and Zero-Dimensional Spaces, 11th Conference on Advances in Modal Logic, AiML 2016, Publisher: College Publications, Pages: 342-361
In a topological setting in which the diamond modality is interpreted as the derivative(set of limit points) operator, we study a ‘tangled derivative’ connective that assigns toany finite set of propositions the largest set in which all those propositions are strictlydense. Building on earlier work of ourselves and others we axiomatise the resultinglogic of the real line. We then show that the logic of any zero-dimensional dense-initselfmetric space is the ‘tangled’ extension of KD4, eliminating an assumption ofseparability in previous results for zero-dimensional spaces. This requires new kindsof ‘dissection lemma’ in the sense of McKinsey-Tarski. We extend the analysis toinclude the universal modality, and also show that the tangled extension of KD4 hasa strong completeness result for topological models that fails for its Kripke semantics.
Goldblatt R, Hodkinson I, 2016, Spatial logic of modal mu-calculus and tangled closure operators, arxiv
There has been renewed interest in recent years in McKinsey and Tarski'sinterpretation of modal logic in topological spaces and their proof that S4 isthe logic of any separable dense-in-itself metric space. Here we extend thiswork to the modal mu-calculus and to a logic of tangled closure operators thatwas developed by Fern\'andez-Duque after these two languages had been shown byDawar and Otto to have the same expressive power over finite transitive Kripkemodels. We prove that this equivalence remains true over topological spaces. We establish the finite model property in Kripke semantics for varioustangled closure logics with and without the universal modality $\forall$. Wealso extend the McKinsey--Tarski topological `dissection lemma'. These resultsare used to construct a representation map (also called a d-p-morphism) fromany dense-in-itself metric space $X$ onto any finite connected locallyconnected serial transitive Kripke frame. This yields completeness theorems over $X$ for a number of languages: (i) themodal mu-calculus with the closure operator $\Diamond$; (ii) $\Diamond$ and thetangled closure operators $\langle t \rangle$; (iii) $\Diamond,\forall$; (iv)$\Diamond,\forall,\langle t \rangle$; (v) the derivative operator $\langle d\rangle$; (vi) $\langle d \rangle$ and the associated tangled closure operators$\langle dt \rangle$; (vii) $\langle d \rangle,\forall$; (viii) $\langle d\rangle,\forall,\langle dt \rangle$. Soundness also holds, if: (a) forlanguages with $\forall$, $X$ is connected; and (b) for languages with $\langled \rangle$, $X$ validates the well known axiom $\mathrm{G}_1$. For countablelanguages without $\forall$, we prove strong completeness. We also show that inthe presence of $\forall$, strong completeness fails if $X$ is compact andlocally connected.
Hodkinson I, 2015, Connections between Relation Algebras and Cylindric Algebras, 15th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS), Publisher: Springer, Pages: 27-42, ISSN: 0302-9743
We give an informal description of a recursive representability-preserving reduction of relation algebras to cylindric algebras.
Dean S, Sunter J, Wheeler RJ, et al., 2015, A toolkit enabling efficient, scalable and reproducible gene tagging in trypanosomatids, Open Biology, Vol: 5, ISSN: 2046-2441
Hodkinson I, 2013, On the Priorean temporal logic with 'around now' over the real line, Journal of Logic and Computation, Vol: 24, Pages: 1071-1110, ISSN: 1465-363X
We consider the temporal language with the Priorean operators G and H expressing that a formula is true at all future times and all past times, plus an operator □ expressing that a formula is true throughout some open interval containing the evaluation time (i.e. it is true ‘around now’). We show that the logic of time based on the real numbers in this language is finitely axiomatizable, answering an implicit question of Shehtman (1993). We also show that the logic has PSPACE-complete complexity, but is not Kripke complete and has no strongly complete axiomatization.
Bulian J, Hodkinson I, 2013, Bare canonicity of representable cylindric and polyadic algebras, ANNALS OF PURE AND APPLIED LOGIC, Vol: 164, Pages: 884-906, ISSN: 0168-0072
- Author Web Link
- Open Access Link
- Cite
- Citations: 7
Hodkinson I, 2013, Simple completeness proofs for some spatial logics of the real line, 12th Asian Logic Conference, Publisher: World Scientific, Pages: 155-177
Hodkinson I, 2012, A construction of cylindric and polyadic algebras from atomic relation algebras, ALGEBRA UNIVERSALIS, Vol: 68, Pages: 257-285, ISSN: 0002-5240
- Author Web Link
- Cite
- Citations: 3
Bezhanishvili N, Hodkinson I, 2012, Preservation of Sahlqvist fixed point equations in completions of relativized fixed point Boolean algebras with operators, ALGEBRA UNIVERSALIS, Vol: 68, Pages: 43-56, ISSN: 0002-5240
- Author Web Link
- Cite
- Citations: 3
Bezhanishvili N, Hodkinson I, 2012, Sahlqvist theorem for modal fixed point logic, THEORETICAL COMPUTER SCIENCE, Vol: 424, Pages: 1-19, ISSN: 0304-3975
- Author Web Link
- Cite
- Citations: 10
Hodkinson I, Mikulas S, 2012, ON CANONICITY AND COMPLETIONS OF WEAKLY REPRESENTABLE RELATION ALGEBRAS, JOURNAL OF SYMBOLIC LOGIC, Vol: 77, Pages: 245-262, ISSN: 0022-4812
van Benthem JFAK, Bezhanishvili N, Hodkinson I, 2012, Sahlqvist correspondence for modal mu-calculus, Studia Logica: an international journal for symbolic logic, Vol: 100, Pages: 31-60
Hirsch R, Hodkinson I, Maddux RD, 2011, Weak representations of relation algebras and relational bases, J SYMBOLIC LOGIC, Vol: 76, Pages: 870-882, ISSN: 0022-4812
Hodkinson I, Paternault L, 2010, Axiomatizing hybrid logic using modal logic, JOURNAL OF APPLIED LOGIC, Vol: 8, Pages: 386-396, ISSN: 1570-8683
- Author Web Link
- Cite
- Citations: 1
Hodkinson I, 2010, THE BOUNDED FRAGMENT AND HYBRID LOGIC WITH POLYADIC MODALITIES, REVIEW OF SYMBOLIC LOGIC, Vol: 3, Pages: 279-286, ISSN: 1755-0203
Hodkinson I, Tahiri H, 2010, A BISIMULATION CHARACTERIZATION THEOREM FOR HYBRID LOGIC WITH THE CURRENT-STATE BINDER, REVIEW OF SYMBOLIC LOGIC, Vol: 3, Pages: 247-261, ISSN: 1755-0203
Hirsch R, Hodkinson I, 2009, STRONGLY REPRESENTABLE ATOM STRUCTURES OF CYLINDRIC ALGEBRAS, JOURNAL OF SYMBOLIC LOGIC, Vol: 74, Pages: 811-828, ISSN: 0022-4812
- Author Web Link
- Open Access Link
- Cite
- Citations: 7
Hodkinson I, Hussain A, 2008, The modal logic of affine planes is not finitely axiomatisable, JOURNAL OF SYMBOLIC LOGIC, Vol: 73, Pages: 940-952, ISSN: 0022-4812
- Author Web Link
- Cite
- Citations: 2
Hodkinson I, Montanari A, Sciavicco G, 2008, Non-finite Axiomatizability and Undecidability of Interval Temporal Logics with C, D, and T, 22nd International Workshop on Computer Science Logic/17th Annual Conference of the European-Association-for-Computer-Science-Logic, Publisher: SPRINGER-VERLAG BERLIN, Pages: 308-+, ISSN: 0302-9743
- Author Web Link
- Cite
- Citations: 11
Goldblatt R, Hodkinson IM, 2008, Commutativity of quantifiers in varying-domain Kripke models, Towards Mathematical Philosophy (Trends in Logic IV), Publisher: Springer, Pages: 9-30
Hodkinson I, Goldblatt R, 2007, The McKinsey-Lemmon logic is barely canonical, The Australasian Journal of Logic, Vol: 5, Pages: 1-19
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.