Homomorphism duality pairs and regular families of forests
Gábor Tardos
Rényi Institute, Budapest
Péter L. Erdős
Rényi Institute, Budapest
Dömötör Pálvölgyi
Eötvös Loránd University, Budapest
Claude Tardif
Royal Military College, Kingston, ON
PDF
PLENARY TALK
Content: Homomorphism duality pairs play a crucial role in the theory of relational structures and in the Constraint Satisfaction Problem. In this talk we concentrate on infinite-finite duality pairs of directed graphs. We find a characterization of infinite antichains that allow for a finite dual. The characterization resembles the Myhill-Nerode characterization of regular languages, so we call these families ragular.