General homomorphic overloading

A general homomorphic overloading in a first-order type system is discussed and its attendant subtype inference problem is formulated. We propose a computationally efficient type inference algorithm by converting the attendant constraint-satisfaction problem into the algebraic path problem for a constraint graph weighted with elements of a specially constructed non-commutative star semiring. The elements of the semiring are monotonic functions from integers to integers (including ±∞) with pointwise maximum and function composition as semiring operations. The computational efficiency of our method is due to Kleene’s algebraic path method’s cubic complexity