betaFeedback

WorksComputer Science

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

Abstract

In the past literature, families of two-way finite automata and pushdown automata having limited resource-bounded complexity 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. We acknowledge three major factors–size, ceiling, and time–of such families, which have a significant impact on the computational/descriptional complexity of finite and pushdown automata families, where the "size" refers to the (stack-)state complexity, the "ceiling" refers to the maximum input length, and the "time" refers to the execution time of underlying automata. In this line of study, we further explore these effects caused by different sizes and ceilings. We exploit automata-based reducibility and translatability to space-bounded advised Turing machines and auxiliary automata.

Nonuniform Automata Families: Old and New Issues

Let us quickly review necessary background materials and overview the main contribution of this work.

Background and Challenges of This Work

In 1959, Rabin and Scott [17] published a paper claiming that, for each fixed positive integer nn, each one-way nondeterministic finite automaton (or 1nfa, for short) NnN_n of nn inner states can be converted into another computationally equivalent1 one-way deterministic finite automaton (or 1dfa) MnM_n of 2n2^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 descriptional complexity measure for the “size” of the finite automaton, which expresses how large a machine’s inner program is. The result of Rabin and Scott can be rephrased in such a way that every 1nfa of size nn can be simulated on an appropriate 1dfa of size at most 2n2^n. This result has provided a measurable complexity comparison between two types of automata. An increase of the state complexity by this simulation expresses the “cost” of converting one type of automaton to another type of computationally equivalent automaton. This notion has been used for scaling the relative complexity of these two types of automata. After the publication of their paper, researchers have been wondering if the value 2n2^n can be significantly reduced.

As for the two-way versions of 1nfa and 1dfa, called 2nfa and 2dfa, Berman and Lingus [2] reported that a simulation between an nn-size 2nfa NnN_n on an appropriate 2dfa MnM_n of nO(1)n^{O(1)} inner states has an intimate connection to the L=?NLL = ?NL question, where LL is the deterministic log-space complexity class and NLNL is its nondeterministic variant. Limiting input alphabet does not seem to help because the best known simulation of an nn-size “unary” 2nfa requires at most nO(log⁡n)n^{O(\log n)} inner states on an appropriate 2dfa [8].

In 1978, Sakoda and Sipser [19] studied a computational model of nonuniform families of finite automata MnM_n in order to solve given families of promise (decision) problems2 (Ln(+),Ln(−))(L_n^{(+)},L_n^{(-)}), indexed by natural numbers nn. At this point, we take a quick look at a simple, concrete example. Assuming a suitable binary encoding ⟨G⟩\langle G\rangle of a graph GG, let us consider the family Lbipartite={(Ln(+),Ln(−))}n∈N\mathcal{L}_{bipartite}=\{(L_n^{(+)},L_n^{(-)})\}_{n\in\mathbb{N}} of promise problems defined by Ln(+)={x∈{0,1}∗∣∣x∣≤2n,x=⟨G⟩, G is a bipartite graph}L_n^{(+)}=\{x\in\{0,1\}^* \mid|x|\leq2^n,x=\langle G\rangle,\ G\text{ is a bipartite graph}\} and Ln(−)={0,1}∗−Ln(+)L_n^{(-)}=\{0,1\}^*-L_n^{(+)} for each index nn. This family Lbipartite\mathcal{L}_{bipartite} can be solved by a suitable family {Nn}n∈N\{N_n\}_{n\in\mathbb{N}} of 2nfa2\mathrm{nfa}’s using nO(1)n^{O(1)} inner states. After the paper of Sakoda and Sipser, a series of followup studies has been conducted intensively in the past literature [7, 13, 14, 15, 16, 25, 26, 27, 29, 32].

