Universal Algebra Seminar

Renzhi Song, Department of Pure Mathematics, University of Waterloo

"Series parallel posets and polymorphisms, part 2"

In this two part series I will talk about the poset retraction problem on the class of series parallel posets. Having classified those series-parallel posets whose retraction problem can be solved in polynomial time, I will now show that these same posets admit what is known as SD-join polymorphisms. Equivalently, their retraction problems are in nondeterministic log space.

MC 5413