Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

Local Normal Forms for First-Order Logic with Applications to Games and Automata

Abstract : Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃ x_1,...,x_l, \forall y, φ where φ is r-local around y, i.e. quantification in φ is restricted to elements of the universe of distance at most r from y. \par From this and related normal forms, variants of the Ehrenfeucht game for first-order and existential monadic second-order logic are developed that restrict the possible strategies for the spoiler, one of the two players. This makes proofs of the existence of a winning strategy for the duplicator, the other player, easier and can thus simplify inexpressibility proofs. \par As another application, automata models are defined that have, on arbitrary classes of relational structures, exactly the expressive power of first-order logic and existential monadic second-order logic, respectively.
Document type :
Journal articles
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Thursday, March 13, 2014 - 4:47:52 PM
Last modification on : Wednesday, November 29, 2017 - 10:26:20 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:00:26 PM


Files produced by the author(s)




Thomas Schwentick, Klaus Barthelmann. Local Normal Forms for First-Order Logic with Applications to Games and Automata. Discrete Mathematics and Theoretical Computer Science, DMTCS, 1999, Vol. 3 no. 3 (3), pp.109-124. ⟨10.46298/dmtcs.254⟩. ⟨hal-00958930⟩



Record views


Files downloads