Deciding context unification

DOI10.1145/3356904MaRDI QIDQ5215468zbMATHOpenAlexWikidataFDO

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

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)

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

Cited in

(13)

• Context unification with one context variable
• One context unification problems solvable in polynomial time
• scientific article; zbMATH DE number 1189059 (Why is no real title available?)
• Unification with Singleton Tree Grammars
• Deciding context unification (with regular constraints)
• Context unification is in PSPACE
• scientific article; zbMATH DE number 1722705 (Why is no real title available?)
• scientific article; zbMATH DE number 1615236 (Why is no real title available?)
• Automated Deduction – CADE-20
• Word equations in non-deterministic linear space
• One-context unification with STG-compressed terms is in NP
• A Decision Algorithm for Stratified Context Unification
• Two-restricted one context unification is in polynomial time

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)