Caterpillar dualities and regular languages

Péter L. Erdős, Claude Tardif, Gábor Tardos

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.

picture_as_pdf flag

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment