5 found
  1.  28
    Constraint Satisfaction, Irredundant Axiomatisability and Continuous Colouring.Marcel Jackson & Belinda Trotta - 2013 - Studia Logica 101 (1):65-94.
    We observe a number of connections between recent developments in the study of constraint satisfaction problems, irredundant axiomatisation and the study of topological quasivarieties. Several restricted forms of a conjecture of Clark, Davey, Jackson and Pitkethly are solved: for example we show that if, for a finite relational structure M, the class of M-colourable structures has no finite axiomatisation in first order logic, then there is no set (even infinite) of first order sentences characterising the continuously M-colourable structures amongst compact (...)
    Direct download (4 more)  
    Export citation  
    Bookmark   2 citations  
  2.  18
    Undecidability of representability as binary relations.Robin Hirsch & Marcel Jackson - 2012 - Journal of Symbolic Logic 77 (4):1211-1244.
    In this article we establish the undecidability of representability and of finite representability as algebras of binary relations in a wide range of signatures. In particular, representability and finite representability are undecidable for Boolean monoids and lattice ordered monoids, while representability is undecidable for Jónsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions.
    Direct download (7 more)  
    Export citation  
    Bookmark   1 citation  
  3.  2
    Undecidability of Algebras of Binary Relations.Robin Hirsch, Ian Hodkinson & Marcel Jackson - 2021 - In Elena Aladova, Pablo Barceló, Johan van Benthem, Gerald Berger, Katrin M. Dannert, Neil Dewar, Răzvan Diaconescu, Ivo Düntsch, Wojciech Dzik, M. Eyad Kurd-Misto, Giambattista Formica, Michèle Friend, Robert Goldblatt, Georg Gottlob, Erich Grädel, Robin Hirsch, Ian Hodkinson, Marcel Jackson, Peter Jipsen, Roger D. Maddux, J. B. Manchak, Ewa Orłowska, Andreas Pieris, Boris Plotkin, Tatjana Plotkin, Vaughan R. Pratt, Ian Pratt-Hartmann, Tarek Sayed Ahmed, James Owen Weatherall, Dag Westerståhl, James Wimberley, Krzysztof Wójtowicz & Christian Wüthrich (eds.), Hajnal Andréka and István Németi on Unity of Science: From Computing to Relativity Theory Through Algebraic Logic. Springer Verlag. 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  
  4.  33
    Flat algebras and the translation of universal Horn logic to equational logic.Marcel Jackson - 2008 - Journal of Symbolic Logic 73 (1):90-128.
    We describe which subdirectly irreducible flat algebras arise in the variety generated by an arbitrary class of flat algebras with absorbing bottom element. This is used to give an elementary translation of the universal Horn logic of algebras, and more generally still, partial structures into the equational logic of conventional algebras. A number of examples and corollaries follow. For example, the problem of deciding which finite algebras of some fixed type have a finite basis for their quasi-identities is shown to (...)
    Direct download (6 more)  
    Export citation  
    Bookmark   1 citation  
  5.  6
    Restriction in Program Algebra.Marcel Jackson & Tim Stokes - 2023 - Logic Journal of the IGPL 31 (5):926-960.
    We provide complete classifications of algebras of partial maps for a significant swathe of combinations of operations not previously classified. Our focus is the many subsidiary operations that arise in recent considerations of the ‘override’ and ‘update’ operations arising in specification languages. These other operations turn out to have an older pedigree: domain restriction, set subtraction and intersection. All signatures considered include domain restriction, at least as a term. Combinations of the operations are classified and given complete axiomatizations with and (...)
    Direct download (3 more)  
    Export citation