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