author:  Thomas Schwentick and Klaus Barthelmann 
title:  Local Normal Forms for FirstOrder Logic with Applications to Games and Automata

keywords:  Firstorder logic, existential monadic secondorder logic, games, automata, locality

abstract:  Building on work of Gaifman [Gai82] it is shown that every firstorder formula is logically equivalent to a formula of the form
∃ x_{1},...,x_{l}, ∀ y, ϕ where ϕ is rlocal
around y, i.e. quantification in ϕ is restricted to elements
of the universe of distance at most r from y.

reference: 
Thomas Schwentick and Klaus Barthelmann (1999),
Local Normal Forms for FirstOrder Logic with Applications to Games and Automata
,
Discrete Mathematics and Theoretical Computer Science 3,
pp. 109124 
corrigendum: 
In 2000 the authors added a short corrigendum to
their paper which you find as second reference for
download below. 
ps.gzsource: 
dm030303.ps.gz
(62 K)
dm030303cor1.ps.gz

pssource: 
dm030303.ps
(163 K)
dm030303cor1.ps

pdfsource: 
dm030303.pdf
(284 K)
dm030303cor1.pdf