Unlike single finite automata, the study of nonuniform automata families has demanded different kinds of insight. These “families” of finite automata takes a similar advantage to (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 generally not, as in the previous example of {Nn}n∈N\{N_n\}_{n\in\mathbb{N}} for Lbipartite\mathcal{L}_{bipartite}.

The focal object of Sakoda and Sipser is in fact the nonuniform families of “polynomial-size” finite automata. Here, the “size” of a finite automaton signifies the descriptional 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.

Sakoda and Sipser invented the now widely-used notations of 2D2\mathrm{D} and 2N2\mathrm{N} to treat collectively promise problem families solvable by families of polynomial-size 2dfa2\mathrm{dfa}’s and of polynomial-size 2nfa2\mathrm{nfa}’s, respectively. The one-way analogues of 2D2\mathrm{D} and 2N2\mathrm{N} are denoted respectively by 1D1\mathrm{D} and 1N1\mathrm{N}. The aforementioned family Lbipartite\mathcal{L}_{bipartite} belongs to 2N2\mathrm{N} but it is not clear whether Lbipartite\mathcal{L}_{bipartite} falls in 2D2\mathrm{D}. Sakoda and Sipser asked a fundamental question of whether those two nonuniform complexity classes coincide.

In recent literature, the study of nonuniform automata families has been significantly expanded to other types of automata, including unambiguous, co-nondeterministic, probabilistic, alternating, counting, and quantum automata [7, 13, 14, 27]. The nonuniform complexity classes 1BP1\mathrm{BP} and 1P1\mathrm{P}, for instance, stand for the classes of all families of promise problems solvable by families of polynomial-size one-way probabilistic finite automata with bounded-error and unbounded-error probabilities, respectively. Fig. 1 illustrates some of the relationships among the complexity classes induced by those nonuniform automata families. Nonuniform counting complexity classes were further studied in [32].

As a natural extension of finite automata families, Yamakami [29, 32, 34, 35] studied the computational complexity of pushdown automata families. For pushdown automata families, the “size” refers to its stack-state complexity, which indicates the total number of inner states multiplied by the total number of “pushable” strings [29, 30, 32]. Hence, for pushdown automata families, the term of “polynomial-size” refers to the polynomial stack-state complexity in place of the polynomial state complexity. Similar to the previous notations of Sakoda and Sipser, the notations of 2DPD2\mathrm{DPD} and 2NPD2\mathrm{NPD} (as well as 1DPD1\mathrm{DPD} and 1NPD1\mathrm{NPD}) were introduced in [29, 32] with the use of polynomial-size pushdown automata families. In the course of study on finite and pushdown automata families, a multi-counter extension was further sought and studied intensively [34, 35].

From a different perspective, Kapoutsis [13, 14] analyzed the behaviors of finite automata families of exponential (i.e., 2nO(1)2^{n^{O(1)}}) size. To express families of promise problems solvable by exponential-size automata families, he introduced the special notations of 22D2^{2\mathrm{D}} and 22N2^{2\mathrm{N}} (resp., 21D2^{1\mathrm{D}} and 21N2^{1\mathrm{N}}), compared to 2D2\mathrm{D} and 2N2\mathrm{N} (resp., 1D1\mathrm{D} and 1N1\mathrm{N}), respectively. With these notations, the aforementioned state complexity result of Rabin and Scott can be rephrased as 1N⊆21D1\mathrm{N}\subseteq2^{1\mathrm{D}}. Similarly to the 2\mathrm{D}≠2\mathrm{N} question of Sakoda and Sipser [19], it is not known whether 22D=22N2^{2\mathrm{D}}=2^{2\mathrm{N}} holds or not.

As seen above, the “size” of underlying finite and pushdown automata families affects the overall performances of those machine families. In a sharp contrast, the second factor to control their behaviors is the length of input strings fed to those underlying machines. Therefore, it is quite beneficial to place an appropriate cap 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 analyzing the overall behaviors of finite and pushdown automata families. Kapoutsis [13, 14, 15] is the first to have focused on various ceilings. Following the notational convention of Kapoutsis, we write 2D/poly2\mathrm{D}/\mathrm{poly} and 2N/poly2\mathrm{N}/\mathrm{poly} for the restrictions of 2D2\mathrm{D} and 2N2\mathrm{N} on machines of polynomial ceilings, which indicates the maximum length of inputs being upper-bounded by a certain polynomial. Such a restriction is also applicable to pushdown automata families. The notations of 2DPD/poly2\mathrm{DPD}/\mathrm{poly} and 2NPD/poly2\mathrm{NPD}/\mathrm{poly} induced respectively from 2DPD2\mathrm{DPD} and 2NPD2\mathrm{NPD} were studied in [29, 34, 35].

The third factor is the execution time-bounds, which have played an important role in studying low nonuniform complexity classes. To emphasize such an execution time (or a runtime), the notation ptime\mathrm{ptime}-2DPD/poly2\mathrm{DPD}/\mathrm{poly} and ptime\mathrm{ptime}-2NPD/poly2\mathrm{NPD}/\mathrm{poly} were introduced in [34, 35] respectively from 2DPD2\mathrm{DPD} and 2NPD2\mathrm{NPD}, where the prefix “ptime-” refers to “polynomial time” (in index nn and length ∣x∣|x| of inputs xx).

The detailed definitions of the aforementioned uniform complexity classes will be provided in § 2.3.

Figure 1. Known inclusion relationships among basic nonuniform complexity classes in the past literature [13, 14, 19, 26, 31, 32, 34, 35]. Red arrows, in particular, indicate the “proper” inclusion relationships.

Importance of Size, Ceiling, and Time Bounds

Throughout the aforementioned studies, there are, in essence, three major factors, which significantly affect the overall performance of each automata family: (i) the size of underlying machines, (ii) the ceiling bounds of input strings given to underlying machines, and (iii) the runtime of underlying machines. These three factors seem to directly relate to the complexity measures of work space, execution time, and advice size used in a standard model of Turing machines in (mainstream) computational complexity theory. Now, we wonder how finite and pushdown automata families can be empowered by their machines’ sizes, ceilings, and execution times. The purpose of this work is therefore to further explore how such factors contribute to the shift of the overall computational complexity of nonuniform automata families.

It was already observed that exponential-size machines behave quite differently from polynomial-size ones. The power of exponential-size automata families were exhibited in the following few examples: 1D⊈1P1\mathrm{D} \not\subseteq1\mathrm{P}, 1P⊈21P1\mathrm{P} \not\subseteq2^{1}\mathrm{P}, 2BP⊆21D2\mathrm{BP} \subseteq2^{1}\mathrm{D} [26], 2N⊆21D2\mathrm{N} \subseteq2^{1}\mathrm{D} [13, 14], and 1t1DPD⊈1P1\mathrm{t}1\mathrm{DPD} \not\subseteq1\mathrm{P} [32], where “1t” refers to “one (stack) turn” and 1P (resp., 2BP) is an unbounded-error (resp., bounded-error) probabilistic variant of 1N (resp., 2N). See § 2.2 and § 3 for their precise definitions. Unfortunately, there are few studies on the case of “superpolynomial-size” automata families. In this work, we wish to focus on the study of superpolynomial-size automata families.

When inputs are all limited to having polynomial ceiling, the families of polynomial-size finite automata and pushdown automata, for instance, were shown to be related to the standard log-space complexity classes, L and NL, supplemented by polynomial-size advice [2, 15, 19]. Other than polynomial ceiling bounds, Kapoutsis also considered promise problem families of superpolynomial ceilings. When ceiling bounds of polynomial-size automata families are expanded to exponentials, they in turn relate to loglog-space complexity classes supported by polylog-size advice [15]. In contrast, when ceiling is exponentially bounded, those finite automata families are related to the O(log⁡log⁡n)O(\log\log n)-space complexity classes, LL and NLL, equipped with poly-logarithmic-size advice [15].

The execution time significantly affects the computational power of two-way finite automata of large size and of two-way pushdown automata. For instance, although it is not yet known that 2UPD=2NPD2\mathrm{UPD}=2\mathrm{NPD}, we can prove that ptime\mathrm{ptime}-2UPD/poly=ptime2\mathrm{UPD}/\mathrm{poly}=\mathrm{ptime}-2NPD/poly2\mathrm{NPD}/\mathrm{poly} with no hidden assumptions [34, 35], where “U” indicates the “unambiguous” computations of underlying finite automata in the promise problem setting.

Unfortunately, we still lack a whole picture of the effects of various combinations of size, ceiling, and runtime for nonuniform families of finite and pushdown automata. Therefore, the purpose of this work is solely dedicated to the clarification of the effects of size, ceiling, and runtime by studying the mutual relationships among nonuniform classes of finite and pushdown automata families.

Illustrations of Main Contributions

In this work, we wish to answer the fundamental questions raised in § 1.2 concerning the effects of size, ceiling, and time bounds on the overall performances of finite and pushdown automata families. For this purpose, we mostly concentrate on the combinations of the following types of automata families: (i) size: polynomial and superpolynomial (including exponential), (ii) ceiling: polynomial (/poly) and exponential (/exp), and (iii) time: polynomial (ptime-), exponential (etime-), and the case of no time bound. We point out that these factors, in particular, size and ceiling do not directly have one-to-one correspondence to work space and advice size, as one expects.

In this work, we intend to develop two technical tools used for proving various collapses and separations among complexity classes: (1) reducibility by two-way deterministic finite transducers (Section 3.1) and (2) translations between automata families and advised Turing machines and auxiliary automata (Section 3.2). The first tool is usable in shifting our focal point from two-way machines to one-way machines. As for collapses/separations of nonuniform complexity classes, the second tool is described as Propositions 3.10–3.11, which play an essential role in translating finite and pushdown automata families to Turing machines and auxiliary automata, respectively. Those two technical tools will be effectively used to prove most of the collapses/separations of nonuniform classes of promise problems solvable by one-way/two-way finite and pushdown automata families. Figure 2 illustrates such collapses and separations of two-way machines and Figure 3 shows corresponding relationships of classes of exponential ceilings for nonuniform complexity classes of polynomial ceilings.

Figure 2. Inclusion relationships among lower nonuniform complexity classes with polynomial ceilings. Solid red lines indicate “proper” inclusions.

Figure 3. Inclusion relationships among nonuniform complexity classes with exponential ceilings except for the separation result of Theorem 5.3. Solid red lines indicate proper inclusions.

It is important to remark that we use the conventional mechanism of random access for advice strings. Since advice strings of size 2nO(1)2^{n^{O(1)}} are too long for underlying polynomial-time Turing machines to read in a standard way (i.e., moving a tape head back and forth over the tape), we need to allow those machines to make a random access to desired locations of the long input and advice strings (see § 3.2).

Organization of This Paper The rest of this work is organized as follows. The basic notions and various notations necessary for the later sections will be explained in § 2, including machine models of finite and pushdown automata families. Two key technical tools used for proving various containments/separations of nonuniform complexity classes will be explained in § 4. The effects of polynomial ceilings will be discussed in § 5 and those of exponential ceilings will be studied in § 6. The behaviors of polynomial- and superpolynomial-size automata families of polynomial ceilings will be examined separately in § 5.1 and § 5.2 as well as § 6. § 6 will treat polynomial- and exponential-size automata families of exponential ceilings. Throughout § 5–§ 6, our focal point is two-way finite and pushdown automata families. In § 7, on the contrary, we will study the computational complexity of one-way finite and pushdown automata families. In § 8, we will make a brief discussion and provide a pointer to the direction of future research.

Foundations of This Work

We will explain the basic notions and notation that the reader needs to read through the rest of this work.

Sets, Numbers, and Alphabets

The notation N\mathbb{N} refers to the class of all natural numbers, including 0. For the set of positive integers, we write N+\mathbb{N}^{+}. Given two integers mm and nn with m≤nm \le n, the notation [m,n]Z[m,n]_{\mathbb{Z}} denotes the integer interval composed of all integers between mm and $n (including mm and n)n) in comparison with the real interval [r1,r2][r_{1},r_{2}]. We often abbreviate as [n][n] the specific integer interval [1,n]Z[1,n]_{\mathbb{Z}} for each number n∈N+n \in\mathbb{N}^{+}. In this work, polynomials take only nonnegative integer coefficients and logarithms are all taken to the base 2. For convenience, we further set log⁡0\log0 to be 0. We use the notations nO(1)n^{O(1)} (resp., log⁡O(1)n\log^{O(1)} n and $2^{\log^{O(1)} n}$) for O(nk)O(n^{k}) (resp., O(log⁡kn)O(\log^{k} n) and 2O(log⁡kn)2^{O(\log^{k} n)}) for an “arbitrary” integer k≥1k \ge1. Given a set QQ, P(Q)\mathcal{P}(Q) denotes the power set of QQ, which consists of all subsets of QQ.

