Fugu-MT 論文翻訳(概要): Complexity and Avoidance

論文の概要: Complexity and Avoidance

arxiv url: http://arxiv.org/abs/2204.11289v1
Date: Sun, 24 Apr 2022 14:36:38 GMT
ステータス: 処理完了
システム内更新日: 2022-04-27 01:02:37.560251
Title: Complexity and Avoidance
Title（参考訳）: 複雑さと回避
Authors: Hayden Jananthan
Abstract要約: 適切な$f$と$p$に対して$q$と$g$があり、$mathrmLUA(q) leq_mathrms mathrmCOMPLEX(f)$と$q$と$g$の成長率があることを示す。シフト複雑性に関して、$$$q$が$rmLUA(q)$の任意のメンバに対して、$delta$-shift複素列を計算するためにどれだけ遅くなるかという明示的な境界が与えられる。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this dissertation we examine the relationships between the several hierarchies, including the complexity, $\mathrm{LUA}$ (Linearly Universal Avoidance), and shift complexity hierarchies, with an eye towards quantitative bounds on growth rates therein. We show that for suitable $f$ and $p$, there are $q$ and $g$ such that $\mathrm{LUA}(q) \leq_\mathrm{s} \mathrm{COMPLEX}(f)$ and $\mathrm{COMPLEX}(g) \leq_\mathrm{s} \mathrm{LUA}(p)$, as well as quantify the growth rates of $q$ and $g$. In the opposite direction, we show that for certain sub-identical $f$ satisfying $\lim_{n \to \infty}{f(n)/n}=1$ there is a $q$ such that $\mathrm{COMPLEX}(f) \leq_\mathrm{w} \mathrm{LUA}(q)$, and for certain fast-growing $p$ there is a $g$ such that $\mathrm{LUA}(p) \leq_\mathrm{s} \mathrm{COMPLEX}(g)$, as well as quantify the growth rates of $q$ and $g$. Concerning shift complexity, explicit bounds are given on how slow-growing $q$ must be for any member of $\rm{LUA}(q)$ to compute $\delta$-shift complex sequences. Motivated by the complexity hierarchy, we generalize the notion of shift complexity to consider sequences $X$ satisfying $\operatorname{KP}(\tau) \geq f(|\tau|) - O(1)$ for all substrings $\tau$ of $X$ where $f$ is any order function. We show that for sufficiently slow-growing $f$, $f$-shift complex sequences can be uniformly computed by $g$-complex sequences, where $g$ grows slightly faster than $f$. The structure of the $\mathrm{LUA}$ hierarchy is examined using bushy tree forcing, with the main result being that for any order function $p$, there is a slow-growing order function $q$ such that $\mathrm{LUA}(p)$ and $\mathrm{LUA}(q)$ are weakly incomparable. Using this, we prove new results about the filter of the weak degrees of deep nonempty $\Pi^0_1$ classes and the connection between the shift complexity and $\mathrm{LUA}$ hierarchies.
Abstract（参考訳）: この論文では、複雑性、$\mathrm{LUA}$(Linearly Universal Avoidance)およびシフト複雑性階層を含むいくつかの階層間の関係を、成長速度の定量的な境界に注目して検討する。適切な$f$と$p$に対して、$q$と$g$があり、$\mathrm{LUA} であることを示す。 (q) \leq_\mathrm{s} \mathrm{COMPLEX} (f)$ と $\mathrm{complex} (g) \leq_\mathrm{s} \mathrm{LUA} (p)$および$q$および$g$の成長率の定量化。逆向きに、$\lim_{n \to \infty}{f(n)/n}=1$を満たす部分同一の$f$ に対して$\mathrm{complex} となる$q$ が存在することを示す。 (f) \leq_\mathrm{w} \mathrm{LUA} (q)$と、ある急速に成長する$p$に対して、$\mathrm{LUA} となる$g$が存在する。 (p) \leq_\mathrm{s} \mathrm{COMPLEX} (g)$および$q$および$g$の成長率の定量化。シフト複雑性に関して、$\rm{LUA} の任意のメンバに対して、q$ がどれだけ遅く成長するかを明確に制限する。 (q)$ で$\delta$-shift の複素列を計算する。複雑性階層に動機付けられ、シフト複雑性の概念を一般化して、$X$ を満たす列 $\operatorname{KP}(\tau) \geq f(|\tau|) - O(1)$ をすべての部分弦に対して $\tau$ of $X$ とする。十分にゆっくり成長する$f$の場合、$f$-shift複素列は$g$-complex sequencesによって一様に計算され、$g$は$f$よりもわずかに速く成長する。 $\mathrm{LUA}$階層の構造は、ブッディーツリーの強制によって調べられ、主な結果は、任意の順序関数$p$に対して、$\mathrm{LUA} のようなゆっくりと成長する順序関数 $q$ が存在することである。 (p)$ と $\mathrm{lua} (q)$は弱可算である。これを用いて、深い空でない$\Pi^0_1$クラスの弱度フィルタとシフト複雑性と$\mathrm{LUA}$階層との間の接続に関する新しい結果を示す。

論文の概要: Complexity and Avoidance

関連論文リスト