On rewrite constraints and context unification

DOI10.1016/S0020-0190(00)00036-3MaRDI QIDQ1607044zbMATH OpenFDO

Authors Joachim Niehren, Sophie Tison, Ralf Treinen

Publication date 25 July 2002

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0020-0190(00)00036-3

zbMATH Keywords

rewriting constraintsstratified context unification

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• A Decision Algorithm for Stratified Context Unification
• scientific article; zbMATH DE number 1841840
• 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
• Stratified Context Unification Is NP-Complete

Cites work

• Bi-rewrite systems
• Completion of rewrite systems with membership constraints. I: Deduction rules
• Decidability of bounded second order unification
• Decidability of unification in the theory of one-sided distributivity and a multiplicative unit
• Encompassment properties and automata with constraints
• Grid structures and undecidable constraint theories
• scientific article; zbMATH DE number 1689586 (Why is no real title available?)
• scientific article; zbMATH DE number 3590511 (Why is no real title available?)
• scientific article; zbMATH DE number 1405621 (Why is no real title available?)
• scientific article; zbMATH DE number 1405622 (Why is no real title available?)
• Linear second-order unification
• On equality up-to constraints over finite trees, context unification, and one-step rewriting
• Solvability of context equations with two context variables is decidable
• The first-order theory of one step rewriting in linear noetherian systems is undecidable
• The first-order theory of one-step rewriting is undecidable
• The undecidability of the second-order unification problem
• Undecidability of the first order theory of one-step right ground rewriting

Cited in

(7)

• Decidability of bounded higher-order unification
• The Existential Fragment of the One-Step Parallel Rewriting Theory
• scientific article; zbMATH DE number 1841840 (Why is no real title available?)
• A Decision Algorithm for Stratified Context Unification
• On equality up-to constraints over finite trees, context unification, and one-step rewriting
• scientific article; zbMATH DE number 6744203 (Why is no real title available?)
• Dominance constraints in stratified context unification

This page was built for publication: On rewrite constraints and context unification

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