Linear unification

DOI10.1016/0022-0000(78)90043-0zbMath0371.68013OpenAlexW4213232664WikidataQ56092429 ScholiaQ56092429MaRDI QIDQ1243575

K. Appert

Publication date: 1978

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(78)90043-0

Mathematics Subject Classification ID

Related Items (84)

A new approach to general E-unification based on conditional rewriting systems ⋮ Effective codescent morphisms in the varieties determined by convergent term rewriting systems. ⋮ Free-variable semantic tableaux for the logic of fuzzy inequalities ⋮ A parallel algorithm for the monadic unification problem ⋮ Accelerating tableaux proofs using compact representations ⋮ Unification for infinite sets of equations between finite terms ⋮ Nominal unification ⋮ Linear unification of higher-order patterns ⋮ Incorporating equality into logic programming via surface deduction ⋮ The negation elimination from syntactic equational formula is decidable ⋮ Unification problems with one-sided distributivity ⋮ Computational complexity and constraint logic programming languages ⋮ Terminological reasoning is inherently intractable ⋮ On complexity of the anti-unification problem ⋮ About the Paterson-Wegman linear unification algorithm ⋮ On the tree-transformation power of XSLT ⋮ A practically efficient and almost linear unification algorithm ⋮ A rational reconstruction of the domain of feature structures ⋮ Decomposable theories ⋮ Complete symbolic reachability analysis using back-and-forth narrowing ⋮ Polymorphic type inference and containment ⋮ Finite generation of ambiguity in context-free languages ⋮ Data storage interpretation of labeled modal logic ⋮ Unification in sort theories and its applications ⋮ On the relationship of congruence closure and unification ⋮ Equational unification, word unification, and 2nd-order equational unification ⋮ On the Parameterized Complexity of Associative and Commutative Unification ⋮ Some complexity theoretic aspects of AC rewriting ⋮ Unification of drags and confluence of drag rewriting ⋮ Herbrand's fundamental theorem in the eyes of Jean van Heijenoort ⋮ The undecidability of the second-order unification problem ⋮ On the time and tape complexity of weak unification ⋮ Automatic theorem proving. II ⋮ Unnamed Item ⋮ Rigid E-unification: NP-completeness and applications to equational matings ⋮ Binary decision diagrams for first-order predicate logic. ⋮ Unifiability is complete for co-N Log Space ⋮ Unifications, deunifications, and their complexity ⋮ Horn clause programs with polymorphic types: Semantics and resolution ⋮ Refinement of bounds of the height of terms in the most general unifier ⋮ Heterogeneous active agents. III: Polynomially implementable agents ⋮ Optimal parallel algorithms for forest and term matching ⋮ Logic and functional programming by retractions : operational semantics ⋮ Using multiset discrimination to solve language processing problems without hashing ⋮ Graph unification and matching ⋮ Unification theory ⋮ Average-case analysis of unification algorithms ⋮ Complexity of unification problems with associative-commutative operators ⋮ A note on the parallel complexity of anti-unification ⋮ Projecting CLP(\({\mathcal R}\)) constraints ⋮ Tight complexity bounds for term matching problems ⋮ Equality and abductive residua for Horn clauses ⋮ C-expressions: A variable-free calculus for equational logic programming ⋮ The correctness of Newman's typability algorithm and some of its extensions ⋮ Automata-driven efficient subterm unification ⋮ Theory and practice of unparsed patterns for metacompilation ⋮ Referential logic of proofs ⋮ Proof schemata in Hilbert-type axiomatic theories ⋮ An almost linear Robinson unification algorithm ⋮ Unification in a combination of arbitrary disjoint equational theories ⋮ The single-conclusion proof logic and inference rules specification ⋮ On the parameterized complexity of associative and commutative unification ⋮ On Herbrand's theorem ⋮ Complete sets of transformations for general E-unification ⋮ A practical unification algorithm ⋮ Complete sets of unifiers and matchers in equational theories ⋮ On the logic of unification ⋮ An ordering linear unification algorithm ⋮ Unification problem in equational theories ⋮ On equational theories, unification, and (un)decidability ⋮ Context unification with one context variable ⋮ Source-tracking unification ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ A view of computability on term algebras ⋮ Fundamental properties of infinite trees ⋮ Automated theorem proving methods ⋮ Working with ARMs: Complexity results on atomic representations of Herbrand models ⋮ Faster linear unification algorithm ⋮ Distinct fringe subtrees in random trees ⋮ The complexity of type inference for higher-order typed lambda calculi ⋮ Simple second-order languages for which unification is undecidable ⋮ Semi-unification ⋮ Book review of: Matthias Baaz and Alexander Leitsch, Methods of cut-elimination ⋮ Properties of substitutions and unifications

Cites Work

• Unnamed Item
• Efficiency of a Good But Not Linear Set Union Algorithm

This page was built for publication: Linear unification