In this paper, we introduce a computational mode of a tree transducer called a bi-stage transducer and study its properties. We consider a mapping on trees realized by composition of any sequence of top-down transducers and bottom-up transducers, and call such a mapping a multi-phase tree transformation. We think a multi-phase tree transformation is sufficiently powerful. It is shown that in the case of rank-preserving transducers, a multi-phase tree transformation is realized by a bi-stage transducer.

There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, head grammars, and combinatory categorial grammars. It is known that these models of grammars have the same generative power of string languages and fall into the class of mildly context-sensitive grammars. For an automaton, it is known that the class of languages accepted by transfer pushdown automata is exactly the class of linear indexed languages. In this paper, deterministic transfer pushdown automata is introduced. We will show that the language accepted by a deterministic transfer pushdown automaton is generated by an unambiguous spine grammar. Moreover, we will show that there exists an inherently ambiguous language.

We have made an exhaustive computation to establish that 33 comparisons never sort 13 items. The computation was carried out within 10 days by a workstation. Since merge insertion sort [Ford, et al. A tournament problem, Amer. Math. Monthly, vol. 66, (1959)] uses 34 comparisons for sorting 13 items, our result guarantees the optimality of the sorting procedure to sort 13 items as far as the number of comparisons is concerned. The problem has been open for nearly three decades since Mark Wells discovered that 30 comparisons are required to sort 12 items in 1965.

A partitioning automaton which is a modified version of the alternating automaton is introduced. The machine can partition the input string into some blocks and check them universally. The classes of languages accepted by partitioning finite automata and partitioning pushdown automata are shown to be equivalent to the classes of CFL and Aho's indexed languages, respectivery.

Some problems in formal language theory are considered and are shown to be deterministic exponential time complete. They include the problems for a given context-free grammar G, a nondeterministic finite automaton M, a deterministic pushdown automaton MD, of determining whether L(G)L(M), and whether L(MD)L(M). Polynomial time reductions are presented from the pebble game problem, known to be deterministic exponential time complete, to each of these problems.

A maximal l-diameter tree cover of a graph G(V,E) is a spanning subgraph C(V,EC) of G such that each connected component of C is a tree, C contains no path with more than l edges, and adding any edge in EEC to C yields either a path of length l1 or a cycle. For every function f from positive integers to positive integers, the maximal f-diameter tree cover prolem (MDTC(f) problem for short) is to find a maximal f(n)-diameter tree cover of G, given an n-node graph G. In this paper, we give two parallel algorithms for the MDTC(f) problem. The first algorithm can be implemented in time O(TMSP(n,f(n))log2n) using polynomial number of processors on an EREW PRAM, where TMSP(n,f(n) is the time needed to find a maximal set of vertex disjoint paths of length f(n) in a given n-node graph using polynomial number of processors on an EREW PRAM. We then show that if suitable restrictions are imposed on the input graph and/or on the magnitude of f, then TMSP(n,f(n))O(logkn) for some constant k and thus, for such cases, we obtain an NC algorithm for the MDTC(f) problem. The second algorithm runs in time O(n log2n/{f(n)1}) using polynomial number of processors on an EREW PRAM. Thus if f(n)Ω(n/logkn) for some kO, we obtain an NC algorithm for the MDTC(f) problem.

The "relativized Turing machines" are introduced as media executing program schemas. On these machines, it is proved that, for any a, 0a1, there exists an O(na) space and O(n2-a log n) time bounded program schema to sort n elements, and any O(na) space bounded schema to sort n elements requires more than O(n2-a) time. Furthermore, it is shown that there exists a problem which causes a large scale time-space trade off. That is, we show the existence of a problem Q such that there is an O(n2) space and polynomial time bounded schema to compute Q, and there is an O(n log n) space bounded schema to compute Q, and further, any S(n) space bounded schema requires more than exponential time if S(n)n2.