Geodesic
Local Normal Forms for First-Order Logic with Applications to Games and Automata
Discrete mathematics & theoretical computer science, Tome 3 (1998-1999) no. 3 Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

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. 
@article{DMTCS_1999_3_3_a1,
     author = {Schwentick, Thomas and Barthelmann, Klaus},
     title = {Local {Normal} {Forms} for {First-Order} {Logic} with {Applications} to {Games} and {Automata}},
     journal = {Discrete mathematics & theoretical computer science},
     year = {1998-1999},
     volume = {3},
     number = {3},
     doi = {10.46298/dmtcs.254},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.254/}
}
TY  - JOUR
AU  - Schwentick, Thomas
AU  - Barthelmann, Klaus
TI  - Local Normal Forms for First-Order Logic with Applications to Games and Automata
JO  - Discrete mathematics & theoretical computer science
PY  - 1998-1999
VL  - 3
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.254/
DO  - 10.46298/dmtcs.254
LA  - en
ID  - DMTCS_1999_3_3_a1
ER  - 
%0 Journal Article
%A Schwentick, Thomas
%A Barthelmann, Klaus
%T Local Normal Forms for First-Order Logic with Applications to Games and Automata
%J Discrete mathematics & theoretical computer science
%D 1998-1999
%V 3
%N 3
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.254/
%R 10.46298/dmtcs.254
%G en
%F DMTCS_1999_3_3_a1
Schwentick, Thomas; Barthelmann, Klaus. Local Normal Forms for First-Order Logic with Applications to Games and Automata. Discrete mathematics & theoretical computer science, Tome 3 (1998-1999) no. 3. doi: 10.46298/dmtcs.254

Cité par Sources :