Right-linear finite path overlapping term rewriting systems effectively preserve recognizability
Conclusion: A new class of TRS named finite path overlapping TRS (RLFPO-TRS) is proposed. It is shown that an RLFPO-TRS effectively preserves recognizability, and that the class properly includes known decidable classes of TRSs which effectively preserve recognizability. Approximations by the proposed class are also discussed. RLFPO-TRS does not include simple EPR-TRSs such that \(R= \{f(x)\to f(f(x))\}\). To construct a tree automaton \(M_*\) which accepts \(R^*(L(M))\) for a given tree automaton \(M\), we might need an operation which ``merges equivalent states of a tree automaton. For the entire collection see [Zbl 0941.00035].
- scientific article; zbMATH DE number 5708984
- Rewriting preserving recognizability of finite tree languages
- scientific article; zbMATH DE number 2090067
- Linear generalized semi-monadic rewrite systems effectively preserve recognizability
- A property of left-linear rewrite systems preserving recognizability
- Decidability for left-linear growing term rewriting systems.
- Term rewriting restricted to ground terms.
- A property of left-linear rewrite systems preserving recognizability
- Descendants of a recognizable tree language for prefix constrained linear monadic term rewriting with position cutting strategy
- Decidable call-by-need computations in term rewriting
- Context-sensitive rewriting strategies
- Right-linear half-monadic term rewrite systems
- Rewriting preserving recognizability of finite tree languages
- Non-linear rewrite closure and weak normalization
- Losing recognizability
- Some decidability results on one-pass reductions
- Tree automata for rewrite strategies
- Reachability analysis of innermost rewriting
- Innermost Reachability and Context Sensitive Reachability Properties Are Decidable for Linear Right-Shallow Term Rewriting Systems
- scientific article; zbMATH DE number 5708984 (Why is no real title available?)
- Unique Normalization for Shallow TRS
- TAGED Approximations for Temporal Properties Model-Checking
- scientific article; zbMATH DE number 2090067 (Why is no real title available?)
- Symbol different term rewrite systems
- Completeness of tree automata completion
- Closure of tree automata languages under innermost rewriting
- On proving soundness of the computationally equivalent transformation for normal conditional term rewriting systems by using unravelings
- Left-linear bounded TRSs are inverse recognizability preserving
- Reachability analysis over term rewriting systems
- Reducing non-occurrence of specified runtime errors to all-path reachability problems of constrained rewriting
- Ground approximations of term rewriting systems
- Termination criteria for tree automata completion
- Undecidable properties of flat term rewrite systems
- Descendants of a recognizable tree language for sets of linear monadic term rewrite rules
- Complete symbolic reachability analysis using back-and-forth narrowing
- Normalization properties for shallow TRS and innermost rewriting
- Murg term rewrite systems
This page was built for publication: Right-linear finite path overlapping term rewriting systems effectively preserve recognizability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2723905)
