On Subquadratic Derivational Complexity of Semi-Thue Systems

DOI10.1007/978-3-030-50026-9_28OpenAlexW3036204048MaRDI QIDQ5042260

Alexey Talambutsa

Publication date: 19 October 2022

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-50026-9_28

zbMATH Keywords

rewriting systemsemi-Thue systemderivational complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• The derivational complexity of string rewriting systems
• Termination of \(\{aa\rightarrow bc,bb\rightarrow ac,cc\rightarrow ab\}\)
• There is only one gap in the isoperimetric spectrum
• Polynomially-bounded Dehn functions of groups
• Isoperimetric and isodiametric functions of groups
• On a method for proving exact bounds on derivational complexity in Thue systems
• HYPERBOLICITY OF GROUPS WITH SUBQUADRATIC ISOPERIMETRIC INEQUALITY
• Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
• Termination proofs and the length of derivations

This page was built for publication: On Subquadratic Derivational Complexity of Semi-Thue Systems