  Logics and automata models for languages over infinite alphabets, such as
Freeze LTL and register automata, serve the verification of processes or
documents with data. They relate tightly to formalisms over nominal sets, such
as nondetermininistic orbit-finite automata (NOFAs), where names play the role
of data. Reasoning problems in such formalisms tend to be computationally hard.
Name-binding nominal automata models such as regular nondeterministic nominal
automata (RNNAs) have been shown to be computationally more tractable. In the
present paper, we introduce a linear-time fixpoint logic Bar-muTL for finite
words over an infinite alphabet, which features full negation and freeze
quantification via name binding. We show by a nontrivial reduction to extended
regular nondeterministic nominal automata that even though Bar-muTL allows
unrestricted nondeterminism and unboundedly many registers, model checking
Bar-muTL over RNNAs and satisfiability checking both have elementary
complexity. For example, model checking is in 2ExpSpace, more precisely in
parametrized ExpSpace, effectively with the number of registers as the
parameter.
