Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-19T11:43:11.438Z Has data issue: false hasContentIssue false
  • English
  • Français

Boolean and classical restriction categories

Published online by Cambridge University Press:  01 April 2009

ROBIN COCKETT  and
ERNIE MANES
ROBIN COCKETT
Affiliation:
Department of Computer Science, University of Calgary, Calgary, T2N 1N4, Alberta, Canada
ERNIE MANES
Affiliation:
Department of Mathematics and Statistics, University of Massachusetts, Amherst, Massachusetts 01003, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

A restriction category is an abstract category of partial maps. A Boolean restriction category is a restriction category that supports classical (Boolean) reasoning. Such categories are models of loop-free dynamic logic that is deterministic in the sense that < α > Q ⊂ [α]Q. Classical restriction categories are restriction categories with a locally Boolean structure: it is shown that they are precisely full subcategories of Boolean restriction categories. In particular, a Boolean restriction category may be characterised as a classical restriction category with finite coproducts in which all restriction idempotents split.

Every restriction category admits a restriction embedding into a Boolean restriction category. Thus, every abstract category of partial maps admits a conservative extension that supports classical reasoning. An explicit construction of the classical completion of a restriction category is given.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 19 , Issue 2 , April 2009 , pp. 357 - 416
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Batbedat, A. (1981) γ-demi-groups, demi-modules, produit demi-directs. Springer-Verlag Lecture Notes in Mathematics 855 1–18.CrossRefGoogle Scholar
Birkhoff, G. (1948) Lattice Theory, American Mathematical Society Colloquium Publications, Volume 25.Google Scholar
Cockett, J. R. B. and Lack, S. (2002) Restriction categories I: categories of partial maps. Theoretical Computer Science 270 223–259.CrossRefGoogle Scholar
Cockett, J. R. B. and Lack, S. (2003) Restriction categories II: partial map classification. Theoretical Computer Science 294 61–102.CrossRefGoogle Scholar
Cockett, J. R. B. and Lack, S. (2004) Restriction categories III: colimits, partial limits and extensivity. Mathematical Structures in Computer Science 17 (4)957–1027.Google Scholar
Cockett, J. R. B. and Guo, X. (2006) Stable meet semilattice fibrations and free restriction categories. Theory and Applications of Categories 16 307–341.Google Scholar
Cockett, J. R. B. and Guo, X. (to be submitted) Restrictions, ranges, partial map categories and fibrations.Google Scholar
Dijkstra, E. J. (1976) A Discipline of Programming, Prentice Hall.Google Scholar
Di Paola, R. A., and Heller, A. (1987) Dominical categories: recursion theory without elements. Journal of Symbolic Logic 52 595–635.CrossRefGoogle Scholar
Elgot, C. C. (1975) Monadic computation and iterative algebraic theories. In: Rose, H. E. and Shepherdson, J. C. (eds.) Proceedings of Logic Colloquium ’73, North-Holland, 175–230.Google Scholar
Escardó, M. H. (2001) The regular-locally compact coreflection of a stably locally compact locale. Journal of Pure and Applied Algebra 157 41–55.CrossRefGoogle Scholar
Fischer, M. J. and Ladner, R. E. (1976) Propositional dynamic logic of regular programs. Journal of Computer and System Sciences 18 286–294.Google Scholar
Fountain, J. (1977) A class of right PP monoids. Quarterly Journal of Mathematics 28 285–300.CrossRefGoogle Scholar
Freyd, P. J. (1972) Aspects of Topoi. Bulletin of the Australian Mathematical Society 7 1–76.CrossRefGoogle Scholar
Freyd, P. J. and Scedrov, A. (1990) Categories, Allegories, North-Holland.Google Scholar
Gould, V. (2002) (Weakly) left E-ample semigroups (notes). (Available at http://www-users.york.ac.uk/~varg1/gpubs.htm.)Google Scholar
Grandis, M. (1990) Cohesive Categories and Manifolds. Annali di Mathematica pura ed applicata 157 199–244.CrossRefGoogle Scholar
Kozen, D. H. A. and Tiuryn, J. (2000) Dynamic Logic, MIT Press.Google Scholar
Harel, D., Meyer, A. R. and Pratt, V. R. (1977) Computability and completeness in logics of programs. Proceedings of the 9th ACM Symposium on the Theory of Computing 261–268.Google Scholar
Jackson, M. and Stokes, T. (2001) An invitation to C-semigroups. Semigroup Forum 62 279–310.CrossRefGoogle Scholar
Jackson, M. and Stokes, T. (submitted) Partial maps with domain and range: extending Schein's representation.Google Scholar
Johnstone, P. T. (1982) Stone Spaces, Cambridge Studies in Advanced Mathematics 3, Cambridge University Press.Google Scholar
Kozen, D. (1980) A representation theorem for models of *-free PDL. In: de Bakker, J. W. and Van Leeuwen, J. (eds.) Automata, Languages and Programming, ICALP ’80. Springer-Verlag Lecture Notes in Computer Science 85 351–362.CrossRefGoogle Scholar
Manes, E. G. (1998) Implementing collection classes with monads. Mathematical Structures in Computer Science 8 231–276.CrossRefGoogle Scholar
Manes, E. G. (2002) Taut monads and T0 spaces. Theoretical Computer Science 275 79–109.CrossRefGoogle Scholar
Manes, E. G. (1992) Predicate Transformer Semantics, Cambridge University Press.CrossRefGoogle Scholar
Manes, E. G. (2006a) Guarded and banded semigroups. Semigroup Forum 72 94–120.CrossRefGoogle Scholar
Manes, E. G. (2006b) Boolean restriction categories and taut monads. Theoretical Computer Science 360 77–95.CrossRefGoogle Scholar
Menger, K. (1955) Calculus, a Modern Approach, Ginn, Boston.Google Scholar
Menger, K. (1959) An axiomatic theory of functions and fluents. In: Henkin, L., Suppes, P. and Tarski, A. (eds.) The Axiomatic Method, North-Holland454–473.CrossRefGoogle Scholar
Moggi, E. (1988) The Partial Lambda-Calculus, Ph.D. thesis, University of Edinburgh. (Available as CST-53-88.)Google Scholar
Mulry, P. S. (1992) Partial map classifiers and partial cartesian closed cartegories. Theoretical Computer Science 99 141–155.CrossRefGoogle Scholar
Resende, P. (2007) Étale groupoids and their quantales. Advances in Mathematics 208 147–209.CrossRefGoogle Scholar
Robinson, E. P. and Rosolini, G. (1988) Categories of partial maps. Information and computation 79 94–130.CrossRefGoogle Scholar
Schein, B. (1970a) Relation algebras and function semigroups. Semigroup Forum 1 1–62.CrossRefGoogle Scholar
Schein, B. (1970b) Restrictive multiplicative algebras of transformations (in Russian). Izv. Vysš. Učebn. Zaved. Matematika 95 (4)91–102.Google Scholar
Schweizer, B. and Sklar, A. (1961) The algebra of functions II. Mathematische Annalen 143 440–447.CrossRefGoogle Scholar
Schweizer, B. and Sklar, A. (1967) Function systems. Mathematische Annalen 172 1–16.CrossRefGoogle Scholar
Segerberg, K. (1977) A completeness theorem in the modal logic of programs. Notices of the American Mathematical Society 24 A-522.Google Scholar