Imperial College London

Emeritus ProfessorIanHodkinson

Faculty of EngineeringDepartment of Computing

Emeritus Professor of Logic and Computation
 
 
 
//

Contact

 

i.hodkinson Website

 
 
//

Location

 

noneHuxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Publication Type
Year
to

92 results found

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.

Book chapter

Goldblatt R, Hodkinson I, 2020, STRONG COMPLETENESS OF MODAL LOGICS OVER 0-DIMENSIONAL METRIC SPACES, Publisher: CAMBRIDGE UNIV PRESS

Working paper

Hodkinson I, 2020, On the variety generated by completions of representable relation algebras, ALGEBRA UNIVERSALIS, Vol: 81, ISSN: 0002-5240

Journal article

Hodkinson I, 2020, Non-representable relation algebras from vector spaces, AUSTRALASIAN JOURNAL OF LOGIC, Vol: 17, Pages: 82-109, ISSN: 1448-5052

Journal article

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

Journal article

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.

Journal article

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.

Journal article

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.

Conference paper

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.

Journal article

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.

Conference paper

Dean S, Sunter J, Wheeler RJ, Hodkinson I, Gluenz E, Gull Ket al., 2015, A toolkit enabling efficient, scalable and reproducible gene tagging in trypanosomatids, Open Biology, Vol: 5, ISSN: 2046-2441

Journal article

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.

Journal article

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

Journal article

Hodkinson I, 2013, Simple completeness proofs for some spatial logics of the real line, 12th Asian Logic Conference, Publisher: World Scientific, Pages: 155-177

Conference paper

Hodkinson I, 2012, A construction of cylindric and polyadic algebras from atomic relation algebras, ALGEBRA UNIVERSALIS, Vol: 68, Pages: 257-285, ISSN: 0002-5240

Journal article

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

Journal article

Bezhanishvili N, Hodkinson I, 2012, Sahlqvist theorem for modal fixed point logic, THEORETICAL COMPUTER SCIENCE, Vol: 424, Pages: 1-19, ISSN: 0304-3975

Journal article

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

Journal article

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

Journal article

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

Journal article

Hodkinson I, Paternault L, 2010, Axiomatizing hybrid logic using modal logic, JOURNAL OF APPLIED LOGIC, Vol: 8, Pages: 386-396, ISSN: 1570-8683

Journal article

Hodkinson I, 2010, Interval temporal logics with chop-like operators

Conference paper

Hodkinson I, 2010, THE BOUNDED FRAGMENT AND HYBRID LOGIC WITH POLYADIC MODALITIES, REVIEW OF SYMBOLIC LOGIC, Vol: 3, Pages: 279-286, ISSN: 1755-0203

Journal article

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

Journal article

Hirsch R, Hodkinson I, 2009, STRONGLY REPRESENTABLE ATOM STRUCTURES OF CYLINDRIC ALGEBRAS, JOURNAL OF SYMBOLIC LOGIC, Vol: 74, Pages: 811-828, ISSN: 0022-4812

Journal article

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

Journal article

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

Conference paper

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

Conference paper

Hodkinson I, Goldblatt R, 2007, The McKinsey-Lemmon logic is barely canonical, The Australasian Journal of Logic, Vol: 5, Pages: 1-19

Journal article

Hodkinson I, 2006, Complexity of monodic guarded fragments over linear and real time, Annals of Pure and Applied Logic, Vol: 138, Pages: 94-125, ISSN: 0168-0072

We show that the satisfiability problem for the monodic guarded and packed fragments with equality and arbitrary first-order domains over linear time, dense linear time, rational numbers time, and some other classes of linear flows of time, is 2Exptime-complete. We then show that with finite first-order domains, these fragments are also 2Exptime-complete over real numbers time, and (hence) over most of the commonly-used linear flows of time, including the natural numbers, integers, rationals, and any first-order definable class of linear flows of time.

Journal article

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.

Request URL: http://wlsprd.imperial.ac.uk:80/respub/WEB-INF/jsp/search-html.jsp Request URI: /respub/WEB-INF/jsp/search-html.jsp Query String: respub-action=search.html&id=00002783&limit=30&person=true