pith. sign in

arxiv: 2606.26685 · v1 · pith:VUMEMRTJnew · submitted 2026-06-25 · 💻 cs.FL · cs.CC

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

Tomoyuki Yamakami (University of Fukui) This is my paper

Pith reviewed 2026-06-26 01:58 UTC · model grok-4.3

classification 💻 cs.FL cs.CC
keywords nonuniform automata familiesstate complexityinput length boundtwo-way finite automatapushdown automataspace-bounded classesKarp-Lipton adviceceiling bound
0
0 comments X

The pith

Size and ceiling bounds significantly impact the complexity of nonuniform finite and pushdown automata families linked to advised space classes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines families of two-way finite automata and pushdown automata whose state complexity and stack-state complexity are restricted, and whose inputs are bounded in length. These families connect directly to space-bounded complexity classes that receive Karp-Lipton style advice of limited size. The author identifies size, meaning the total number of states, and ceiling, meaning the input-length bound, as two factors that produce meaningful changes in the languages recognized. By exploring different values of these parameters, the work shows how the automata families' power varies relative to the advised classes.

Core claim

Size (state complexity) and ceiling (input length bound) are two major factors that have a significant impact on the complexity of finite and pushdown automata families studied in connection with space-bounded classes with Karp-Lipton style advice of limited size when all inputs given to the automata have bounded length. The paper further explores those effects caused by different sizes and ceilings.

What carries the argument

Size (total number of inner states or stack-state complexity) and ceiling (bound on input length) as the two parameters that control the complexity of the automata families.

If this is right

  • Different state counts produce distinct families of languages relative to the advised space classes.
  • Different input-length ceilings modify how the automata families relate to Karp-Lipton advice.
  • Combinations of size and ceiling yield separate complexity behaviors for finite versus pushdown automata.
  • The two parameters refine the nonuniform computation captured by these automata models.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The size-ceiling distinction may separate advice classes more finely than uniform automata alone allow.
  • Specific numerical choices for size and ceiling could yield new characterizations of space classes with limited advice.
  • Analogous size and ceiling effects are likely to appear when the same approach is applied to other automata models.

Load-bearing premise

That restricting the total number of states together with bounding input length produces meaningful changes in the recognized languages relative to advised space classes.

What would settle it

A concrete language family for which changing the state count or the input-length ceiling leaves the recognized languages unchanged relative to the advised space classes.

Figures

Figures reproduced from arXiv: 2606.26685 by Tomoyuki Yamakami (University of Fukui).

