Erdős, Péter and Tardif, C. and Tardos, Gábor (2013) On Infinitefinite Duality Pairs of Directed Graphs. ORDERA JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 30 (3). pp. 807819. ISSN 01678094

Text
ETTOrder2ndrevision.pdf Download (102kB)  Preview 
Abstract
The {Mathematical expression} duality pairs play a crucial role in the theory of general relational structures and in Constraint Satisfaction Problems. The case where both sides are finite is fully characterized. The case where both sides are infinite seems to be very complex. It is also known that no finiteinfinite duality pair is possible if we make the additional restriction that both classes are antichains. In this paper (which is the first one of a series) we start the detailed study of the infinitefinite case. Here we concentrate on directed graphs. We prove some elementary properties of the infinitefinite duality pairs, including lower and upper bounds on the size of {Mathematical expression}, and show that the elements of {Mathematical expression} must be equivalent to forests if {Mathematical expression} is an antichain. Then we construct instructive examples, where the elements of {Mathematical expression} are paths or trees. Note that the existence of infinitefinite antichain dualities was not previously known.
Item Type:  Article 

Uncontrolled Keywords:  Regular languages; Nondeterministic finite automaton; graph homomorphism; General relational structures; Duality pairs; Constraint satisfaction problem; Nondeterministic finite automaton 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  06 Feb 2014 05:42 
Last Modified:  08 Feb 2014 07:59 
URI:  http://real.mtak.hu/id/eprint/9899 
Actions (login required)
Edit Item 