Lambda-confluence for context rewriting systems
DOI10.1016/j.tcs.2015.01.013zbMath1319.68129OpenAlexW2025943894MaRDI QIDQ2344748
Friedrich Otto, František Mráz
Publication date: 18 May 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.01.013
decidabilitylimited context restarting automaton\(\lambda\)-confluenceclearing restarting automatoncontext rewriting systemfactor-erasing string-rewriting system
Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Turing machines and related notions (03D10)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of 2-monotone restarting automata
- An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
- Some undecidability results for non-monadic Church-Rosser Thue systems
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- McNaughton families of languages.
- Undecidable questions related to Church-Rosser Thue systems
- Don't Care Non-determinism in Logic Program Refinement
- On the classes of languages accepted by limited context restarting automata
- Clearing Restarting Automata
- Learning Analysis by Reduction from Positive Data
- Church-Rosser Thue systems and formal languages
- A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors
- The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
- Restarting automata
- Lambda-Confluence Is Undecidable for Clearing Restarting Automata
This page was built for publication: Lambda-confluence for context rewriting systems
