58 found
Order:
Disambiguations
Ian Hodkinson [52]I. Hodkinson [9]I. M. Hodkinson [2]Im Hodkinson [1]
  1.  49
    Temporal Logic: Mathematical Foundations and Computational Aspects.Dov M. Gabbay, Ian Hodkinson & Mark A. Reynolds - 1994 - Oxford University Press on Demand.
    This much-needed book provides a thorough account of temporal logic, one of the most important areas of logic in computer science today. The book begins with a solid introduction to semantical and axiomatic approaches to temporal logic. It goes on to cover predicate temporal logic, meta-languages, general theories of axiomatization, many dimensional systems, propositional quantifiers, expressive power, Henkin dimension, temporalization of other logics, and decidability results. With its inclusion of cutting-edge results and unifying methodologies, this book is an indispensable reference (...)
    Direct download  
     
    Export citation  
     
    Bookmark   39 citations  
  2.  66
    Complete representations in algebraic logic.Robin Hirsch & Ian Hodkinson - 1997 - Journal of Symbolic Logic 62 (3):816-847.
    A boolean algebra is shown to be completely representable if and only if it is atomic, whereas it is shown that neither the class of completely representable relation algebras nor the class of completely representable cylindric algebras of any fixed dimension (at least 3) are elementary.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   29 citations  
  3.  42
    Atom structures of cylindric algebras and relation algebras.Ian Hodkinson - 1997 - Annals of Pure and Applied Logic 89 (2):117-148.
    For any finite n 3 there are two atomic n-dimensional cylindric algebras with the same atom structure, with one representable, the other, not.Hence, the complex algebra of the atom structure of a representable atomic cylindric algebra is not always representable, so that the class RCAn of representable n-dimensional cylindric algebras is not closed under completions. Further, it follows by an argument of Venema that RCAn is not axiomatisable by Sahlqvist equations, and hence nor by equations where negation can only occur (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   25 citations  
  4.  75
    (1 other version)Decidable fragments of first-order temporal logics.Ian Hodkinson, Frank Wolter & Michael Zakharyaschev - 2000 - Annals of Pure and Applied Logic 106 (1-3):85-134.
    In this paper, we introduce a new fragment of the first-order temporal language, called the monodic fragment, in which all formulas beginning with a temporal operator have at most one free variable. We show that the satisfiability problem for monodic formulas in various linear time structures can be reduced to the satisfiability problem for a certain fragment of classical first-order logic. This reduction is then used to single out a number of decidable fragments of first-order temporal logics and of two-sorted (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   25 citations  
  5.  46
    Spatial logic of tangled closure operators and modal mu-calculus.Robert Goldblatt & Ian Hodkinson - 2017 - Annals of Pure and Applied Logic 168 (5):1032-1090.
  6. Step by step – Building representations in algebraic logic.Robin Hirsch & Ian Hodkinson - 1997 - Journal of Symbolic Logic 62 (1):225-279.
    We consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterized according to the outcome of certain games. The Lyndon conditions defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finite relation algebras with homogeneous representations are characterized by first order formulas. Equivalence games are defined, and are used to establish whether an (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   14 citations  
  7.  29
    The Finite Model Property for Logics with the Tangle Modality.Robert Goldblatt & Ian Hodkinson - 2018 - Studia Logica 106 (1):131-166.
    The tangle modality is a propositional connective that extends basic modal logic to a language that is expressively equivalent over certain classes of finite frames to the bisimulation-invariant fragments of both first-order and monadic second-order logic. This paper axiomatises several logics with tangle, including some that have the universal modality, 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, including local and global connectedness (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  8.  89
    Provability with finitely many variables.Robin Hirsch, Ian Hodkinson & Roger D. Maddux - 2002 - Bulletin of Symbolic Logic 8 (3):348-379.
    For every finite n ≥ 4 there is a logically valid sentence φ n with the following properties: φ n contains only 3 variables (each of which occurs many times); φ n contains exactly one nonlogical binary relation symbol (no function symbols, no constants, and no equality symbol): φ n has a proof in first-order logic with equality that contains exactly n variables, but no proof containing only n - 1 variables. This result was first proved using the machinery of (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  9. (2 other versions)On modal logics between K × K × K and s5 × s5 × S.R. Hirsch, I. Hodkinson & A. Kurucz - 2002 - Journal of Symbolic Logic 67 (1):221-234.
    We prove that everyn-modal logic betweenKnandS5nis undecidable, whenever n ≥ 3. We also show that each of these logics is non-finitely axiomatizable, lacks the product finite model property, and there is no algorithm deciding whether a finite frame validates the logic. These results answer several questions of Gabbay and Shehtman. The proofs combine the modal logic technique of Yankov–Fine frame formulas with algebraic logic results of Halmos, Johnson and Monk, and give a reduction of the representation problem of finite relation (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  10.  35
    Relation algebras with n-dimensional relational bases.Robin Hirsch & Ian Hodkinson - 2000 - Annals of Pure and Applied Logic 101 (2-3):227-274.
    We study relation algebras with n-dimensional relational bases in the sense of Maddux. Fix n with 3nω. Write Bn for the class of non-associative algebras with an n-dimensional relational basis, and RAn for the variety generated by Bn. We define a notion of relativised representation for algebras in RAn, and use it to give an explicit equational axiomatisation of RAn, and to reprove Maddux's result that RAn is canonical. We show that the algebras in Bn are precisely those that have (...))
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  11. Sahlqvist Correspondence for Modal mu-calculus.Johan van Benthem, Nick Bezhanishvili & Ian Hodkinson - 2012 - Studia Logica 100 (1-2):31-60.
    We define analogues of modal Sahlqvist formulas for the modal mu-calculus, and prove a correspondence theorem for them.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  12. (1 other version)Relation Algebras by Games.Robin Hirsch & Ian Hodkinson - 2003 - Bulletin of Symbolic Logic 9 (4):515-520.
     
    Export citation  
     
    Bookmark   10 citations  
  13.  35
    Relation algebras from cylindric algebras, II.Robin Hirsch & Ian Hodkinson - 2001 - Annals of Pure and Applied Logic 112 (2-3):267-297.
    We prove, for each 4⩽ n ω , that S Ra CA n+1 cannot be defined, using only finitely many first-order axioms, relative to S Ra CA n . The construction also shows that for 5⩽n S Ra CA n is not finitely axiomatisable over RA n , and that for 3⩽m S Nr m CA n+1 is not finitely axiomatisable over S Nr m CA n . In consequence, for a certain standard n -variable first-order proof system ⊢ m (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  14. Loosely guarded fragment of first-order logic has the finite model property.Ian Hodkinson - 2002 - Studia Logica 70 (2):205 - 240.
    We show that the loosely guarded and packed fragments of first-order logic have the finite model property. We use a construction of Herwig and Hrushovski. We point out some consequences in temporal predicate logic and algebraic logic.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  15.  55
    Finite algebras of relations are representable on finite sets.H. Andreka, I. Hodkinson & I. Nemeti - 1999 - Journal of Symbolic Logic 64 (1):243-267.
    Using a combinatorial theorem of Herwig on extending partial isomorphisms of relational structures, we give a simple proof that certain classes of algebras, including Crs, polyadic Crs, and WA, have the `finite base property' and have decidable universal theories, and that any finite algebra in each class is representable on a finite set.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  16.  73
    Finite conformal hypergraph covers and Gaifman cliques in finite structures.Ian Hodkinson & Martin Otto - 2003 - Bulletin of Symbolic Logic 9 (3):387-405.
    We provide a canonical construction of conformal covers for finite hypergraphs and present two immediate applications to the finite model theory of relational structures. In the setting of relational structures, conformal covers serve to construct guarded bisimilar companion structures that avoid all incidental Gaifman cliques-thus serving as a partial analogue in finite model theory for the usually infinite guarded unravellings. In hypergraph theoretic terms, we show that every finite hypergraph admits a bisimilar cover by a finite conformal hypergraph. In terms (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  17.  68
    Erdős graphs resolve fine's canonicity problem.Robert Goldblatt, Ian Hodkinson & Yde Venema - 2004 - Bulletin of Symbolic Logic 10 (2):186-208.
    We show that there exist 2 ℵ 0 equational classes of Boolean algebras with operators that are not generated by the complex algebras of any first-order definable class of relational structures. Using a variant of this construction, we resolve a long-standing question of Fine, by exhibiting a bimodal logic that is valid in its canonical frames, but is not sound and complete for any first-order definable class of Kripke frames (a monomodal example can then be obtained using simulation results of (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  18.  25
    Omega-categoricity, relative categoricity and coordinatisation.Wilfrid Hodges, I. M. Hodkinson & Dugald Macpherson - 1990 - Annals of Pure and Applied Logic 46 (2):169-199.
  19.  35
    Hybrid Formulas and Elementarily Generated Modal Logics.Ian Hodkinson - 2006 - Notre Dame Journal of Formal Logic 47 (4):443-478.
    We characterize the modal logics of elementary classes of Kripke frames as precisely those modal logics that are axiomatized by modal axioms synthesized in a certain effective way from "quasi-positive" sentences of hybrid logic. These are pure positive hybrid sentences with arbitrary existential and relativized universal quantification over nominals. The proof has three steps. The first step is to use the known result that the modal logic of any elementary class of Kripke frames is also the modal logic of the (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  20.  99
    Bare canonicity of representable cylindric and polyadic algebras.Jannis Bulian & Ian Hodkinson - 2013 - Annals of Pure and Applied Logic 164 (9):884-906.
    We show that for finite n⩾3n⩾3, every first-order axiomatisation of the varieties of representable n-dimensional cylindric algebras, diagonal-free cylindric algebras, polyadic algebras, and polyadic equality algebras contains an infinite number of non-canonical formulas. We also show that the class of structures for each of these varieties is non-elementary. The proofs employ algebras derived from random graphs.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  21.  31
    The McKinsey–Lemmon logic is barely canonical.Robert Goldblatt & Ian Hodkinson - 2007 - Australasian Journal of Logic 5:1-19.
    We study a canonical modal logic introduced by Lemmon, and axiomatised by an infinite sequence of axioms generalising McKinsey’s formula. We prove that the class of all frames for this logic is not closed under elementary equivalence, and so is non-elementary. We also show that any axiomatisation of the logic involves infinitely many non-canonical formulas.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  22.  44
    Sahlqvist Correspondence for Modal mu-calculus.Johan Benthem, Nick Bezhanishvili & Ian Hodkinson - 2012 - Studia Logica 100 (1-2):31-60.
    We define analogues of modal Sahlqvist formulas for the modal mu-calculus, and prove a correspondence theorem for them.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  23.  53
    Relation algebras from cylindric algebras, I.Robin Hirsch & Ian Hodkinson - 2001 - Annals of Pure and Applied Logic 112 (2-3):225-266.
    We characterise the class S Ra CA n of subalgebras of relation algebra reducts of n -dimensional cylindric algebras by the notion of a ‘hyperbasis’, analogous to the cylindric basis of Maddux, and by representations. We outline a game–theoretic approximation to the existence of a representation, and how to use it to obtain a recursive axiomatisation of S Ra CA n.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  24.  91
    Monodic packed fragment with equality is decidable.Ian Hodkinson - 2002 - Studia Logica 72 (2):185-197.
    We prove decidability of satisfiability of sentences of the monodic packed fragment of first-order temporal logic with equality and connectives Until and Since, in models with various flows of time and domains of arbitrary cardinality. We also prove decidability over models with finite domains, over flows of time including the real order.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  25.  76
    Strongly representable atom structures of cylindric algebras.Robin Hirsch & Ian Hodkinson - 2009 - Journal of Symbolic Logic 74 (3):811-828.
    A cylindric algebra atom structure is said to be strongly representable if all atomic cylindric algebras with that atom structure are representable. This is equivalent to saying that the full complex algebra of the atom structure is a representable cylindric algebra. We show that for any finite n >3, the class of all strongly representable n-dimensional cylindric algebra atom structures is not closed under ultraproducts and is therefore not elementary. Our proof is based on the following construction. From an arbitrary (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  26.  36
    On canonical modal logics that are not elementarily determined.Robert Goldblatt, Ian Hodkinson & Yde Venema - 2003 - Logique Et Analyse 181:77-101.
  27.  15
    The Tangled Derivative Logic of the Real Line and Zero-Dimensional Space.Robert Goldblatt & Ian Hodkinson - 2016 - In Lev Beklemishev, Stéphane Demri & András Máté (eds.), Advances in Modal Logic, Volume 11. CSLI Publications. pp. 342-361.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   2 citations  
  28. On modal logics between K × K × K and $s5 \times s5 \times s5$.R. Hirsch, I. Hodkinson & A. Kurucz - 2002 - Journal of Symbolic Logic 67 (1):221 - 234.
    We prove that every n-modal logic between K n and S5 n is undecidable, whenever n ≥ 3. We also show that each of these logics is non- finitely axiomatizable, lacks the product finite model property, and there is no algorithm deciding whether a finite frame validates the logic. These results answer several questions of Gabbay and Shehtman. The proofs combine the modal logic technique of Yankov-Fine frame formulas with algebraic logic results of Halmos, Johnson and Monk, and give a (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  29.  60
    Finite h-dimension does not imply expressive completeness.Ian Hodkinson - 1994 - Journal of Philosophical Logic 23 (5):535 - 573.
    A conjecture of Gabbay (1981) states that any class of flows of time having the property known as finite H-dimension admits a finite set of expressively complete one-dimensional temporal connectives. Here we show that the class of 'circular' structures refutes the generalisation of this conjecture to Kripke frames. We then construct from this class, by a general method, a new class of irreflexive transitive flows of time that refutes the original conjecture. Our paper includes full descriptions of a method for (...)
    No categories
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  30.  26
    Axiomatising Various Classes of Relation and Cylindric Algebras.Robin Hirsch & Ian Hodkinson - 1997 - Logic Journal of the IGPL 5 (2):209-229.
    We outline a simple approach to axiomatising the class of representable relation algebras, using games. We discuss generalisations of the method to cylindric algebras, homogeneous and complete representations, and atom structures of relation algebras.
    Direct download  
     
    Export citation  
     
    Bookmark   3 citations  
  31.  18
    Complexity of monodic guarded fragments over linear and real time.Ian Hodkinson - 2006 - Annals of Pure and Applied Logic 138 (1):94-125.
    We show that the satisfiability problem for the monodic guarded, loosely guarded, and packed fragments of first-order temporal logic with equality is 2Exptime-complete for structures with arbitrary first-order domains, over linear time, dense linear time, rational number time, and some other classes of linear flows of time. We then show that for structures with finite first-order domains, these fragments are also 2Exptime-complete over real number time and hence over most of the commonly used linear flows of time, including the natural (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  32.  14
    Languages, Meta-languages and METATEM, A Discussion Paper.Howard Barringer, Graham Gough, Derek Brough, Dov Gabbay & Ian Hodkinson - 1996 - Logic Journal of the IGPL 4 (2):255-272.
    Meta-languages are vital to the development and usage of formal systems, and yet the nature of meta-languages and associated notions require clarification. Here we attempt to provide a clear definition of the requirements for a language to be a meta-language, together with consideration of issues of proof theory, model theory and interpreters for such a language.
    Direct download  
     
    Export citation  
     
    Bookmark  
  33.  42
    All Normal Extensions of S5-squared Are Finitely Axiomatizable.Nick Bezhanishvili & Ian Hodkinson - 2004 - Studia Logica 78 (3):443-457.
    We prove that every normal extension of the bi-modal system S52 is finitely axiomatizable and that every proper normal extension has NP-complete satisfiability problem.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  34.  12
    Canonicity in Power and Modal Logics of Finite Achronal Width.Robert Goldblatt & Ian Hodkinson - 2024 - Review of Symbolic Logic 17 (3):705-735.
    We develop a method for showing that various modal logics that are valid in their countably generated canonical Kripke frames must also be valid in their uncountably generated ones. This is applied to many systems, including the logics of finite width, and a broader class of multimodal logics of ‘finite achronal width’ that are introduced here.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  35.  24
    Strong Completeness of Modal Logics Over 0-Dimensional Metric Spaces.Robert Goldblatt & Ian Hodkinson - 2020 - Review of Symbolic Logic 13 (3):611-632.
    We prove strong completeness results for some modal logics with the universal modality, with respect to their topological semantics over 0-dimensional dense-in-themselves metric spaces. We also use failure of compactness to show that, for some languages and spaces, no standard modal deductive system is strongly complete.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  36. Mosaics and step-by-step. Remarks on “A modal logic of relations”.Robin Hirsch, Ian Hodkinson, Maarten Marx, Szabolsc Mikulás & Mark Reynolds - 1999 - In E. Orłowska (ed.), Logic at Work. Heidelberg.
     
    Export citation  
     
    Bookmark  
  37. Mosaics and step-by-step| Remarks onA modal logic of relations' by Venema & Marx.Robin Hirsch & Ian Hodkinson - 1999 - In E. Orłowska (ed.), Logic at Work. Heidelberg.
     
    Export citation  
     
    Bookmark  
  38. (1 other version)On the number of variables required for proofs.Robin Hirsch, I. Hodkinson & Roger Maddux - 2002 - Journal of Symbolic Logic 67 (1):197-213.
     
    Export citation  
     
    Bookmark   1 citation  
  39.  9
    Undecidability of Algebras of Binary Relations.Robin Hirsch, Ian Hodkinson & Marcel Jackson - 2021 - In Judit Madarász & Gergely Székely (eds.), Hajnal Andréka and István Németi on Unity of Science: From Computing to Relativity Theory Through Algebraic Logic. Springer. pp. 267-287.
    Let S be a signature of operations and relations definable in relation algebra, let R be the class of all S-structures isomorphic to concrete algebras of binary relations with concrete interpretations for symbols in S, and let F be the class of S-structures isomorphic to concrete algebras of binary relations over a finite base. To prove that membership of R or F for finite S-structures is undecidable, we reduce from a known undecidable problem—here we use the tiling problem, the partial (...)
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  40.  80
    Weak representations of relation algebras and relational bases.Robin Hirsch, Ian Hodkinson & Roger D. Maddux - 2011 - Journal of Symbolic Logic 76 (3):870 - 882.
    It is known that for all finite n ≥ 5, there are relation algebras with n-dimensional relational bases but no weak representations. We prove that conversely, there are finite weakly representable relation algebras with no n-dimensional relational bases. In symbols: neither of the classes RA n and wRRA contains the other.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  41.  73
    A bisimulation characterization theorem for hybrid logic with the current-state Binder.Ian Hodkinson & Hicham Tahiri - 2010 - Review of Symbolic Logic 3 (2):247-261.
    We prove that every first-order formula that is invariant under quasi-injective bisimulations is equivalent to a formula of the hybrid logic . Our proof uses a variation of the usual unravelling technique. We also briefly survey related results, and show in a standard way that it is undecidable whether a first-order formula is invariant under quasi-injective bisimulations.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark  
  42.  19
    Axiomatizing hybrid logic using modal logic.Ian Hodkinson & Louis Paternault - 2010 - Journal of Applied Logic 8 (4):386-396.
  43. EVANS, DM, and HEWITT, PR, Counterexamples to a con-jecture on relative categoricity GOODMAN, ND, Topological models of epistemic set theory HEWITT, PR, see EVANS, DM.W. Hodges, Im Hodkinson & D. Macpherson - 1990 - Annals of Pure and Applied Logic 46:299.
  44. Fragments of rst-order temporal logics.I. Hodkinson, F. Wolter & M. Zakharyaschev - forthcoming - Annals of Pure and Applied Logic.
     
    Export citation  
     
    Bookmark  
  45.  18
    Friedman, Sy D. and VeliCkovit, B., Al-Definability.I. Hodkinson, R. Kaye, I. Korec, F. Maurin, H. Mildenberger & F. O. Wagner - 1997 - Annals of Pure and Applied Logic 89 (1):277.
  46. J. Väänänen, Models and games.Ian Hodkinson - 2012 - Bulletin of Symbolic Logic 18 (3):406.
  47.  28
    L. Csirmaz, D. Gabbay, M. de Rijke, eds., Logic colloquium '92, studies in logic language, and information'.Ian Hodkinson - 1997 - Journal of Logic, Language and Information 6 (4):453-457.
  48.  11
    Non-representable relation algebras from vector spaces.Ian Hodkinson - 2020 - Australasian Journal of Logic 17 (2):82-109.
    Extending a construction of Andreka, Givant, and Nemeti (2019), we construct some finite vector spaces and use them to build finite non-representable relation algebras. They are simple, measurable, and persistently finite, and they validate arbitrary finite sets of equations that are valid in the variety RRA of representable relation algebras. It follows that there is no finitely axiomatisable class of relation algebras that contains RRA and validates every equation that is both valid in RRA and preserved by completions of relation (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  49.  34
    On canonicity and completions of weakly representable relation algebras.Ian Hodkinson & Szabolcs Mikulás - 2012 - Journal of Symbolic Logic 77 (1):245-262.
    We show that the variety of weakly representable relation algebras is neither canonical nor closed under Monk completions.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  50.  41
    Relational structures determined by their finite induced substructures.I. M. Hodkinson & H. D. Macpherson - 1988 - Journal of Symbolic Logic 53 (1):222-230.
    A countably infinite relational structure M is called absolutely ubiquitous if the following holds: whenever N is a countably infinite structure, and M and N have the same isomorphism types of finite induced substructures, there is an isomorphism from M to N. Here a characterisation is given of absolutely ubiquitous structures over languages with finitely many relation symbols. A corresponding result is proved for uncountable structures.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
1 — 50 / 58