The derivational complexity of string rewriting systems
From MaRDI portal
Recommendations
- Termination and derivational complexity of confluent one-rule string-rewriting systems
- A complete characterization of termination of \(0^p1^q\to 1^r0^s\)
- Infinite string rewrite systems and complexity
- A complete characterization of termination of 0p 1q→1r 0s
- Derivational complexity is an invariant cost model
Cites work
- scientific article; zbMATH DE number 1460545 (Why is no real title available?)
- scientific article; zbMATH DE number 789389 (Why is no real title available?)
- An Approach to a Unified Theory of Automata
- Infinite string rewrite systems and complexity
- Isoperimetric and isodiametric functions of groups
- On the computational power of pushdown automata
- Some remarks on derivations in general rewriting systems
- Termination of rewriting
- Termination proofs and the length of derivations
- Termination proofs by multiset path orderings imply primitive recursive derivation lengths
Cited in
(9)- On a method for proving exact bounds on derivational complexity in Thue systems
- scientific article; zbMATH DE number 5788680 (Why is no real title available?)
- scientific article; zbMATH DE number 2087241 (Why is no real title available?)
- Derivational complexity is an invariant cost model
- scientific article; zbMATH DE number 1860714 (Why is no real title available?)
- On Subquadratic Derivational Complexity of Semi-Thue Systems
- Upper bound on the derivational complexity in some word rewriting system
- scientific article; zbMATH DE number 1324448 (Why is no real title available?)
- scientific article; zbMATH DE number 6819785 (Why is no real title available?)
This page was built for publication: The derivational complexity of string rewriting systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q441853)
