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.

翻译：多项式规模的有限自动机族与下推自动机族分别与非均匀NL和非均匀LOGCFL具有紧密联系。本文研究了由这类自动机族在操作多个计数器时产生的无歧义与共非确定性计算行为，其中计数器指仅使用单一非底部符号的栈。作为直接推论，当所有有效实例被限制为多项式长度字符串或一元字符串时，我们获得了由有限自动机族和下推自动机族可解的承诺问题族所对应的复杂性类的多种塌缩结果。证明的关键技术要素在于对同时操作多个计数器的有限自动机与下推自动机各计算图可达顶点的归纳计数。