Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
From MaRDI portal
Publication:918215
DOI10.1016/0890-5401(90)90015-AzbMath0705.68067MaRDI QIDQ918215
Sophie Tison, Thierry Heuillard, Pierre Lescanne, Max Dauchet
Publication date: 1990
Published in: Information and Computation (Search for Journal in Brave)
Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42) Thue and Post systems, etc. (03D03)
Related Items (34)
Bottom-up tree pushdown automata: Classification and connection with rewrite systems ⋮ Monadic second-order definable graph transductions: a survey ⋮ Deciding confluence of certain term rewriting systems in polynomial time ⋮ Fair termination is decidable for ground systems ⋮ Decidability of confluence and termination of monadic term rewriting systems ⋮ Open problems in rewriting ⋮ More problems in rewriting ⋮ Problems in rewriting III ⋮ Decidable approximations of term rewriting systems ⋮ Linear generalized semi-monadic rewrite systems effectively preserve recognizability ⋮ Rewriting higher-order stack trees ⋮ Path resolution for nested recursive modules ⋮ First-order theory of rewriting for linear variable-separated rewrite systems: automation, formalization, certification ⋮ Intersection of finitely generated congruences over term algebra ⋮ Term rewriting restricted to ground terms. ⋮ On ground tree transformations and congruences induced by tree automata. ⋮ Levels of undecidability in rewriting ⋮ Symbol different term rewrite systems ⋮ Verification of well-formed communicating recursive state machines ⋮ New Undecidability Results for Properties of Term Rewrite Systems ⋮ Decidable call-by-need computations in term rewriting ⋮ Bottom-up rewriting for words and terms ⋮ A fast algorithm for constructing a tree automaton recognizing a congruential tree language ⋮ Reachability and confluence are undecidable for flat term rewriting systems ⋮ The $\Pi^0_2$ -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity) ⋮ The Reachability Problem over Infinite Graphs ⋮ Handling Left-Quadratic Rules When Completing Tree Automata ⋮ CHAP and rewrite components ⋮ Decidable call by need computations in term rewriting (extended abstract) ⋮ Congruential complements of ground term rewrite systems ⋮ Decidability and complexity of simultaneous rigid E-unification with one variable and related results ⋮ RIGID REACHABILITY, THE NON-SYMMETRIC FORM OF RIGID E-UNIFICATION ⋮ Restricted ground tree transducers ⋮ Derivation trees of ground term rewriting systems.
Cites Work
This page was built for publication: Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems
