A Characterisation of Languages on Infinite Alphabets with Nominal Regular Expressions

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.
Type de document :
Communication dans un congrès
Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.193-208, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_14〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01556226
Contributeur : Hal Ifip <>
Soumis le : mardi 4 juillet 2017 - 17:45:47
Dernière modification le : mardi 4 juillet 2017 - 17:47:02
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 02:45:36

Fichier

978-3-642-33475-7_14_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Alexander Kurz, Tomoyuki Suzuki, Emilio Tuosto. A Characterisation of Languages on Infinite Alphabets with Nominal Regular Expressions. Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.193-208, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_14〉. 〈hal-01556226〉

Partager

Métriques

Consultations de la notice

34

Téléchargements de fichiers

17