Regular families of forests, antichains and duality pairs of relational structures

DOI10.1007/S00493-015-3003-4zbMath1399.68066arXiv1207.4402OpenAlexW1924742230MaRDI QIDQ681598

Gábor Tardos, Vlaude Tardif, Dömötör Pálvölgyi, Péter L. Erdős

Publication date: 12 February 2018

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.4402

zbMATH Keywords

antichainsrelational structuresforestsduality pairs

Mathematics Subject Classification ID

Trees (05C05) Descriptive complexity and finite models (68Q19)

Related Items (5)

In praise of homomorphisms ⋮ On infinite-finite duality pairs of directed graphs ⋮ Security Protocol Analysis in Context: Computing Minimal Executions Using SMT and CPSA ⋮ NU Polymorphisms on Reflexive Digraphs ⋮ All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)

Cites Work

• No finite-infinite antichain duality in the homomorphism poset of directed graphs
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• How to split antichains in infinite posets
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• A Characterisation of First-Order Constraint Satisfaction Problems
• Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
• Dualities for Constraint Satisfaction Problems
• Automata, Languages and Programming

This page was built for publication: Regular families of forests, antichains and duality pairs of relational structures