The derivational complexity of string rewriting systems
type: Item
instance of: scholarly article
title: The derivational complexity of string rewriting systems
zbMATH Open document ID: 1247.68121
author: Yuji Kobayashi
published in: Theoretical Computer Science
publication date: 2012-08-08T00:00:00Z
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6064137
zbMATH Keywords: rewriting system
zbMATH Keywords: derivational complexity
zbMATH Keywords: Turing machine
zbMATH Keywords: time function
zbMATH Keywords: computable real number
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.02.037
OpenAlex ID: W2059807420
cites work: On the computational power of pushdown automata
cites work: Infinite string rewrite systems and complexity
cites work: Q4846257
cites work: Termination of rewriting
cites work: Some remarks on derivations in general rewriting systems
cites work: Termination proofs by multiset path orderings imply primitive recursive derivation lengths
cites work: Termination proofs and the length of derivations
cites work: An Approach to a Unified Theory of Automata
cites work: Isoperimetric and isodiametric functions of groups
cites work: Q4485693
DOI: 10.1016/J.TCS.2012.02.037
description: scientific article; zbMATH DE number 6064137