We consider the problem of evaluating in streaming (i.e., in a single
left-to-right 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
Functional transductions realized by two-way 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 one-way transducer,
but the given algorithm has non-elementary 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 one-way
transducer, whenever it exists, in doubly or triply exponential time, again
depending on whether the input transducer is sweeping or two-way. 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
second-order (MSO) logic. The robust subclass of aperiodic languages is defined
by: counter-free automata, star-free expressions, aperiodic (finite)
congruences, or first-order (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. word-to-word 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 PSPACE-complete.
Functional transductions realized by two-way 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 one-way transducer, but the given algorithm has non-elementary 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 two-way transducer can be
implemented by a sweeping transducer, with either known or unknown number of
Any two-way finite state automaton is equivalent to some one-way finite state
automaton. This well-known result, shown by Rabin and Scott and independently
by Shepherdson, states that two-way finite state automata (even
non-deterministic) characterize the class of regular languages. It is also
known that this result does not extend to finite string transductions:
(deterministic) two-way finite state transducers strictly extend the expressive
power of (functional) one-way transducers. In particular deterministic two-way
transducers capture exactly the class of MSO-transductions of finite strings.
In this paper, we address the following definability problem: given a function
defined by a two-way finite state transducer, is it definable by a one-way
finite state transducer? By extending Rabin and Scott's proof to transductions,
we show that this problem is decidable. Our procedure builds a one-way
transducer, which is equivalent to the two-way transducer, whenever one exists.
An automaton is universal if it accepts every possible input. We study the
notion of u-universality, which asserts that the automaton accepts every input
starting with u. Universality and u-universality are both EXPTIME-hard for
non-deterministic tree automata. We propose efficient antichain-based
techniques to address these problems for visibly pushdown automata operating on
trees. One of our approaches yields algorithms for the universality and
u-universality of hedge automata.