Two ways of introducing alternation for context-free grammars and pushdown automata are compared. One is the usual way which combines "states" with alternation [1], [4], [7], and the other is the way used in [6] to define the alternating context-free grammar, i.e., alternation is governed by the variables of the grammar. In this paper the latter way is taken over to define a new type of alternating pushdown automaton by combining the "pushdown symbols" of the pushdown automaton with alternation. We have derived a characterization of the original alternating context-free grammars in terms of such a new type of alternating pushdown automaton without states. It is also shown that, if (non-alternating) states are introduced as an additional feature for this type of pushdown automaton, then the resulting alternating pushdown automaton has exactly the same expressive power as the original alternating pushdown automaton.

This paper investigates a relationship between inkdot and one-pebble for two-dimensional finite automata (2-fa's). Especially we show that (1) alternating inkdot 2-fa's are more powerful than nondeterministic one-pebble 2-fa's, and (2) there is a set accepted by an alternating inkdot 2-fa, but not accepted by any alternating one-pebble 2-fa with only universal states.

This paper introduces a 1-inkdot two-way alternating pushdown automaton which is a two-way alternating pushdown automaton (2apda) with the additional power of marking at most 1 tape-cell on the input (with an inkdot) once. We first investigate a relationship between the accepting powers of sublogarithmically space-bounded 2apda's with and without 1 inkdot, and show, for example, that sublogarithmically space-bounded 2apda's with 1 inkdot are more powerful than those which have no inkdots. We next investigate an alternation hierarchy for sublogarithmically space-bounded 1-inkdot 2apda's, and show that the alternation hierarchy on the first level for 1-inkdot 2apda's holds, and we also show that 1-inkdot two-way nondeterministic pushdown automata using sublogarithmic space are incomparable with 1-inkdot two-way alternating pushdown automata with only universal states using the same space.

This paper investigates the accepting powers of one-way alternatiog finite automata with counters and stack-counters (lafacs's) which operate in realtime. (The difference between counter" and stack-counter" is that the latter can be entered without the contents being changed, but the former cannot.) For each k0 and l0 ((k, l)(0, 0)), let 1AFACS(k, l, real) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters, and let 1UFACS(k, l, real) (1NFACS(k, l, real)) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters which have only universal (existential) states. We first investigate a relationship among the accepting powers of realtime lafacs's with only universal states, with only existential states, and with full alternation, and show, for example, that for each k0 and l0 ((k, l)(0, 0)), 1UFACS(k, l, real) 1NFACS(k, l, real) 1AFACS(k, l, real). We then investigate hierarchical properties based on the number of counters and stack-counters, and show, foe example, that for each k0 and l0 ((k, l)(0, 0)), and each X{U, N}, 1XFACS(k1, l, real)1AFACS(k, l, real)φ. We finally investigate a relationship between counters and stack-counters, and show, for example, that for each k0, l0 and m1, and each X{U, N}, 1XFACS(k, lm, real)1AFACS(k2m1, l, real)φ.

This paper establishes a relationship among the accepting powers of deterministic, nondeterministic, and alternating one-way auxiliary pushdown automata, for any tape bound below n. Some other related results are also presented.

This paper investigates the properties of synchronized alternating one-way multicounter machines (lsamcm's) which operate in real time (lsamcm-real's) and whose leaf-sizes are bounded by a constant or some function of the length of an input. Leaf-size reflects the number of processors which run in parallel in scanning a given input. We first consider the hieracrchies of lsamcm-real's based on the number of counters and constant leaf-sizes. We next show that lsamcm-real's are less powerful than lsamcm's which operate in linear time when the leaf-sizes of these machines are bounded by a function L(n) such that limn[L(n) log n/n]0 and L(n)2.