Paper Info
Title
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.
Year
DOI
Venue
2012
10.1007/978-3-642-33475-7_14
IFIP TCS
Keywords
Field
DocType
history-dependent automaton,characterise language,nominal regular expression,infinite alphabet,fresh-register automaton,kleene theorem,dynamic context-dependent expression,fresh name generation
Discrete mathematics,Combinatorics,Regular expression,Deterministic automaton,Expression (mathematics),Permutation,Automaton,Tree automaton,Mathematics
Conference
Citations 
PageRank 
References 
2
0.40
19
Authors
3
Name
Order
Citations
PageRank
Alexander Kurz120415.76
Tomoyuki Suzuki2151.05
Emilio Tuosto349942.62