Two kinds of automata are introduced, for recognising regular and context-free nominal languages. We compare their expressive power with that of analogous proposals in the literature. Some properties of our languages are proved, in particular that emptiness of a contextfree nominal language L is decidable, and that the intersection of L with a regular nominal language is still context-free. This paves the way for model-checking systems against access control properties in the nominal case, which is our main objective.
展开▼