How Can Size and Ceiling Bounds Affect the Complexity of Nonuniform Automata Families?
Tomoyuki Yamakami · 2026
Read How Can Size and Ceiling Bounds Affect the Complexity of Nonuniform Automata Families? by Tomoyuki Yamakami (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26685.txt.
Introduction
Tomoyuki Yamakami examines how size and ceiling bounds shape the power of nonuniform automaton families. A nonuniform family uses a different automaton for each input length. Two measures govern such families: size, the count of internal states, and ceiling, the maximum input length allowed. Similar measures for pushdown automata include stack contents. These families connect to space-bounded complexity classes with limited advice.
Advice is extra information given to a machine for each input length. Earlier work linked small-state families to complexity classes with short advice. Yamakami explores how varying the size and ceiling bounds changes what the families can compute. The analysis separates the roles of the two bounds. It clarifies which restrictions truly weaken the machines and which merely repackage their power.
Catalog record
| CREATOR | Tomoyuki Yamakami |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.26685
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
How Can Size and Ceiling Bounds Affect the Complexity of Nonuniform Automata Families? Tomoyuki Yamakami 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. Keywords. nonuniform state complexity, promise problem, stack-state complexity, size, ceiling, advice 1 Background and Challenges of This Work In 1959, Rabin and Scott [ 16 ] published a paper claiming that, for each fixed positive integer n , each one-way nondeterministic finite automaton (or 1nfa, for short) N_{n} of n inner states can be converted into another computationally equivalent 1 1 1 Two machines are computationally equivalent if their outcomes coincide on every input. one-way deterministic finite automaton (or 1dfa) M_{n} of 2^{n} inner states. The total number of inner states used to describe each finite automaton, known as the state complexity , has served as a useful complexity measure indicating the “size” of the finite automaton. In other words, the result of Rabin and Scott asserts that every 1nfa of size n can be simulated on an appropriate 1dfa of size at most 2^{n} . After the publication of their paper, researchers have been wondering if the value 2^{n} can be significantly reduced. As for the simulation of an n -size 2nfa N_{n} on an n^{O(1)} -size 2dfa M_{n} , where 2nfa and 2dfa are respectively the two-way versions of 1nfa and 1dfa, Berman and Lingus [ 3 ] reported an intimate connection to the \mathrm{L}=?\mathrm{NL} question, where \mathrm{L} is the deterministic log-space complexity class and \mathrm{NL} is its nondeterministic variant. In 1978, Sakoda and Sipser [ 18 ] studied collectively (nonuniform) families of finite automata M_{n} of n^{O(1)} size (i.e., polynomial size) in order to solve given families of promise (decision) problems 2 2 2 A promise (decision) problem is a pair of disjoint sets over the same alphabet. (L_{n}^{(+)},L_{n}^{(-)}) indexed by natural numbers n . As a concrete example, assuming a suitable binary encoding \langle G\rangle of a graph G , let us consider the family {\cal L}_{bipartite}=\{(L_{n}^{(+)},L_{n}^{(-)})\}_{n\in{\rm Nature}} of promise problems defined by L_{n}^{(+)}=\{x\in\{0,1\}^{*}\mid|x|\leq 2^{n},x=\langle G\rangle,\text{ $G$ is a bipartite graph}\} and L_{n}^{(-)}=\{0,1\}^{*}-L_{n}^{(+)} for each index n . This family {\cal L}_{bipartite} can be solved by a suitable family \{N_{n}\}_{n\in{\rm Nature}} of polynomial-size 2nfa’s. A series of followup studies has been conducted intensively in the past literature [ 6 , 12 , 13 , 14 , 15 , 23 , 25 , 22 , 24 , 31 ] . The focal object of Sakoda and Sipser is actually the nonuniform families of “polynomial-size” finite automata. Here, the “size” describing a finite automaton signifies the computational complexity of this automaton, more akin to the (work) space complexity measure of a Turing machine equipped with an external information source known as “advice”. This association contributes, as a hidden gem, to the study of automata theory by way of (mainstream) computational complexity theory. As for pushdown automata families, in contrast, the “size” refers to its stack-state complexity , which indicates the total number of inner states multiplied by the total number of “pushable” strings [ 24 , 31 ] because stack symbols are translatable in some sense to inner states. The study of those “families” of finite and pushdown automata takes a similar advantage to that of (nonuniform) Boolean circuit families; however, a major difference also lies in the point that, whereas each circuit appearing in a Boolean circuit family is limited to particular input size, each finite automaton in an automata family is not in general, as the previous example {\cal L}_{bipartite} shows. Therefore, it is sometimes beneficial to cap an appropriate upper bound on the length of input strings fed into underlying finite and pushdown automata. Such a cap is known as a “ceiling” and has played a key role in [ 3 , 14 , 18 ] , in which, for instance, the standard log-space complexity classes, \mathrm{L} and \mathrm{NL} , supplemented by polynomial-size advice can be expressed in terms of collections of finite automata families when input strings are all limited to having polynomial ceiling (i.e., polynomially bounded length). Through those studies, there are, in essence, two major factors— size and ceiling —which significantly affect the overall performance of each automata family. Those factors may directly relate to the complexity measures of work space and advice size used in standard complexity theory. The purpose of this work is therefore to further explore how such factors contribute to the shift of the overall complexity of nonuniform automata families. Associated with those factors, the aforementioned initial studies of automata families have been expanded into further directions. As natural extensions of polynomial-size automata families, for instance, Kapoutsis [ 12 , 13 ] studied the behaviors of finite automata families of exponential (i.e., 2^{n^{O(1)}} ) size . As for ceiling bounds, Kapoutsis also considered promise problem families of superpolynomial ceilings . When ceiling bounds of polynomial-size automata families are expanded from polynomials to, e.g., exponentials, they in turn relate to loglog-space complexity classes supported by polylog-size advice [ 14 ] . Unfortunately, we still lack a whole picture depicting the effects of the combinations of sizes and ceilings for nonuniform families of finite and pushdown automata. The rest of this work is organized as follows. The basic notions and various notations will be explained in Section 2 . The effects of polynomial ceilings will be discussed in Section 4 and those of exponential ceilings will be studied in Section 5 . From additional viewpoints, polynomial-size and superpolynomial-size automata will be examined separately in Sections 4.1 and 4.2 as well as Section 5 . All omitted proofs will be included in a forthcoming complete version of this paper. 2 Foundations of This Work We will explain the basic notions and notation that the reader needs to read through the rest of this work. 2.1 Sets, Numbers, and Alphabets We use the standard notations, including {\rm Nature} (natural number class with 0 ). For positive integers, we write {\rm Nature}^{+} for {\rm Nature}-\{0\} . For two integers m,n with m\leq n , [m,n]_{\mathbb{Z}} denotes the integer interval composed of all integers between m and n in comparison with the real interval [r_{1},r_{2}] . We often abbreviate as [n] the integer interval [1,n]_{\mathbb{Z}} for any number n\in{\rm Nature}^{+} . In this work, polynomials take nonnegative integer coefficients and logarithms are all taken to the base 2 . For convenience, we further set \log{0} to be 0 . Given a set Q , {\cal P}(Q) denotes the power set of Q . The notation \lambda denotes the empty