An alphabet is a nonempty finite set of “symbols” or “letters”. Given such an alphabet Σ\Sigma, a string over Σ\Sigma is a finite sequence of symbols in Σ\Sigma. The length of a string xx, denoted ∣x∣|x|, is the total number of occurrences of any symbols in xx. The notation λ\lambda denotes the empty string of length 0. Let Σ∗\Sigma^{*} denote the collection of all strings over Σ\Sigma. For any number n∈Nn \in\mathbb{N}, the notation Σn\Sigma^{n} (resp., Σ≤n\Sigma^{\le n} and Σ<n\Sigma^{<n}) denotes the subset of Σ∗\Sigma^{*} consisting only of all strings of length exactly nn (resp., at most nn and less than nn). Given a string xx of the form x1x2⋯xnx_{1}x_{2}\cdots x_{n} with xi∈Σx_{i} \in\Sigma for all i∈[n]i \in[n], the reverse of xx, denoted xRx^{R}, is the string xnxn−1⋯x2x1x_{n}x_{n-1}\cdots x_{2}x_{1}. For two languages AA and BB, the concatenation A⋅BA \cdot B (or more simply, ABAB) denotes the language {xy∣x∈A,y∈B}\{xy \mid x \in A,y \in B\}. In particular, when BB is a singleton {y}\{y\}, we succinctly write AyAy. Similarly, when A={x}A=\{x\}, we write xBxB.

