A Decision Algorithm for Linear Isomorphism of Types with Complexity tex2html_wrap_inline21

Alexander E. Andreev
Sergei Soloviev

November 1996


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 tex2html_wrap_inline21

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.