← 研踪 PaperTrailarXiv:2610.16473 · v2
Some complete $ω$-powers of a one-counter language in the difference hierarchy
首次提交 2026-10-12 17:26
版本更新 2026-11-12 21:04
雷达观测 2026-11-17 04:58
摘要
Fix a finite alphabet having at least two letters, and natural numbers . We denote by the class of differences of subsets of the Cantor space in , and by the class of complements of sets in . We prove, for any natural numbers , the existence of a finite alphabet having at least two letters and a finitary language over accepted by a one-counter automaton such that the -power is -complete. We also prove a conditional result for the dual classes : under the assumption that there exists a finitary language accepted by a one-counter automaton, such that its -power is -complete, there would also exist, for any integer , a finitary language accepted by a one-counter automaton, such that its -power is -complete. Finally we add another conditionnal result about Wadge degrees of rational omega powers, which completes the recent results of [FGL26].
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-12 21:04 · 最新观测版本
Some complete $ω$-powers of a one-counter language in the difference hierarchy
Fix a finite alphabet having at least two letters, and natural numbers . We denote by the class of differences of subsets of the Cantor space in , and by the class of complements of sets in . We prove, for any natural numbers , the existence of a finite alphabet having at least two letters and a finitary language over accepted by a one-counter automaton such that the -power is -complete. We also prove a conditional result for the dual classes : under the assumption that there exists a finitary language accepted by a one-counter automaton, such that its -power is -complete, there would also exist, for any integer , a finitary language accepted by a one-counter automaton, such that its -power is -complete. Finally we add another conditionnal result about Wadge degrees of rational omega powers, which completes the recent results of [FGL26].
查看此版本解读 →查看此版本原文 ↗