Caterpillar dualities and regular languages

Abstract

We characterize obstruction sets in caterpillar dualities in terms of regular languages, and give a construction of the dual of a regular family of caterpillars. We show that these duals correspond to the constraint satisfaction problems definable by a monadic linear Datalog program with at most one EDB per rule.