Towards Nominal Formal Languages
  We introduce formal languages over infinite alphabets where words may contain binders. We define the notions of nominal language, nominal monoid, and nominal regular expressions. Moreover, we extend history-dependent automata (HD-automata) by adding stack, and study the recognisability of nominal languages. 
Alexander Kurz and Tomoyuki Suzuki and Emilio Tuosto
cs.FL