Hostname: page-component-8448b6f56d-42gr6 Total loading time: 0 Render date: 2024-04-18T14:09:38.940Z Has data issue: false hasContentIssue false
  • English
  • Français

On universal algebra over nominal sets

Published online by Cambridge University Press:  25 March 2010

ALEXANDER KURZ  and
DANIELA PETRIŞAN
ALEXANDER KURZ
Affiliation:
Department of Computer Science, University of Leicester, UK Email: kurz@mcs.le.ac.uk; petrisan@mcs.le.ac.uk
DANIELA PETRIŞAN
Affiliation:
Department of Computer Science, University of Leicester, UK Email: kurz@mcs.le.ac.uk; petrisan@mcs.le.ac.uk
Get access Rights & Permissions [Opens in a new window]

Abstract

We investigate universal algebra over the category Nom of nominal sets. Using the fact that Nom is a full reflective subcategory of a monadic category, we obtain an HSP-like theorem for algebras over nominal sets. We isolate a ‘uniform’ fragment of our equational logic, which corresponds to the nominal logics present in the literature. We give semantically invariant translations of theories for nominal algebra and NEL into ‘uniform’ theories, and systematically prove HSP theorems for models of these theories.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 20 , Special Issue 2: Domains , April 2010 , pp. 285 - 318
Copyright
Copyright © Cambridge University Press 2010

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

Adámek, J., Herrlich, H. and Strecker, G. E. (1990) Abstract and Concrete Categories, John Wiley and Sons.Google Scholar
Adámek, J. and Rosický, J. (1994) Locally Presentable and Accessible Categories, Cambridge University Press.CrossRefGoogle Scholar
Adámek, J., Rosický, J. and Vitale, E. M. (draft) Algebraic Theories: a Categorical Introduction to General Algebra. Available at http://www.iti.cs.tu-bs.de/~adamek/algebraic.theories.pdf.Google Scholar
Bonsangue, M. and Kurz, A. (2007) Pi-calculus in logical form. 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007) 303–312.Google Scholar
Bonsangue, M. M. and Kurz, A. (2006) Presenting functors by operations and equations. In: FoSSaCS. Springer-Verlag Lecture Notes in Computer Science 3921.Google Scholar
Borceux, F. (1994) Handbook of Categorical Algebra, Cambridge University Press.Google Scholar
Clouston, R. and Pitts, A. (2007) Nominal equational logic. In: Computation, Meaning and Logic: Articles dedicated to Gordon Plotkin. Electronic Notes in Theoretical Computer Science 172.Google Scholar
Fiore, M., Plotkin, G. and Turi, D. (1999) Abstract syntax and variable binding. Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science 193–202.Google Scholar
Fiore, M. P. and Hur, C.-K. (2008) Term equational systems and logics (extended abstract). Electronic Notes in Theoretical Computer Science 218 171–192.Google Scholar
Gabbay, M. (2008) Nominal algebra and the HSP theorem. Journal of Logic and Computation 19 (2)341–367.Google Scholar
Gabbay, M. and Pitts, A. (1999) A new approach to abstract syntax involving binders. Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science (LICS'99) 214–224.Google Scholar
Gabbay, M. J. and Mathijssen, A. (2009) Nominal (universal) algebra: equational logic with names and binding. Journal of Logic and Computation (in press).Google Scholar
Johnstone, P. T. (2002) Sketches of an Elephant: A Topos Theory Compendium, vol. 1, Oxford Logic Guides 43, Oxford University Press.Google Scholar
Kurz, A. and Petrişan, D. (2008) Functorial coalgebraic logic: The case of many-sorted varieties. In: Adámek, J. and Kupke, C. (eds.) Proceedings of the Ninth Workshop on Coalgebraic Methods in Computer Science (CMCS 2008). Electronic Notes in Theoretical Computer Science 203 (5)175–194CrossRefGoogle Scholar
Kurz, A. and Rosický, J. (2006) Strongly complete logics for coalgebras (submitted).Google Scholar
Mac Lane, S. and Moerdijk, I. (1994) Sheaves in Geometry and Logic: A First Introduction to Topos Theory (Universitext), Springer-Verlag.Google Scholar
Stark, I. (2008) Free-algebra models for the pi -calculus. Theoretical Computer Science 390 (2-3)248–270.CrossRefGoogle Scholar