The derivational complexity of string rewriting systems
From MaRDI portal
Publication:441853
DOI10.1016/J.TCS.2012.02.037zbMATH Open1247.68121OpenAlexW2059807420MaRDI QIDQ441853FDOQ441853
Authors: Yuji Kobayashi 
Publication date: 8 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.037
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
- Title not available (Why is that?)
- On the computational power of pushdown automata
- Termination proofs and the length of derivations
- Termination of rewriting
- Title not available (Why is that?)
- Infinite string rewrite systems and complexity
- Isoperimetric and isodiametric functions of groups
- Termination proofs by multiset path orderings imply primitive recursive derivation lengths
- An Approach to a Unified Theory of Automata
- Some remarks on derivations in general rewriting systems
Cited In (9)
- On a method for proving exact bounds on derivational complexity in Thue systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Derivational complexity is an invariant cost model
- Title not available (Why is that?)
- On Subquadratic Derivational Complexity of Semi-Thue Systems
- Upper bound on the derivational complexity in some word rewriting system
- Title not available (Why is that?)
- Title not available (Why is that?)
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)
