An Ehrenfeucht-Fraïssé game for Lω1ω

Authors
Publication date 08-2013
Journal Mathematical Logic Quarterly
Volume | Issue number 59 | 4-5
Pages (from-to) 357-370
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract

In this paper we develop an Ehrenfeucht-Fraïssé game for Lω1ω. Unlike the standard Ehrenfeucht-Fraïssé 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.
Document type Article
Language English
Published at https://doi.org/10.1002/malq.201200104
Permalink to this page
Back