Paper: First-Order Definable Retraction Problems for Posets and Reflexive Graphs (at LICS 2004)
Authors: Victor Dalmau Andrei Krokhin Benoit LaroseAbstract
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} }