搜索结果: 1-2 共查到“数学 language”相关记录2条 . 查询时间(0.191 秒)
Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language
Decision problems infinite Post Correspondence Problem analytical hierarchy high undecidability infinitary rational relations
2011/10/10
Abstract: It was noticed by Harel in [Har86] that "one can define $\Sigma_1^1$-complete versions of the well-known Post Correspondence Problem". We first give a complete proof of this result, showing ...
Abstract: We firstly show that the standard interpretation of natural quantification in mathematical logic does not provide a satisfying account of its original richness. In particular, it ignores the...