On rewrite constraints and context unification

DOI10.1016/S0020-0190(00)00036-3zbMath1014.68076MaRDI QIDQ1607044

Ralf Treinen, Joachim Niehren, Sophie Tison

Publication date: 25 July 2002

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

zbMATH Keywords

rewriting constraintsstratified context unification

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items

Dominance constraints in stratified context unification, Decidability of bounded higher-order unification, The Existential Fragment of the One-Step Parallel Rewriting Theory

Cites Work

• Bi-rewrite systems
• Decidability of unification in the theory of one-sided distributivity and a multiplicative unit
• The undecidability of the second-order unification problem
• Completion of rewrite systems with membership constraints. I: Deduction rules
• Solvability of context equations with two context variables is decidable
• Decidability of bounded second order unification
• Undecidability of the first order theory of one-step right ground rewriting
• The first-order theory of one step rewriting in linear noetherian systems is undecidable
• Encompassment properties and automata with constraints
• The first-order theory of one-step rewriting is undecidable
• Linear second-order unification
• On equality up-to constraints over finite trees, context unification, and one-step rewriting
• Grid structures and undecidable constraint theories
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item