IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Twentieth Annual IEEE Symposium on

Logic in Computer Science (LICS 2005)

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

Authors: Hannu Niemistö


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.


    author = 	 {Hannu Niemistö},
    title = 	 {On Locality and Uniform Reduction},
    booktitle =  {Proceedings of the Twentieth Annual IEEE Symposium on Logic in Computer Science (LICS 2005)},
    year =	 {2005},
    month =	 {June}, 
    pages =      {41--50},
    location =   {Chicago, USA}, 
    publisher =	 {IEEE Computer Society Press}

Last modified: 2017-04-0512:37
Andrzej Murawski