Abstract
Nominal sets, introduced to Computer Science by Gabbay and Pitts, are useful for modeling computation on data structures built of atoms that can only be compared for equality. In certain contexts it is useful to consider atoms equipped with some nontrivial structure that can be tested in computation. Here, we study nominal sets over atoms equipped with both relational and algebraic structure. Our main result is a representation theorem for orbit-finite nominal sets over such atoms, a generalization of a previously known result for atoms equipped with relational structure only.
This work was supported by the Polish National Science Centre (NCN) grant 2012/07/B/ST6/01497.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bojańczyk, M., Klin, B., Lasota, S.: Automata Theory in Nominal Sets (to appear)
Bojańczyk, M., Klin, B., Lasota, S.: Automata with Group Actions. In: Proc. LICS 2011, pp. 355–364 (2011)
Bojańczyk, M., Lasota, S.: A Machine-independent Characterization of Timed Languages. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 92–103. Springer, Heidelberg (2012)
Bojańczyk, M., Klin, B., Lasota, S., Toruńczyk, S.: Turing Machines with Atoms. In: Proc. LICS 2013, pp. 183–192 (2013)
Fiore, M., Staton, S.: Comparing Operational Models of Name-passing Process Calculi. Inf. Comput. 204, 524–560 (2006)
Gabbay, M.J., Pitts, A.M.: A new approach to abstract syntax with variable binding. Formal Aspects of Computing 13, 341–363 (2002)
Gadducci, F., Miculan, M., Montanari, U.: About Permutation Algebras (Pre)Sheaves and Named Sets. Higher Order Symbol. Comput. 19, 283–304 (2006)
Hodges, W.: Model theory. Cambridge University Press (1993)
Kaminski, M., Francez, N.: Finite-memory Automata. Theor. Comput. Sci. 134, 329–363 (1994)
Pistore, M.: History Dependent Automata. PhD thesis, Università di Pisa, Dipartimento di Informatica. available at University of Pisa as PhD Thesis TD-5/99 (1999)
Pitts, A.M.: Nominal Sets: Names and Symmetry in Computer Science. Cambridge Tracts in Theoretical Computer Science, vol. 57. Cambridge University Press (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Ochremiak, J. (2014). Nominal Sets over Algebraic Atoms. In: Höfner, P., Jipsen, P., Kahl, W., Müller, M.E. (eds) Relational and Algebraic Methods in Computer Science. RAMICS 2014. Lecture Notes in Computer Science, vol 8428. Springer, Cham. https://doi.org/10.1007/978-3-319-06251-8_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-06251-8_26
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06250-1
Online ISBN: 978-3-319-06251-8
eBook Packages: Computer ScienceComputer Science (R0)