The derivational complexity of string rewriting systems

DOI10.1016/j.tcs.2012.02.037zbMath1247.68121OpenAlexW2059807420MaRDI QIDQ441853

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

zbMATH Keywords

Turing machinerewriting systemcomputable real numbertime functionderivational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Related Items (1)

On Subquadratic Derivational Complexity of Semi-Thue Systems

Cites Work

• Unnamed Item
• Unnamed Item
• Termination of rewriting
• Termination proofs by multiset path orderings imply primitive recursive derivation lengths
• Infinite string rewrite systems and complexity
• Isoperimetric and isodiametric functions of groups
• On the computational power of pushdown automata
• Termination proofs and the length of derivations
• An Approach to a Unified Theory of Automata
• Some remarks on derivations in general rewriting systems

This page was built for publication: The derivational complexity of string rewriting systems