Deciding context unification

DOI10.1145/3356904zbMATH Open1473.68103OpenAlexW2980901358WikidataQ127014603 ScholiaQ127014603MaRDI QIDQ5215468FDOQ5215468

Authors: Artur Jeż 

Publication date: 11 February 2020

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3356904

Recommendations

• Context unification is in PSPACE
• Deciding context unification (with regular constraints)
• Solvability of context equations with two context variables is decidable
• scientific article; zbMATH DE number 1341608
• scientific article; zbMATH DE number 1722705

zbMATH Keywords

term rewritingsecond-order unificationcontext unification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Decidability of theories and sets of sentences (03B25)

Cited In (13)

• Title not available (Why is that?)
• Unification with Singleton Tree Grammars
• Automated Deduction – CADE-20
• Title not available (Why is that?)
• Context unification is in PSPACE
• Two-restricted one context unification is in polynomial time
• One context unification problems solvable in polynomial time
• Context unification with one context variable
• Title not available (Why is that?)
• Word equations in non-deterministic linear space
• Deciding context unification (with regular constraints)
• A Decision Algorithm for Stratified Context Unification
• One-context unification with STG-compressed terms is in NP

This page was built for publication: Deciding context unification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215468)