A polynomial algorithm testing partial confluence of basic semi-Thue systems
From MaRDI portal
Publication:1127336
DOI10.1016/S0304-3975(97)00145-XzbMath0908.68108WikidataQ128037015 ScholiaQ128037015MaRDI QIDQ1127336
Publication date: 13 August 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (4)
Rational subsets of partially reversible monoids ⋮ LARS: a learning algorithm for rewriting systems ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ Lambda-confluence for context rewriting systems
Cites Work
- 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
- Monadic Thue systems
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- 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
- Efficient string matching
- An algebraic theory of graph reduction
- The equivalence problem for deterministic pushdown automata is decidable
- The equivalence problem for deterministic finite-turn pushdown automata
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- Finite-Turn Pushdown Automata
This page was built for publication: A polynomial algorithm testing partial confluence of basic semi-Thue systems
