Logic in Computer Science (LICS 2005)

Paper: On Locality and Uniform Reduction (at LICS 2005)

Authors: Hannu Niemisto

Abstract

Uniform reduction for pairs originates from abstract logic but it has not been studied much in the context of fi- nite model theory. The paper demonstrates its relationship to locality. The first part of the paper is motivated by the question when first-order logic extended with quantifiers is Hanf-local. Two properties, tolerant Hanf-locality and separable Hanf-locality are defined, both of which ensure this if all quantifiers in question have the property. It is shown that all regular Hanf-local logics not tolerantly Hanf-local have weak version of uniform reduction for pairs. In the rest of the paper, relationship between different forms of locality, regularity and uniform reduction is studied in the class of finite directed trees.

BibTeX

  @InProceedings{Niemisto-OnLocalityandUnifor,
    author = 	 {Hannu Niemisto},
    title = 	 {On Locality and Uniform Reduction},
    booktitle =  {Proceedings of the Twentieth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2005},
    year =	 2005,
    editor =	 {Prakash Panangaden},
    month =	 {June}, 
    pages =      {41--50},
    location =   {Chicago, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }