Some complete $ω$-powers of a one-counter language in the difference hierarchy

概要

Fix a finite alphabet $Σ$ having at least two letters, and natural numbers $n,k\geq 1$. We denote by $D_n(\mathbfΠ^0_k)$ the class of differences of $n$ subsets of the Cantor space $Σ^ω$ in $\mathbfΠ0_k$, and by $D_n-(\mathbfΠ^0_k)$ the class of complements of sets in $D_n(\mathbfΠ^0_k)$. We prove, for any natural numbers $n,k\geq 1$, the existence of a finite alphabet $Σ$ having at least two letters and a finitary language $U_{n,k}$ over $Σ$ accepted by a one-counter automaton such that the $ω$-power $$U_{n,k}^\infty:={ w_0w_1\cdots\inΣ^ω\mid\forall i\inω~~w_i\in U_{n,k}}$$ is $D_{2n-1}(\mathbfΠ^0_k)$-complete. We also prove a conditional result for the dual classes $D^-_{2n}(\mathbfΠ^0_k)$: under the assumption that there exists a finitary language $V_{n,3}$ accepted by a one-counter automaton, such that its $ω$-power $V_{n,3}^\infty$ is $D^-_{2n}(\mathbfΠ^0_3)$-complete, there would also exist, for any integer $k>3$, a finitary language $V_{n,k}$ accepted by a one-counter automaton, such that its $ω$-power $V_{n,k}^\infty$ is $D^-_{2n}(\mathbfΠ^0_k)$-complete. Finally we add another conditionnal result about Wadge degrees of rational $\mathbfΔ^0_2$ omega powers, which completes the recent results of [FGL26].

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Some complete $ω$-powers of a one-counter language in the difference hierarchy

# 概要
Fix a finite alphabet $Σ$ having at least two letters, and natural numbers $n,k\geq 1$. We denote by $D_n(\mathbfΠ^0_k)$ the class of differences of $n$ subsets of the Cantor space $Σ^ω$ in…

# 原典
https://arxiv.org/abs/2610.16473

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。