Stratified context unification is in PSPACE

DOI10.1007/3-540-44802-0_35MaRDI QIDQ4783328zbMATH OpenFDO

Authors Manfred Schmidt-Schauß

Publication date 4 December 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2142/21420498

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A Decision Algorithm for Stratified Context Unification
• Stratified Context Unification Is NP-Complete
• On rewrite constraints and context unification
• On the complexity of bounded second-order unification and stratified context unification
• On equality up-to constraints over finite trees, context unification, and one-step rewriting

Cited in

(8)

• On rewrite constraints and context unification
• The complexity of linear and stratified context matching problems
• Decidability of bounded higher-order unification
• On the complexity of bounded second-order unification and stratified context unification
• Stratified Context Unification Is NP-Complete
• A Decision Algorithm for Stratified Context Unification
• Context unification is in PSPACE
• On equality up-to constraints over finite trees, context unification, and one-step rewriting

This page was built for publication: Stratified context unification is in PSPACE

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