
We consider the problem of evaluating in streaming (i.e., in a single
lefttoright pass) a nested word transduction with a limited amount of memory.
A transduction T is said to be height bounded memory (HBM) if it can be
evaluated with a memory that depends only on the size of T and on the height of
the input word. We show that it is decidable in coNPTime for a nested word
transduction defined by a visibly pushdown transducer (VPT), if it is HBM. In
this case, the required amount of memory may depend exponentially on the height
of the word. We exhibit a sufficient, decidable condition for a VPT to be
evaluated with a memory that depends quadratically on the height of the word.
This condition defines a class of transductions that strictly contains all
determinizable VPTs.

Functional transductions realized by twoway transducers (or, equally, by
streaming transducers or MSO transductions) are the natural and standard notion
of "regular" mappings from words to words. It was shown in 2013 that it is
decidable if such a transduction can be implemented by some oneway transducer,
but the given algorithm has nonelementary complexity. We provide an algorithm
of different flavor solving the above question, that has doubly exponential
space complexity. In the special case of sweeping transducers the complexity is
one exponential less. We also show how to construct an equivalent oneway
transducer, whenever it exists, in doubly or triply exponential time, again
depending on whether the input transducer is sweeping or twoway. In the
sweeping case our construction is shown to be optimal.

Rational word languages can be defined by several equivalent means: finite
state automata, rational expressions, finite congruences, or monadic
secondorder (MSO) logic. The robust subclass of aperiodic languages is defined
by: counterfree automata, starfree expressions, aperiodic (finite)
congruences, or firstorder (FO) logic. In particular, their algebraic
characterization by aperiodic congruences allows to decide whether a regular
language is aperiodic. We lift this decidability result to rational
transductions, i.e. wordtoword functions defined by finite state transducers.
In this context, logical and algebraic characterizations have also been
proposed. Our main result is that one can decide if a rational transduction
(given as a transducer) is in a given decidable congruence class. As a
consequence, it is decidable if a rational transduction is aperiodic, and we
show that this problem is PSPACEcomplete.

Functional transductions realized by twoway transducers (equivalently, by
streaming transducers and by MSO transductions) are the natural and standard
notion of "regular" mappings from words to words. It was shown recently
(LICS'13) that it is decidable if such a transduction can be implemented by
some oneway transducer, but the given algorithm has nonelementary complexity.
We provide an algorithm of different flavor solving the above question, that
has double exponential space complexity. We further apply our technique to
decide whether the transduction realized by a twoway transducer can be
implemented by a sweeping transducer, with either known or unknown number of
passes.

Any twoway finite state automaton is equivalent to some oneway finite state
automaton. This wellknown result, shown by Rabin and Scott and independently
by Shepherdson, states that twoway finite state automata (even
nondeterministic) characterize the class of regular languages. It is also
known that this result does not extend to finite string transductions:
(deterministic) twoway finite state transducers strictly extend the expressive
power of (functional) oneway transducers. In particular deterministic twoway
transducers capture exactly the class of MSOtransductions of finite strings.
In this paper, we address the following definability problem: given a function
defined by a twoway finite state transducer, is it definable by a oneway
finite state transducer? By extending Rabin and Scott's proof to transductions,
we show that this problem is decidable. Our procedure builds a oneway
transducer, which is equivalent to the twoway transducer, whenever one exists.

An automaton is universal if it accepts every possible input. We study the
notion of uuniversality, which asserts that the automaton accepts every input
starting with u. Universality and uuniversality are both EXPTIMEhard for
nondeterministic tree automata. We propose efficient antichainbased
techniques to address these problems for visibly pushdown automata operating on
trees. One of our approaches yields algorithms for the universality and
uuniversality of hedge automata.