Abstract
The category \(\mathbf{Nom}\), of all finitely supported G-sets, called G-nominal sets, where \(G=\mathrm{Perm}_{\mathrm{f}}({\mathbb {D}})\) is the group of all finitary permutations over a countable infinite set \({\mathbb {D}}\), is a subject of interest by both set theorists and computer scientists. The category 01-Nom, of all G-nominal sets equipped with the source and the target operations, was introduced by Pitts. He has shown that this category is isomorphic to the category of sets whose elements have a finite support property with respect to an action of the monoid Cb of name substitutions. The latter category is a coreflective subcategory of the category \(\mathbf{Set}^{Cb}\), of sets with the action of the monoid Cb. For a functorial relation between the categories \(\mathbf{Nom}\) and \(\mathbf{Set}^{Cb}\), we study the existence of the free objects in the category 01-Nom. More precisely, we construct the left adjoint to the forgetful functor from the category of 01-G-nominal sets to the category of G-nominal sets, where G is a suitable subgroup of the group of all permutations over a countable infinite set \({\mathbb {D}}\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Abramsky S, Ghica DR, Murawski AS, Luke Ong CH, Stark IDB (2004) Nominal games and full abstraction for the nu-calculus. In: Proceedings of 19th IEEE Symposium on Logic in Computer Science, pp 150–159
Alexandru A, Ciobanu G (2014) Nominal groups and their homomorphism theorems. Fundam Inform 131(3–4):279–298
Bojanczyk M, Klin B, Lasota S (2011) Automata with group actions, In 26th Symposium on Logic in Computer Science, pp 355–364
Bojanczyk M (2011) Data monoids, In Proceediongs of 28th Symposium on Theoretical Computer Science, pp 105–116
Bojanczyk M (2013) Nominal monoids. Theor Comput Syst 53:194–222
Bojanczyk M, Klin B, Lasota S (2014) Automata theory in nominal sets. Log Methods Comput Sci 10(3):1–44
Ebrahimi MM, Mahmoudi M (2001) The category of \(M\)-sets. Ital J Pure Appl Math 9:123–132
Gabbay MJ, Mathijssen A (2008) One-and-a-halfth-order logic. J Log Comput 18:521–562
Gabbay M, Pitts A (2002) A new approach to abstract syntax with variable binding. Form Asp Comput 13(3–5):341–363
Kilp M, Knauer U, Mikhalev A (2000) Monoids, acts and categories. Walter de Gruyter, Berlin, Newyork
Odersky M (1994) A functional theory of local names. In Conference Record of the 21st Annual ACM Symposium on Principles of Programming Languages, pp 48–59
Petrisan D (2011) Investigations into algebra and topology over nominal sets, Ph. D. Thesis, University of Leicester, Leicester
Pitts A (2003) Nominal logic, a first order theory of names and binding. Inf Comput 186:165–193
Pitts A (2013) Nominal sets, names and symmetry in computer science. Cambridge University Press, Cambridge
Pitts A (2015) Nominal presentations of the cubical sets model of type theory, In Leibniz International Proceedings Informations, pp 202–220
Pitts A, Stark IDB (1993) Observable properties of higher order functions that dynamically create local names, or: whats new?, Mathematical Foundations of Computer Science, In Proceedings of 18th International Symposium. Lecture Notes in Computer Science 711(1993):122–141
Shinwell MR (2005) The fresh approach: functional programming with names and binders, Ph.D. Thesis, University of Cambridge, Computer Laboratory, Cambridge
Shinwell MR, Pitts A (2005) Fresh objective caml user manual, In Technical Report UCAM-CLTR-621, University of Cambridge, Cambridge
Swan A (2016) An algebraic weak factorization system on 01substitution sets: a constructive proof. J Log Anal 8(1):1–35
Turner D, Winskel G (2009) Nominal domain theory for concurrency. Lect Notes Comput Sci 751:546–560
Urban C (2008) Nominal techniques in isabelle/HOL. J Autom Reason 40:327–356
Acknowledgements
We thank the kind hospitality of Malayer University, where this work was completed during our one week stay there. Also, our special thank goes to Professor M.Mehdi Ebrahimi for his very useful kind suggestions. The authors would also like to thank the referee for the insightful comments on the paper.
Funding This study is a part of a Ph.D. thesis and has not funded separately.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
Authors declare that they have no conflict of interest.
Ethical approval
This article does not contain any studies with human participants or animals performed by any of the authors.
Additional information
Communicated by A. Di Nola.
Rights and permissions
About this article
Cite this article
Keshvardoost, K., Mahmoudi, M. Free functor from the category of G-nominal sets to that of 01-G-nominal sets. Soft Comput 22, 3637–3648 (2018). https://doi.org/10.1007/s00500-017-2793-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-017-2793-2