  Automata models for data languages (i.e. languages over infinite alphabets)
often feature either global or local freshness operators. We show that Bollig
et al.'s session automata, which focus on global freshness, are equivalent to
regular nondeterministic nominal automata (RNNA), a natural nominal automaton
model with explicit name binding that has appeared implicitly in the semantics
of nominal Kleene algebra (NKA), an extension of Kleene algebra with name
binding. The expected Kleene theorem for NKA is known to fail in one direction,
i.e. there are nominal languages that can be accepted by an RNNA but are not
definable in NKA; via session automata, we obtain a full Kleene theorem for
RNNAs for an expression language that extends NKA with unscoped name binding.
Based on the equivalence with RNNAs, we then slightly rephrase the known
equivalence checking algorithm for session automata. Reinterpreting the data
language semantics of name binding by unrestricted instead of clean
alpha-equivalence, we obtain a local freshness semantics as a quotient of the
global freshness semantics. Under local freshness semantics, RNNAs turn out to
be equivalent to a natural subclass of Bojanczyk et al.'s nondeterministic
orbit-finite automata. We establish decidability of inclusion under local
freshness by modifying the RNNA-based algorithm; in summary, we obtain a
formalism for local freshness in data languages that is reasonably expressive
and has a decidable inclusion problem.
