An Ehrenfeucht-Fraisse game for L-omega 1 omega

作者：Vaananen Jouko; Wang Tong^*

来源：Mathematical Logic Quarterly, 2013, 59(4-5): 357-370.

DOI：10.1002/malq.201200104

• Ehrenfeucht-Fraisse game
• infinitary logic

In this paper we develop an Ehrenfeucht-Fraisse game for L1. Unlike the standard Ehrenfeucht-Fraisse games which are modeled solely after the behavior of quantifiers, this new game also takes into account the behavior of connectives in logic. We prove the adequacy theorem for this game. We also apply the new game to prove complexity results about infinite binary strings.

• 出版日期2013-8