A polynomial algorithm testing partial confluence of basic semi-Thue systems
From MaRDI portal
Publication:5055831
DOI10.1007/3-540-59200-8_57zbMath1503.68154OpenAlexW1524320637MaRDI QIDQ5055831
Publication date: 9 December 2022
Published in: Rewriting Techniques and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-59200-8_57
Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Thue and Post systems, etc. (03D03)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On weakly confluent monadic string-rewriting systems
- The equivalence problem of multitape finite automata
- Some decision problems about controlled rewriting systems
- A characterisation of deterministic context-free languages by means of right-congruences
- The equivalence and inclusion problems for NTS languages
- NTS languages are deterministic and congruential
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
- Monadic Thue systems
- Infinite regular Thue systems
- It is decidable whether a monadic thue system is canonical over a regular set
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors
- The equivalence of pre-NTS grammars is decidable
- The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
- An algebraic theory of graph reduction
- Finite-Turn Pushdown Automata
