4 papers
Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
Tomoyuki Yamakami
Nonuniform families of polynomial-size finite automata and pushdown automata respectively have strong connections to nonuniform-NL and nonuniform-LOGCFL. We examine the behaviors o…
The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata
Tomoyuki Yamakami
In various models of one-way pushdown automata, the explicit use of two designated endmarkers on a read-once input tape has proven to be extremely useful for making a conscious, fi…
Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
Tomoyuki Yamakami
Lately, there have been intensive studies on strengths and limitations of nonuniform families of promise decision problems solvable by various types of polynomial-size finite autom…
Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
Tomoyuki Yamakami
We study the computational complexity of finite intersections and finite unions of deterministic context-free (dcf) languages. Earlier, Wotschke [J. Comput. System Sci. 16 (1978) 4…