References

  1. [1]C. Axler. Über die primzahl-zählfunktion, die n-te primzahl und verallgemeinerte Ramanujan-primzahlen. Doctoral Dissertation, Heinrich-Heine-Universität Düsseldorf (2013).
  2. [2]P. Berman and A. Lingas. On complexity of regular languages in terms of finite automata. Report 304, Institute of Computer Science, Polish Academy of Science, Warsaw (1977).
  3. [3]B. von Braunmühl, S. Cook, K. Mehlhorn, and R. Verbeek. The recognition of deterministic CFLs in small time and space. Information and Control 56 (1983) 34–51. doi.org/10.1016/S0019-9958(83)80049-7DOI
  4. [4]A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer. Alternation. J. ACM 28 (1981) 114–133. doi.org/10.1145/322234.322243
  5. [5]S. A. Cook. Characterizations of pushdown machines in terms of time-bounded computers. J. ACM 18 (1971) 4–18. doi.org/10.1145/321623.321625DOI
  6. [6]D. Du and K. Ko. Theory of Computational Complexity (Wiley-Interscience Series in Discrete Mathematics and Optimization), John Wiley & Sons, Inc. (2000).
  7. [7]V. Geffert. An alternating hierarchy for finite automata. Theoret. Comput. Sci. 445 (2012) 1–24. doi.org/10.1016/j.tcs.2012.04.044
  8. [8]V. Geffert, C. Mereghetti, G. Pighizzini. Converting two-way nondeterministic automata into simpler automata. Theoret. Comput. Sci. 295 (2003) 189–203. doi.org/10.1016/S0304-3975(02)00403-6
  9. [13]C. A. Kapoutsis. Size complexity of two-way finite automata. In the Proc. of the 13th International Conference on Developments in Language Theory (DLT 2009), Lecture Notes in Computer Science, vol. 5583, pp. 47–66 (2009). doi.org/10.1007/978-3-642-02737-6_4
  10. [14]C. A. Kapoutsis. Minicomplexity. J. Autom. Lang. Comb. 17 (2012) , 205–224.
  11. [15]C. A. Kapoutsis. Two-way automata versus logarithmic space. Theory Comput. Syst. 55 (2014) 421–447. doi.org/10.1007/s00224-013-9465-0
  12. [16]C. A. Kapoutsis and G. Pighizzini. Two-way automata characterizations of L/poly versus NL. Theory Comput. Syst. 56 (2015) 662–685. doi.org/10.1007/s00224-014-9560-x
  13. [17]M. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development 3 (1959) 114–125. /doi.org/10.1147/rd.32.0114DOI
  14. [18]W. L. Ruzzo. Tree-size bounded alternation. J. Comput. System Sci. 21 (1980) 218–235. /doi.org/10.1016/0022-0000(80)90036-7DOI
  15. [19]W. J. Sakoda and M. Sipser. Nondeterminism and the size of two-way finite automata. In the Proc. of the 10th Annual ACM Symposium on Theory of Computing (STOC 1978), pp. 275–286 (1978). doi.org/10.1145/800133.804357DOI
  16. [20]W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. System Sci. 4 (1970) 177–192. doi.org:10.1016/S0022-0000(70)80006-XDOI
  17. [21]J. H. Sudborough. On the tape complexity of deterministic context-free languages. J. ACM 25 (1978) 405–414. doi.org/10.1145/322077.322083
  18. [22]T. Yamakami. Swapping lemmas for regular and context-free languages. Manuscript. Available at arXiv:0808.4122 (2008).arxiv.org/abs/0808.4122
  19. [23]T. Yamakami. Pseudorandom generators against advised context-free languages. Theoret. Comput. Sci. 613 (2016) 1–27. doi.org/10.1016/j.tcs.2015.10.026arxiv.org/abs/0902.2774
  20. [24]T. Yamakami. The 2CNF Boolean formula satisfiability problem and the linear space hypothesis. J. Comput. Syst. Sci. 136 (2023) 88–112. doi.org/10.1016/j.jcss.2023.03.001. A preliminary version appeared in the Proc. of MFCS 2017, LIPIcs, vol. 83, 62:1–62:14 (2017).
  21. [25]T. Yamakami. State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis. Theoret. Comput. Sci. 798 (2019) 2–22. doi.org/10.1016/j.tcs.2019.09.006. A preliminary version appeared in the Proc. of DCFS 2018, LNCS, vol. 10952, pp. 237–249, Springer (2018).
  22. [26]T. Yamakami. Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice. Inf. Comput. 286 (2022) article no. 104783. doi.org/10.1016/j.ic.2021.104783. A preliminary version appeared in the Proc. of LATA 2019, LNCS, vol. 11417, pp. 134–145, Springer (2019).
  23. [27]T. Yamakami. Relativizations of nonuniform quantum finite automata families. In the Proc. of the 18th International Conference on Unconventional Computation and Natural Computation (UCNC 2019), Lecture Notes in Computer Science, vol. 11493, pp. 257–271, Springer (2019). doi.org/10.1007/978-3-030-19311-9_20DOI
  24. [28]T. Yamakami. Intersection and union hierarchies of deterministic context-free languages and pumping lemmas. Inf. Comput. 307 (2025) article no. 105358. doi.org/10.1016/j.ic.2025.105358. A preliminary report appeared in the Proc. of LATA 2020, LNCS, vol. 12038, pp. 341–353, Springer (2020).
  25. [29]T. Yamakami. Parameterizations of logarithmic-space reductions, stack-state complexity of nonuniform families of pushdown automata, and a road to the LOGCFL ⊆ LOGDCFL/poly. Manuscript, available at arXiv:2108.12779 (2021).arxiv.org/abs/2108.12779
  26. [30]T. Yamakami. The no endmarker theorem for one-way probabilistic pushdown automata. Manuscript, available at arXiv:2111.02688 (2021).arxiv.org/abs/2111.02688
  27. [31]T. Yamakami. Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata. In the Proc. of the 16th International Conference on Reachability Problems (RP 2022), Lecture Notes in Computer Science, vol. 13608, pp. 77–92, Springer (2022). doi.org/10.1007/978-3-031-19135-0_6. A corrected and expanded version is available at arXiv:2311.09979.arxiv.org/abs/2311.09979
  28. [32]T. Yamakami. Power of counting by nonuniform families of polynomial-size finite automata. Inf. Comput. 307 (2025) article no. 105372. doi.org/10.1016/j.ic.2025.105372. A preliminary report appeared in the Proc. of FCT 2023, LNCS, vol. 14292, pp. 421–435, Springer (2023).
  29. [33]T. Yamakami. When input integers are given in the unary numeral representation. In the Proc. of the 24th Italian Conference on Theoretical Computer Science (ICTCS 2023), CEUR Workshop Proceedings (CEUR-WS.org), vol. 3587, pp. 268–282 (2023).arxiv.org/abs/2312.04348
  30. [34]T. Yamakami. Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters. In the Proc. of the 18th Annual Conference on Theory and Applications of Models of Computation (TAMC 2024), Lecture Notes in Computer Science, vol. 14637, pp. 14–25, Springer (2024). doi.org/10.1007/978-981-97-2340-9_2arxiv.org/abs/2404.13254
  31. [35]T. Yamakami. 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 [34]. Available at arXiv:2404.13254 (2024).arxiv.org/abs/2404.13254
  32. [37]T. Yamakami. How can size and ceiling bounds affect the complexity of nonuniform automata families? In the Proc. of the 16th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2026), Electronic Proceedings in Theoretical Computer Science (EPTCS) vol. 446, pp. 105–120, 2026. doi.org:10.4204/EPTCS.446.7

Paper details

vlnc:W_m639vpf8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents