Lambda-confluence for context rewriting systems
In a context rewriting system \(C = (\Sigma,\Gamma,I)\), \(\Gamma\) is a finite working alphabet that contains the input alphabet \(\Sigma\) as a subset, but neither \(\#\) nor \(\$ \), and \(I\) is a finite set of instructions \((x \mid z \rightarrow t \mid y)\), where \(x\in \Gamma^* \cup \#\Gamma^*\), \(y \in \Gamma^* \cup \Gamma^* \$\), and \(z,t \in \Gamma^*\). A word \(uzv\) can be rewritten as \(utv\) using the instruction \((x \mid z \rightarrow t \mid y)\) if \(x\) is a suffix of \(\# u\) and \(y\) is a prefix of \(v\$\). The language accepted by \(C\) consists of the words over \(\Sigma\) that can be reduced to the empty word \(\lambda\). The authors consider three special types of such systems defined by various restrictions on the instructions allowed, namely limited context restarting automata (lc-R-automata) of types \(\mathcal{R}_1\) and \(\mathcal{R}_2\), and clearing restarting automata. In all three cases the membership problem is decidable, with \(\mathrm{NTIME}(n^2)\) as an upper complexity bound, because all rewriting steps are length-reducing. However, the time complexity becomes linear if the system is \(\lambda\)-confluent, i.e., confluent in the equivalence class of the empty word. It is shown that \(\lambda\)-confluence is decidable in polynomial time for type-\(\mathcal{R}_2\) lc-R-automata, but not even recursively enumerable for clearing restarting automata or type-\(\mathcal{R}_1\) lc-R-automata. Context rewriting systems are closely related to string rewriting systems, and the main theorem of the paper, from which the above two undecidability results also follow, states that \(\lambda\)-confluence is not recursively enumerable for finite factor-erasing string rewriting systems.
- Lambda-confluence is undecidable for clearing restarting automata
- The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
- On deciding confluence of finite string-rewriting systems modulo partial commutativity
- Termination and derivational complexity of confluent one-rule string-rewriting systems
- Confluence of prefix-constrained rewrite systems
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors
- An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
- Church-Rosser Thue systems and formal languages
- Clearing restarting automata
- Don't care non-determinism in logic program refinement
- scientific article; zbMATH DE number 3664336 (Why is no real title available?)
- scientific article; zbMATH DE number 2087223 (Why is no real title available?)
- scientific article; zbMATH DE number 789389 (Why is no real title available?)
- scientific article; zbMATH DE number 1394484 (Why is no real title available?)
- Lambda-confluence is undecidable for clearing restarting automata
- Learning Analysis by Reduction from Positive Data
- McNaughton families of languages.
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- On the classes of languages accepted by limited context restarting automata
- On the complexity of 2-monotone restarting automata
- Restarting automata
- Some undecidability results for non-monadic Church-Rosser Thue systems
- The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
- Undecidable questions related to Church-Rosser Thue systems
This page was built for publication: Lambda-confluence for context rewriting systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344748)