Figure 1
Figure 1. Figure 1: Inclusion relationships among nonuniform complexity classes with polynomial ceilings except [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Inclusion relationships among nonuniform complexity classes with exponential ceilings except [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper discusses families of two-way finite automata and pushdown automata with limited state complexity (total inner states) and stack-state complexity (states multiplied by pushable strings), studied in connection with space-bounded complexity classes equipped with Karp-Lipton style advice of limited size when inputs have bounded length. It identifies size ((stack-)state complexity) and ceiling (input length bound) as two major factors with significant impact on the complexity of such nonuniform automata families and states that it further explores the effects caused by different sizes and ceilings.

Significance. The connection between bounded-resource nonuniform automata and advised space classes is a recognized area in automata theory. If the exploration produced explicit characterizations, separations, or examples showing how specific size/ceiling combinations alter recognized languages relative to advised classes, the work could clarify the role of these parameters. The provided text, however, contains no theorems, proofs, concrete examples, or results, preventing any assessment of significance.

major comments (1)
  1. [Abstract] Abstract: The text asserts that size and ceiling 'have a significant impact' and that the paper 'further explore[s] those effects,' yet supplies no definitions of concrete size/ceiling values, no example languages, no comparison of recognized classes, and no indication of what the exploration concludes. This absence leaves the stated purpose of the manuscript unsupported.
minor comments (1)
  1. [Abstract] Abstract: The sentence beginning 'Here, we acknowledge two major factors' repeats the phrase 'finite and pushdown automata families'; rephrasing would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed report and the opportunity to respond. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The text asserts that size and ceiling 'have a significant impact' and that the paper 'further explore[s] those effects,' yet supplies no definitions of concrete size/ceiling values, no example languages, no comparison of recognized classes, and no indication of what the exploration concludes. This absence leaves the stated purpose of the manuscript unsupported.

    Authors: We agree that the abstract, as written, does not provide sufficient concrete detail to support its claims. The manuscript is a short conceptual note that identifies size (state or stack-state complexity) and ceiling (input-length bound) as parameters affecting the power of nonuniform two-way finite and pushdown automata families relative to advised space classes. To address the concern, we will revise the abstract to include brief definitions of these parameters, reference the automata models and advice mechanism under study, and summarize the directional conclusions on how varying sizes and ceilings alter the recognized classes. These changes will appear in the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The provided abstract and description contain no derivations, equations, predictions, or self-citations. The paper explicitly frames its contribution as an exploration of the effects of size (state complexity) and ceiling (input-length bound) on nonuniform automata families, which is a standard premise in automata theory rather than a derived claim. No load-bearing steps reduce by construction to inputs, fitted parameters, or author self-citations, satisfying the criteria for a self-contained exploratory study with no circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are identifiable from the abstract alone; the review is limited to the provided abstract text.

pith-pipeline@v0.9.1-grok · 5679 in / 1131 out tokens · 15780 ms · 2026-06-26T01:58:33.228070+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 23 canonical work pages

  1. [1]

    Axler (2013): Über die Primzahl-Zzählfunktion, die n-te Primzahl und verallgemeinerte Ramanujan- Primzahlen

    C. Axler (2013): Über die Primzahl-Zzählfunktion, die n-te Primzahl und verallgemeinerte Ramanujan- Primzahlen. Doctoral dissertation, Heinrich-Heine-Universität Düsseldorf

    2013

  2. [2]

    Berman & A

    P. Berman & A. Lingas (1977): On complexity of regular languages in terms of finite automata . Technical Report Report 304, Institute of Computer Science, Polish Academy of Science, Warsaw

    1977

  3. [3]

    von Braunmühl, S

    B. von Braunmühl, S. Cook, K. Mehlhorn & R. Verbeek (1983): The recognition of determinsitic CFLs in small time and space. Information and Control 56, pp. 34–51. doi:10.1016/s0019-9958(83)80049-7

    work page doi:10.1016/s0019-9958(83)80049-7 1983

  4. [4]

    S. A. Cook (1971): Characterizations of pushdown machines in terms of time-bounded computers . Journal of the ACM 18, pp. 4–18. doi:10.1145/321623.321625

    work page doi:10.1145/321623.321625 1971

  5. [5]

    Geffert (2012):An alternating hierarchy for finite automata

    V . Geffert (2012):An alternating hierarchy for finite automata. Theoretical Computer Science 445, pp. 1–24. doi:10.1016/j.tcs.2012.04.044

    work page doi:10.1016/j.tcs.2012.04.044 2012

  6. [6]

    Geffert, C

    V . Geffert, C. Mereghetti & G. Pighizzini (2003): Converting two-way nondeterministic automata into sim- pler automata. Theoretical Computer Science 295, pp. 189–203. doi:10.1016/s0304-3975(02)00403-6

    work page doi:10.1016/s0304-3975(02)00403-6 2003

  7. [7]

    Geffert & G

    V . Geffert & G. Pighizzini (2011): Two-way unary automata versus logarithmic space . Information and Computation 209, pp. 1016–1025. doi:10.1016/j.ic.2011.03.003

    work page doi:10.1016/j.ic.2011.03.003 2011

  8. [8]

    Ginsburg & E

    S. Ginsburg & E. H. Spanier (1966): Finite-turn pushdown automata. 10.1137/0304034

    work page doi:10.1137/0304034 1966

  9. [9]

    Hartmanis (1972): On non-determinacy in simple computing devices

    J. Hartmanis (1972): On non-determinacy in simple computing devices . Acta Informatica 1, pp. 336–344. doi:10.1007/bf00289513

    work page doi:10.1007/bf00289513 1972

  10. [10]

    J. E. Hopcroft & J. D. Ullman (1979): Introduction to Automata Theory, Languages, and Computation . Addison-Wesley Publishing Co

    1979

  11. [11]

    C. A. Kapoutsis (2009): Size complexity of two-way finite automata . In: Proc. of the 13th International Conference on Developments in Language Theory (DLT 2009) , Lecture Notes in Computer Science 5583, pp. 47–66. doi:10.1007/978-3-642-02737-6_4

    work page doi:10.1007/978-3-642-02737-6_4 2009

  12. [12]

    C. A. Kapoutsis (2012): Minicomplexity. Journal of Automata, Languages and Combinatorics 17, pp. 205– 224

    2012

  13. [13]

    C. A. Kapoutsis (2014): Two-way automata versus logarithmic space. Theory of Computing Systems 55, pp. 421–447. doi:10.1007/s00224-013-9465-0. 120 Complexity of Nonuniform Automata Families

    work page doi:10.1007/s00224-013-9465-0 2014

  14. [14]

    C. A. Kapoutsis & G. Pighizzini (2015): Two-way automata characterizations of L/poly versus NL. Theory of Computing Systems 56, pp. 662–685. doi:10.1007/s00224-014-9560-x

    work page doi:10.1007/s00224-014-9560-x 2015

  15. [15]

    Rabin & D

    M. Rabin & D. Scott (1959): Finite automata and their decision problems . IBM Journal of Research and Development 3, pp. 114–125. doi:10.1147/rd.32.0114

    work page doi:10.1147/rd.32.0114 1959

  16. [16]

    W. L. Ruzzo (1980): Tree-size bounded alternation . Journal of Computer and System Sciences 21, pp. 218–235. doi:10.1016/0022-0000(80)90036-7

    work page doi:10.1016/0022-0000(80)90036-7 1980

  17. [17]

    W. J. Sakoda & M. Sipser (1978): Nondeterminism and the size of two-way finite automata . In: Proc. of the 10th Annual ACM Symposium on Theory of Computing (STOC 1978) , pp. 275–286. doi:10.1145/800133.804357

    work page doi:10.1145/800133.804357 1978

  18. [18]

    I. H. Sudborough (1978): On the tape complexity of deterministic context-free languages . Journal of the ACM 25, pp. 405–414. doi:10.1145/322077.322083

    work page doi:10.1145/322077.322083 1978

  19. [19]

    Yamakami (2008): Swapping lemmas for regular and context-free languages

    T. Yamakami (2008): Swapping lemmas for regular and context-free languages . Available at arXiv:0808.4122

    Pith/arXiv arXiv 2008

  20. [20]

    Yamakami (2016): Pseudorandom generators against advised context-free languages

    T. Yamakami (2016): Pseudorandom generators against advised context-free languages. Theoretical Com- puter Science 613, pp. 1–27. doi:10.1016/j.tcs.2015.10.026

    work page doi:10.1016/j.tcs.2015.10.026 2016

  21. [21]

    Yamakami (2019): Relativizations of nonuniform quantum finite automata families

    T. Yamakami (2019): Relativizations of nonuniform quantum finite automata families. In: Proc. of the 18th International Conference on Unconventional Computation and Natural Computation (UCNC 2019) , Lecture Notes in Computer Science 11493, Springer, pp. 257–271. doi:10.1007/978-3-030-19311-9_20

    work page doi:10.1007/978-3-030-19311-9_20 2019

  22. [22]

    Yamakami (2019): State complexity characterizations of parameterized degree-bounded graph connectiv- ity, sub-linear space computation, and the linear space hypothesis

    T. Yamakami (2019): State complexity characterizations of parameterized degree-bounded graph connectiv- ity, sub-linear space computation, and the linear space hypothesis . Theoretical Computer Science 798, pp. 2–22. doi:10.1016/j.tcs.2019.09.006

    work page doi:10.1016/j.tcs.2019.09.006 2019

  23. [23]

    Yamakami (2021): Parameterizations of logarithmic-space reductions, stack-state complexity of nonuni- form families of pushdown automata, and a road to the LOGCFL ⊆ LOGDCFL/poly

    T. Yamakami (2021): Parameterizations of logarithmic-space reductions, stack-state complexity of nonuni- form families of pushdown automata, and a road to the LOGCFL ⊆ LOGDCFL/poly. Available at arXiv:2108.12779

    arXiv 2021

  24. [24]

    Yamakami (2022): Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice

    T. Yamakami (2022): Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice. Information and Computation 286, p. 104783. doi:10.1016/j.ic.2021.104783

    work page doi:10.1016/j.ic.2021.104783 2022

  25. [25]

    Yamakami (2023): The 2CNF Boolean formula satisfiability problem and the linear space hypothesis

    T. Yamakami (2023): The 2CNF Boolean formula satisfiability problem and the linear space hypothesis . Journal of Computer and System Sciences 136, pp. 88–112. doi:10.1016/j.jcss.2023.03.001

    work page doi:10.1016/j.jcss.2023.03.001 2023

  26. [26]

    Yamakami (2023): When input integers are given in the unary numeral representation

    T. Yamakami (2023): When input integers are given in the unary numeral representation. In: Proc. of the 24th Italian Conference on Theoretical Computer Science (ICTCS 2023), CEUR Workshop Proceedings 3587, pp. 268–282. Available at https://ceur-ws.org/V ol-3587/5062.pdf

    2023

  27. [27]

    Yamakami (2024): Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters

    T. Yamakami (2024): Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters. In: Proc. of the 18th Annual Conference on Theory and Applications of Models of Computation (TAMC 2024), Lecture Notes in Computer Science 14637, Springer, pp. 14–25. doi:10.1007/978-981-97-2340-9_2

    work page doi:10.1007/978-981-97-2340-9_2 2024

  28. [28]

    Yamakami (2024): Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters

    T. Yamakami (2024): Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters . This is an extended and corrected version of [27]. Available at arXiv:2404.13254

    arXiv 2024

  29. [29]

    Yamakami (2025): Intersection and union hierarchies of deterministic context-free languages and pumping lemmas

    T. Yamakami (2025): Intersection and union hierarchies of deterministic context-free languages and pumping lemmas. Information and Computation 307, p. 105358. doi:10.1016/j.ic.2025.105358

    work page doi:10.1016/j.ic.2025.105358 2025

  30. [30]

    Yamakami (2025): Power of counting by nonuniform families of polynomial-size finite automata

    T. Yamakami (2025): Power of counting by nonuniform families of polynomial-size finite automata . Infor- mation and Computation 307, p. 105372. doi:10.1016/j.ic.2025.105372

    work page doi:10.1016/j.ic.2025.105372 2025

  31. [31]

    Yamakami (2025): What is the most natural generalized pumping lemma beyond regular and context- free languages? In: Proc

    T. Yamakami (2025): What is the most natural generalized pumping lemma beyond regular and context- free languages? In: Proc. of the 26th IFIP WG 1.02 International Conference on Descriptional Complex- ity of Formal Systems (DCFS 2025) , Lecture Notes in Computer Science 15759, Springer, pp. 196–210. doi:10.1007/978-3-031-97100-6_14

    work page doi:10.1007/978-3-031-97100-6_14 2025