CATERPILLAR DUALITIES AND REGULAR LANGUAGES
Erdős, Péter, Tardif, C., Gábor Tardos · Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) · 2013
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. In particular, we prove that every monadic linear Datalog program with at most one EDB per rule defines the complement of a contraint satisfaction problem. 1.