On a method for proving exact bounds on derivational complexity in Thue systems

DOI10.1134/S0001434612070012zbMath1285.03047OpenAlexW2081016988MaRDI QIDQ1938620

S. I. Adyan

Publication date: 22 February 2013

Published in: Mathematical Notes (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0001434612070012

zbMATH Keywords

derivational complexityThue systemleft (right) divisibility of a wordpolynomial upper boundword rewriting system

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Thue and Post systems, etc. (03D03)

Related Items (7)

On Subquadratic Derivational Complexity of Semi-Thue Systems ⋮ Ideal gas/liquid transition as a generalization of the problem of ``partitio numerorum ⋮ The mathematical theory of classical thermodynamics ⋮ The Burnside problem on periodic groups and related questions. ⋮ The normalizers of free subgroups in free Burnside groups of odd period \(n\geq 1003\). ⋮ Questions in algebra and mathematical logic. Scientific heritage of S. I. Adian ⋮ On subsemigroup lattices of aperiodic groups

Cites Work

• Termination of \(\{aa\rightarrow bc,bb\rightarrow ac,cc\rightarrow ab\}\)
• Complexity of Guided Insertion-Deletion in RNA-Editing

This page was built for publication: On a method for proving exact bounds on derivational complexity in Thue systems