{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T08:45:19Z","timestamp":1782636319960,"version":"3.54.5"},"reference-count":27,"publisher":"Open Publishing Association","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. Proc. Theor. Comput. Sci.","EPTCS"],"DOI":"10.4204\/eptcs.446.7","type":"journal-article","created":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T08:24:52Z","timestamp":1782635092000},"page":"105-120","source":"Crossref","is-referenced-by-count":0,"title":["How Can Size and Ceiling Bounds Affect the Complexity of Nonuniform Automata Families?"],"prefix":"10.4204","volume":"446","author":[{"given":"Tomoyuki","family":"Yamakami","sequence":"first","affiliation":[{"name":"University of Fukui"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"2720","published-online":{"date-parts":[[2026,6,25]]},"reference":[{"key":"Axl13","volume-title":"\u00dcber die Primzahl-Zz\u00e4hlfunktion, die n-te Primzahl und verallgemeinerte Ramanujan-Primzahlen","author":"Axler","year":"2013"},{"key":"BCM+83","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/s0019-9958(83)80049-7","article-title":"The recognition of determinsitic CFLs in small time and space","volume":"56","author":"von Braunm\u00fchl","year":"1983","journal-title":"Information and Control"},{"key":"Coo71","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/321623.321625","article-title":"Characterizations of pushdown machines in terms of time-bounded computers","volume":"18","author":"Cook","year":"1971","journal-title":"Journal of the ACM"},{"key":"Gef12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.04.044","article-title":"An alternating hierarchy for finite automata","volume":"445","author":"Geffert","year":"2012","journal-title":"Theoretical Computer Science"},{"key":"GMP03","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/s0304-3975(02)00403-6","article-title":"Converting two-way nondeterministic automata into simpler automata","volume":"295","author":"Geffert","year":"2003","journal-title":"Theoretical Computer Science"},{"key":"GP11","doi-asserted-by":"publisher","first-page":"1016","DOI":"10.1016\/j.ic.2011.03.003","article-title":"Two-way unary automata versus logarithmic space","volume":"209","author":"Geffert","year":"2011","journal-title":"Information and Computation"},{"key":"GS66","doi-asserted-by":"crossref","DOI":"10.1137\/0304034","volume-title":"Finite-turn pushdown automata","author":"Ginsburg","year":"1966"},{"key":"Har72","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/bf00289513","article-title":"On non-determinacy in simple computing devices","volume":"1","author":"Hartmanis","year":"1972","journal-title":"Acta Informatica"},{"key":"HU79","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"1979"},{"key":"Kap09","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-642-02737-6_4","article-title":"Size complexity of two-way finite automata","volume-title":"Proc. of the 13th International Conference on Developments in Language Theory (DLT 2009)","volume":"5583","author":"Kapoutsis","year":"2009"},{"key":"Kap12","first-page":"205","article-title":"Minicomplexity","volume":"17","author":"Kapoutsis","year":"2012","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"Kap14","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s00224-013-9465-0","article-title":"Two-way automata versus logarithmic space","volume":"55","author":"Kapoutsis","year":"2014","journal-title":"Theory of Computing Systems"},{"key":"KP15","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/s00224-014-9560-x","article-title":"Two-way automata characterizations of L\/poly versus NL","volume":"56","author":"Kapoutsis","year":"2015","journal-title":"Theory of Computing Systems"},{"key":"RS59","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","article-title":"Finite automata and their decision problems","volume":"3","author":"Rabin","year":"1959","journal-title":"IBM Journal of Research and Development"},{"key":"Ruz80","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","article-title":"Tree-size bounded alternation","volume":"21","author":"Ruzzo","year":"1980","journal-title":"Journal of Computer and System Sciences"},{"key":"SS78","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1145\/800133.804357","article-title":"Nondeterminism and the size of two-way finite automata","volume-title":"Proc. of the 10th Annual ACM Symposium on Theory of Computing (STOC 1978)","author":"Sakoda","year":"1978"},{"key":"Sud78","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1145\/322077.322083","article-title":"On the tape complexity of deterministic context-free languages","volume":"25","author":"Sudborough","year":"1978","journal-title":"Journal of the ACM"},{"key":"Yam16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2015.10.026","article-title":"Pseudorandom generators against advised context-free languages","volume":"613","author":"Yamakami","year":"2016","journal-title":"Theoretical Computer Science"},{"key":"Yam19b","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-030-19311-9_20","article-title":"Relativizations of nonuniform quantum finite automata families","volume-title":"Proc. of the 18th International Conference on Unconventional Computation and Natural Computation (UCNC 2019)","volume":"11493","author":"Yamakami","year":"2019"},{"key":"Yam18","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2019.09.006","article-title":"State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis","volume":"798","author":"Yamakami","year":"2019","journal-title":"Theoretical Computer Science"},{"key":"Yam19a","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104783","article-title":"Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice","volume":"286","author":"Yamakami","year":"2022","journal-title":"Information and Computation"},{"key":"Yam17","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.jcss.2023.03.001","article-title":"The 2CNF Boolean formula satisfiability problem and the linear space hypothesis","volume":"136","author":"Yamakami","year":"2023","journal-title":"Journal of Computer and System Sciences"},{"key":"Yam23b","series-title":"CEUR Workshop Proceedings","first-page":"268","article-title":"When input integers are given in the unary numeral representation","volume-title":"Proc. of the 24th Italian Conference on Theoretical Computer Science (ICTCS 2023)","volume":"3587","author":"Yamakami","year":"2023"},{"key":"Yam24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-981-97-2340-9_2","article-title":"Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters","volume-title":"Proc. of the 18th Annual Conference on Theory and Applications of Models of Computation (TAMC 2024)","volume":"14637","author":"Yamakami","year":"2024"},{"key":"Yam20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2025.105358","article-title":"Intersection and union hierarchies of deterministic context-free languages and pumping lemmas","volume":"307","author":"Yamakami","year":"2025","journal-title":"Information and Computation"},{"key":"Yam23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2025.105372","article-title":"Power of counting by nonuniform families of polynomial-size finite automata","volume":"307","author":"Yamakami","year":"2025","journal-title":"Information and Computation"},{"key":"Yam25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-031-97100-6_14","article-title":"What is the most natural generalized pumping lemma beyond regular and context-free languages?","volume-title":"Proc. of the 26th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems (DCFS 2025)","volume":"15759","author":"Yamakami","year":"2025"}],"container-title":["Electronic Proceedings in Theoretical Computer Science"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,6,28]],"date-time":"2026-06-28T08:25:03Z","timestamp":1782635103000},"score":1,"resource":{"primary":{"URL":"http:\/\/arxiv.org\/abs\/2606.26685v1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,25]]},"references-count":27,"URL":"https:\/\/doi.org\/10.4204\/eptcs.446.7","relation":{},"ISSN":["2075-2180"],"issn-type":[{"value":"2075-2180","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,25]]}}}