A Decision Algorithm for Linear Isomorphism of Types with Complexity Cn(log2(n))

Alexander E. Andreev, Sergei Soloviev


It is known that ordinary isomorphisms (associativity and commutativity
of "times", isomorphisms for "times" unit and currying)
provide a complete axiomatisation for linear isomorphism of types.
One of the reasons to consider linear isomorphism of types instead of
ordinary isomorphism was that better complexity could be expected.
Meanwhile, no upper bounds reasonably close to linear were obtained.
We describe an algorithm deciding if two types are linearly isomorphic
with complexity Cn(log2(n)).

Full Text:


DOI: http://dx.doi.org/10.7146/brics.v3i46.20048
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.

ISSN: 0909-0878 

Hosted by the Royal Danish Library and Aarhus University Library