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



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.

Back to all abstracts