Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters

Abstract

Nonuniform families of polynomial-size finite automata and pushdown automata respectively have strong connections to nonuniform-NL and nonuniform-LOGCFL. We examine the behaviors of unambiguous and co-nondeterministic computations produced by such families of automata operating multiple counters, where a counter is a stack using only a single non-bottom symbol. As immediate consequences, we obtain various collapses of the complexity classes of families of promise problems solvable by finite and pushdown automata families when all valid instances are limited to either polynomially long strings or unary strings. A key technical ingredient of our proofs is an inductive counting of reachable vertices of each computation graph of finite and pushdown automata that operate multiple counters simultaneously.

(A4, 10pt, 20 pages, 3 figures) A preliminary report appeared in the Proceedings of the 18th Annual Conference on Theory and Applications of Models of Computation (TAMC 2024), Hong Kong, China, May 13-15, 2024, Lecture Notes in Computer Science, vol. 14637, pp. 14--25, Springer, 2024