跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.20999 · v1

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

首次提交 2026-11-16 20:26
版本更新 2026-11-16 20:26
雷达观测 2026-11-17 17:11
arXiv ↗PDF ↗

摘要

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.

作者备注:(A4 size, 10pt, 34 pages, 6 figures) This paper is a modified, extended version of arxiv.org/abs/2606.26685v1 (2026). This paper is an extended and corrected version of a preliminary report (with a slightly different title) appeared in the Proceedings of the 16th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2026), EPTCS vol. 446, pp. 105-120, 2026

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-16 20:26 · 最新观测版本

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

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.

查看此版本解读 →查看此版本原文 ↗