The undecidability of the semi-unification problem

DOI10.1006/INCO.1993.1003zbMath0769.68059OpenAlexW1993695344WikidataQ61634982 ScholiaQ61634982MaRDI QIDQ1207950

A. J. Kfoury, Paweł Urzyczyn, Jerzy Tiuryn

Publication date: 16 May 1993

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1993.1003

zbMATH Keywords

undecidabilityboundednessTuring machinesSemi-Unification Problem

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Undecidability and degrees of sets of sentences (03D35) Grammars and rewriting systems (68Q42)

Related Items (14)

The role of polymorphism in the characterisation of complexity by soft types ⋮ Semi-unification of two terms in Abelian groups ⋮ Fast algorithms for uniform semi-unification ⋮ Contribution of Warsaw logicians to computational logic ⋮ Constructive Many-one Reduction from the Halting Problem to Semi-unification (Extended Version) ⋮ On subsumption and semiunification in feature algebras ⋮ The undecidability of type related problems in the type-free style System F with finitely stratified polymorphic types ⋮ Iteration and coiteration schemes for higher-order and nested datatypes ⋮ Existential Type Systems with No Types in Terms ⋮ Some undecidability results concerning the property of preserving regularity ⋮ Extending the type checker of Standard ML by polymorphic recursion ⋮ Typability and type checking in System F are equivalent and undecidable ⋮ Thue trees ⋮ Type inference with partial types

This page was built for publication: The undecidability of the semi-unification problem