Towards Nominal Formal Languages

2011/02/15 by Kurz, Alexander, Suzuki, Tomoyuki, Tuosto, Emilio
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1102.3174

Abstract

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.

Related

• Nominal Regular Expressions for Languages over Infinite Alphabets. Extended Abstract
• A decidable class of (nominal) omega-regular languages over an infinite alphabet
• Alternating Nominal Automata with Name Allocation
• Nominal Automata with Name Binding
• Graded Monads in the Semantics of Nominal Automata