Nested words are a restriction of the class of visibly pushdown languages that provide a natural model of runs of programs
with recursive procedure calls. The usual connection between monadic second-order logic (MSO) and automata extends from words
to nested words and gives us a natural notion of regular languages of nested words.
In this paper we look at some well-known aspects of regular languages – their characterization via fixed points, deterministic
and alternating automata for them, and synchronization for defining regular relations – and extend them to nested words. We
show that mu-calculus is as expressive as MSO over finite and infinite nested words, and the equivalence holds, more generally,
for mu-calculus with past modalities evaluated in arbitrary positions in a word, not only in the first position. We introduce
the notion of alternating automata for nested words, show that they are as expressive as the usual automata, and also prove
that Muller automata can be determinized (unlike in the case of visibly pushdown languages). Finally we look at synchronization
over nested words. We show that the usual letter-to-letter synchronization is completely incompatible with nested words (in
the sense that even the weakest form of it leads to an undecidable formalism) and present an alternative form of synchronization
that gives us decidable notions of regular relations.