A polynomial algorithm testing partial confluence of basic semi-Thue systems
From MaRDI portal
Publication:1127336
Recommendations
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- Rewriting systems and word problems in a free partially commutative monoid
- scientific article; zbMATH DE number 1418332
- scientific article; zbMATH DE number 1615237
- Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems
Cites work
- scientific article; zbMATH DE number 3871338 (Why is no real title available?)
- scientific article; zbMATH DE number 3684913 (Why is no real title available?)
- scientific article; zbMATH DE number 3788014 (Why is no real title available?)
- scientific article; zbMATH DE number 176741 (Why is no real title available?)
- scientific article; zbMATH DE number 3612461 (Why is no real title available?)
- scientific article; zbMATH DE number 1142316 (Why is no real title available?)
- scientific article; zbMATH DE number 789389 (Why is no real title available?)
- scientific article; zbMATH DE number 3430632 (Why is no real title available?)
- A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors
- A characterisation of deterministic context-free languages by means of right-congruences
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- An algebraic theory of graph reduction
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Efficient string matching
- Finite-Turn Pushdown Automata
- Infinite regular Thue systems
- It is decidable whether a monadic thue system is canonical over a regular set
- Monadic Thue systems
- NTS languages are deterministic and congruential
- On deciding the confluence of a finite string-rewriting system on a given congruence class
- On weakly confluent monadic string-rewriting systems
- Some decision problems about controlled rewriting systems
- The equivalence and inclusion problems for NTS languages
- The equivalence of pre-NTS grammars is decidable
- The equivalence problem for deterministic finite-turn pushdown automata
- The equivalence problem for deterministic pushdown automata is decidable
- The equivalence problem of multitape finite automata
- The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
Cited in
(6)- LARS: a learning algorithm for rewriting systems
- Rational subsets of partially reversible monoids
- Lambda-confluence for context rewriting systems
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- A Polynomial-Time Algorithm to Check Closedness of Simple Second Order Mixed-Integer Sets
- \(L(A)=L(B)\)? decidability results from complete formal systems
This page was built for publication: A polynomial algorithm testing partial confluence of basic semi-Thue systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1127336)
