Discrete Mathematics & Theoretical Computer Science


Volume 3 n° 3 (1999), pp. 109-124

author:Thomas Schwentick and Klaus Barthelmann
title:Local Normal Forms for First-Order Logic with Applications to Games and Automata
keywords:First-order logic, existential monadic second-order logic, games, automata, locality
abstract:Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃ x1,...,xl, ∀ 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.
reference: Thomas Schwentick and Klaus Barthelmann (1999), Local Normal Forms for First-Order Logic with Applications to Games and Automata , Discrete Mathematics and Theoretical Computer Science 3, pp. 109-124
corrigendum: In 2000 the authors added a short corrigendum to their paper which you find as second reference for download below.
ps.gz-source: dm030303.ps.gz (62 K) dm030303-cor1.ps.gz
ps-source: dm030303.ps (163 K) dm030303-cor1.ps
pdf-source: dm030303.pdf (284 K) dm030303-cor1.pdf

The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Automatically produced on Tue Sep 28 13:11:40 MEST 1999 by gustedt