Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01556226
Contributor : Hal Ifip <>
Submitted on : Tuesday, July 4, 2017 - 5:45:47 PM
Last modification on : Tuesday, July 4, 2017 - 5:47:02 PM
Long-term archiving on: : Friday, December 15, 2017 - 2:45:36 AM

File

978-3-642-33475-7_14_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Alexander Kurz, Tomoyuki Suzuki, Emilio Tuosto. A Characterisation of Languages on Infinite Alphabets with Nominal Regular Expressions. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. pp.193-208, ⟨10.1007/978-3-642-33475-7_14⟩. ⟨hal-01556226⟩

Share

Metrics

Record views

99

Files downloads

199