论文标题
描述性集理论和$ω$ - 一条语言的力量
Descriptive Set Theory and $ω$-Powers of Finitary Languages
论文作者
论文摘要
有限字母$σ$的$ω$ - lphabet $σ$是无限单词的语言，超过$σ$，由l $ \ infty $：= {w 0 w 1。.. $ \ in $ $σ$ $ $ $ω$ | $ \ forall $ i $ \ in $ $ $ω$ w i $ \ in $ l}。 $ω$ - 能力在理论计算机科学中非常自然地表征了多种自动机接受的几类语言，例如b {ü} chi automata或b {ü} chi Pushdown automata。我们调查了有关描述性集理论和$ω$强力的链接的一些最新结果。
The $ω$-power of a finitary language L over a finite alphabet $Σ$ is the language of infinite words over $Σ$ defined by L $\infty$ := {w 0 w 1. .. $\in$ $Σ$ $ω$ | $\forall$i $\in$ $ω$ w i $\in$ L}. The $ω$-powers appear very naturally in Theoretical Computer Science in the characterization of several classes of languages of infinite words accepted by various kinds of automata, like B{ü}chi automata or B{ü}chi pushdown automata. We survey some recent results about the links relating Descriptive Set Theory and $ω$-powers.
