Logic in Computer Science (LICS 2004)

Paper: First-Order Definable Retraction Problems for Posets and Reflexive Graphs (at LICS 2004)

Authors: Victor Dalmau Andrei Krokhin Benoit Larose

Abstract

A retraction from a structure P to its substructure Q is a homomorphism from P onto Q that is the identity on Q. We present an algebraic condition which completely characterises all posets and all reflexive graphs Q with the following property: the class of all posets or reflexive graphs, respectively, that admit a retraction onto Q is first-order definable.

BibTeX

  @InProceedings{DalmauKrokhinLarose-FirstOrderDefinable,
    author = 	 {Victor Dalmau and Andrei Krokhin and Benoit Larose},
    title = 	 {First-Order Definable Retraction Problems for Posets and Reflexive Graphs},
    booktitle =  {Proceedings of the Nineteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2004},
    year =	 2004,
    editor =	 {Harald Ganzinger},
    month =	 {July}, 
    pages =      {232--241},
    location =   {Turku, Finland}, 
    publisher =	 {IEEE Computer Society Press}
  }