This paper discusses the decidability of node query preservation problems for tree transducers. We assume a transformation given by a deterministic linear top-down data tree transducer (abbreviated as DLTV) and an n-ary query based on runs of a tree automaton. We say that a DLTV Tr strongly preserves a query Q if there is a query Q' such that for every tree t, the answer set of Q' for Tr(t) is equal to the answer set of Q for t. We also say that Tr weakly preserves Q if there is a query Q' such that for every t, the answer set of Q' for Tr(t) includes the answer set of Q for t. We show that the weak preservation problem is coNP-complete and the strong preservation problem is in 2-EXPTIME. We also show that the problems are decidable when a given transducer is a functional extended linear top-down data tree transducer with regular look-ahead, which is a more expressive transducer than DLTV.

In this paper we introduce a bottom-up pushdown tree transducer (b-PDTT) which is a bottom-up tree transducer with pushdown storage (where the pushdown storage stores the trees) and may be considered as a dual concept of the top-down pushdown tree transducer (t-PDTT). After proving some fundamental properties of b-PDTT, for example, any b-PDTT can be realized by a linear stack with single state and converted into G-type normal form which corresponds to Greibach normal form in a context-free grammar, and so on, we compare the translational capability of a b-PDTT with that of a t-PDTT.

In this paper, some properties of domain tree languages of top-down pushdown tree transducers (domain(t-PDTT) or t-PDTTD) are shown. It is shown that (1) for any L1, L2 in context-free language (CFL), L1L2yielde(t-PDTTD) (where yielde is an extended yield), (2) yielde(t-PDTTε0DF) is closed under homomorphisms, where t-PDTTε0 is a t-PDTT which can not proceed generations after reading a constant symbol σ and t-PDTTε0DF denotes a domain tree language of t-PDTTε0 with a final state translation, and (3) yielde(t-PDTTε0DF) is the class of recursively enumerable languages, and consequently yielde(t-PDTTD) is the class of recursively enumerable languages.

Some kind of practical problems such as security verification of cryptographic protocols can be described as a problem to accomplish a given purpose by using limited operations and limited materials only. To model such problems in a natural way, unification problems under constrained substitutions have been proposed. This paper is a collection of results on the decidability and the computational complexity of a syntactic unification problem under constrained substitutions. A number of decidable, undecidable, tractable and intractable results of the problem are presented. Since a unification problem under constrained substitutions can be regarded as an order-sorted unification problem with term declarations such that the number of sorts is only one, the results presented in this paper also indicate how the intractability of order-sorted unification problems is reduced by restecting the number of sorts to one.

String grammars (languages) have been extensively studied from the 60's. On the other hand, the transformational grammar, proposed by N. Chomsky, contains the transformation from the set of derivation trees of a context-free language to the surface set. Here the grammar regarded a tree as an input sentence to some transducer. After that from the second half of 60's, the studies of acceptors, transducers, and so on, whose inputs are trees, have been done extensively. Recently pushdown tree automata were introduced, and their fundamental and some other various properties were investigated [12],[13],[22]-[26]. Furthermore a top-down pushdown tree transducer (t-PDTT for short), which is an extension of a top-down pushdown automaton (t-PDTA for short), was introduced and its fundamental properties were investigated [27]. In this paper we focus on t-PDTT, linear t-PDTT, t-FST (top-down finite state transducer), and t-PDTA. The main subjects discussed here are as follows: (1) the class of domain/surface tree languages of t-PDTT properly contains the class of tree languages accepted by t-PDTA, (2) the class of domain/surface tree languages of linear t-PDTT's coincides with the class of tree languages accepted by t-PDTA's, (3) the class of tree languages accepted by t-PDTA's properly contains the class of surface tree languages of t-FST's.

Finite state translation systems (fsts') are a widely studied computational model in the area of tree automata theory. In this paper, the string generating capacities of fsts' and their subclasses are studied. First, it is shown that the class of string languages generated by deterministic fsts' equals to that of parallel multiple context-free grammars, which are an extension of context-free grammars. As a corollary, it can be concluded that the recognition problem for a deterministic fsts is solvable in O(ne1)-time, where n is the length of an input word and e is a constant called the degree of the deterministic fsts'. In contrast to the latter fact, it is also shown that nondeterministic monadic fsts' with state-bound 2 can generate an NP-complete language.

String grammars (languages) have been extensively studied from 60's. On the other hand, the transformational grammar, proposed by Chomsky, contains the transformation from the set of derivation trees of context-free language to the surface set. And the grammar regarded a tree as an input sentence to some transducer. After that from latter half of 60's, the studies of acceptor, transducer, and so on, whose input is a tree, have been done extensively. In this paper we propose, as a model, a new type of transducer which translates trees into trees and investigate its fundamental properties. The model proposed here is the pushdown tree transducer (for shortly PDTT) that is an extension of the finite state tree transducer discussed by J. W. Thacher, W. C. Rounds, J. Engelfriet, and so on. The main subjects discussed here (we consider only top-down case (t-PDTT)), are as follows: (1) final state t-PDTT translation is equivalent to empty stack t-PDTT translation and vice versa, (2) for any t-PDTT, a single state t-PDTT which is equivalent to it always exists, (3) as a standard form the symmetric stack form t-PDTT is proposed and based on this, it is shown that any single state t-PDTT can be always converted into a linear stack t-PDTT, and so on.