Abstract
We give a characterisation of languages on infinite alphabets in a variant of nominal regular expressions with permutations (p-NREs). We also introduce automata with fresh name generations and permutations (fp-automata), inspired by history-dependent automata (HDAs) and fresh-register automata. Noteworthy, permutations require to deal with dynamic context-dependent expressions. Finally, we give a Kleene theorem for p-NREs and fp-automata to formally characterise languages on infinite alphabets.
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
Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56(3) (2009)
Bartoletti, M., Degano, P., Ferrari, G.L., Zunino, R.: Hard life with weak binders. Electr. Notes Theor. Comput. Sci. 242(1), 49–72 (2009)
Bojanczyk, M.: Data monoids. In: STACS, pp. 105–116 (2011)
Bojanczyk, M., Klin, B., Lasota, S.: Automata with group actions. In: IEEE Symposium on Logic in Computer Science, pp. 355–364 (2011)
Bouyer, P., Petit, A., Thérien, D.: An algebraic approach to data languages and timed languages. Inf. Comput. 182(2), 137–162 (2003)
Ciancia, V., Tuosto, E.: A novel class of automata for languages on infinite alphabets. Technical Report CS-09-003, Leicester (2009)
Ciancia, V., Venema, Y.: Stream automata are coalgebras. In: 11th International Workshop on Coalgebraic Methods in Computer Science, CMCS 2012 (2012)
Gabbay, M.J., Ciancia, V.: Freshness and Name-Restriction in Sets of Traces with Names. In: Hofmann, M. (ed.) FOSSACS 2011. LNCS, vol. 6604, pp. 365–380. Springer, Heidelberg (2011)
Gabbay, M., Pitts, A.: A new approach to abstract syntax involving binders. In: Symbolic on Logics in Comput Science, pp. 214–224 (1999)
Kaminski, M., Tan, T.: Regular expressions for languages over infinite alphabets. Fundam. Inform. 69(3), 301–318 (2006)
Kaminski, N., Francez, M.: Finite-memory automata. TCS 134(2), 329–363 (1994)
Kozen, D.: On Hoare logic and Kleene algebra with tests. ACM Trans. Comput. Log. 1(1), 60–76 (2000)
Kurz, A., Suzuki, T., Tuosto, E.: On Nominal Regular Languages with Binders. In: Birkedal, L. (ed.) FOSSACS 2012. LNCS, vol. 7213, pp. 255–269. Springer, Heidelberg (2012)
Montanari, U., Pistore, M.: π-Calculus, Structured Coalgebras and Minimal HD-Automata. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, pp. 569–578. Springer, Heidelberg (2000)
Myers, R.: Rational Coalgebraic Machines in Varieties: Languages, Completeness and Automatic Proofs. PhD thesis, Imperial College London (2011)
Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Logic 5(3), 403–435 (2004)
Pistore, M.: History Dependent Automata. PhD thesis, Dipartimento di Informatica, Università di Pisa (1999)
Pouillard, N., Pottier, F.: A fresh look at programming with names and binders. In: Proceeding of the 15th ACM SIGPLAN International Conference on Functional Programming, pp. 217–228 (2010)
Segoufin, L.: Automata and Logics for Words and Trees over an Infinite Alphabet. In: Ésik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 41–57. Springer, Heidelberg (2006)
Shinwell, M., Pitts, A., Gabbay, M.: Freshml: programming with binders made simple. In: Proceedings of the Eighth ACM SIGPLAN International Conference on Functional Programming, pp. 263–274 (2003)
Stirling, C.: Dependency Tree Automata. In: de Alfaro, L. (ed.) FOSSACS 2009. LNCS, vol. 5504, pp. 92–106. Springer, Heidelberg (2009)
Tzevelekos, N.: Fresh-Register Automata. In: Symposium on Principles of Programming Languages, pp. 295–306. ACM (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 IFIP International Federation for Information Processing
About this paper
Cite this paper
Kurz, A., Suzuki, T., Tuosto, E. (2012). A Characterisation of Languages on Infinite Alphabets with Nominal Regular Expressions. In: Baeten, J.C.M., Ball, T., de Boer, F.S. (eds) Theoretical Computer Science. TCS 2012. Lecture Notes in Computer Science, vol 7604. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33475-7_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-33475-7_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33474-0
Online ISBN: 978-3-642-33475-7
eBook Packages: Computer ScienceComputer Science (R0)