  A type system combining type application, constants as types, union types
(associative, commutative and idempotent) and recursive types has recently been
proposed for statically typing path polymorphism, the ability to define
functions that can operate uniformly over recursively specified applicative
data structures. A typical pattern such functions resort to is $x\,y$ which
decomposes a compound, in other words any applicative tree structure, into its
parts. We study type-checking for this type system in two stages. First we
propose algorithms for checking type equivalence and subtyping based on
coinductive characterizations of those relations. We then formulate a
syntax-directed presentation and prove its equivalence with the original one.
This yields a type-checking algorithm which unfortunately has exponential time
complexity in the worst case. A second algorithm is then proposed, based on
automata techniques, which yields a polynomial-time type-checking algorithm.
