搜索结果: 1-2 共查到“知识库 数理逻辑与数学基础 language”相关记录2条 . 查询时间(0.156 秒)
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...