AbstractWe consider fixed point logics, i.e., extensions of first order predicate logic with operators defining fixed points. A number of such operators, generalizing inductive definitions, have been studied in the context of finite model theory, including nondeterministic and alternating operators. We review results established in finite model theory, and also consider the expressive power of the resulting logics on infinite structures. In particular, we establish the relationship between inflationary and nondeterministic fixed point logics and second order logic, and we consider questions related to the determinacy of games associated with alternating fixed points.
摘要:我们考虑固定点逻辑,即在一阶谓词逻辑中定义固定点的操作符扩展。在有限模型理论的背景下,已经研究了许多这样的操作符,包括泛化归纳定义的非确定性和交替操作符。我们回顾了在有限模型理论中建立的结果,并考虑了结果逻辑在无限结构上的表达能力。特别是,我们建立了增生和非确定性固定点逻辑与二阶逻辑之间的关系,并考虑了与交替固定点相关联的游戏的确定性问题。