06085041

a

06085041 Kurz, Alexander Suzuki, Tomoyuki Tuosto, Emilio A characterisation of languages on infinite alphabets with nominal regular expressions. Baeten, Jos C. M. (ed.) et al., Theoretical computer science. 7th IFIP TC 1/WG 2.2 international conference, TCS 2012, Amsterdam, The Netherlands, September 26--28, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-33474-0/pbk). Lecture Notes in Computer Science 7604, 193-208 (2012). 2012 Berlin: Springer EN

doi:10.1007/978-3-642-33475-7_14

Summary: 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.