Lambda-confluence for context rewriting systems

DOI10.1016/J.TCS.2015.01.013MaRDI QIDQ2344748zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

\(\lambda\)-confluenceclearing restarting automatoncontext rewriting systemdecidabilityfactor-erasing string-rewriting systemlimited context restarting automaton

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• 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

Cites work

• 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

Cited in

(3)

• Context Update for Lambdas and Vectors
• Lambda-confluence is undecidable for clearing restarting automata
• Logical Aspects of Computational Linguistics

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)