How Can Size and Ceiling Bounds Affect the Complexity of Nonuniform Automata Families?

2026/06/25 by Tomoyuki Yamakami · 1 voice
Biochemistry, Genetics and Molecular Biology · Computer Science · #Automaton #Bounded function #Ceiling (cloud) #Complexity and Algorithms in Graphs #Computational complexity theory #DNA and Biological Computing #Deterministic context-free grammar #Finite-state machine #Pushdown automaton #Quantum finite automata #cs.CC #cs.FL #semigroups and automata theory

paper · pdf · open access · doi:10.4204/eptcs.446.7

published in Electronic Proceedings in Theoretical Computer Science 446, 105-120 (Open Publishing Association)

openalex publication_date 2026/06/25 · arxiv published 2026/06/25 · arxiv updated 2026/06/25 · openalex created_date 2026/06/28 · openalex updated_date 2026/08/05

Abstract

In the past literature, families of two-way finite automata and pushdown automata having limited state complexity (i.e., the total number of inner states) and stack-state complexity (i.e., the total number of inner states multiplied by the total number of strings "pushable" to a stack), have been studied in direct connection to (mainstream) space-bounded complexity classes equipped with Karp-Lipton style advice of limited size when all inputs given to the automata have bounded length. Here, we acknowledge two major factors -- size and ceiling -- of such families, which have a significant impact on the complexity of finite and pushdown automata families, where the "size" refers to (stack-)state complexity and the "ceiling" refers to an input's length bound. In this line of study, we further explore those effects caused by different sizes and ceilings.

Citations

• Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
• When Input Integers are Given in the Unary Numeral Representation
• Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
• Parameterizations of Logarithmic-Space Reductions, Stack-State Complexity of Nonuniform Families of Pushdown Automata, and a Road to the LOGCFL⊆LOGDCFL/poly Question
• Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
• Pseudorandom Generators Against Advised Context-Free Languages
• Swapping Lemmas for Regular and Context-Free Languages
• Finite Automata and Their Decision Problems

Discussions

• Tomoyuki Yamakami (University of Fukui): How Can Size and Ceiling Bounds Affect the Complexity of Nonuniform Automata Families? https://arxiv.org/abs/2606.26685 https://arxiv.org/pdf/2606.26685 https: [bsky, 0 points, 0 comments]

Related

• Parameterizations of Logarithmic-Space Reductions, Stack-State Complexity of Nonuniform Families of Pushdown Automata, and a Road to the LOGCFL⊆LOGDCFL/poly Question
• Exact descriptional complexity of determinization of input-driven pushdown automata
• Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
• Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
• Complexity of Membership and Non-Emptiness Problems in Unbounded Memory Automata