Geodesic
On a Method for Proving Exact Bounds on Derivational Complexity in Thue Systems
Matematičeskie zametki, Tome 92 (2012) no. 1, pp. 3-18.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, the following system of substitutions in a $3$-letter alphabet $$ \mathbf\Sigma=\langle a,b,c\mid a^2 \to bc,\,b^2\to ac,\,c^2\to ab\rangle $$ is considered. A detailed proof of results that were described briefly in the author's paper [1] is presented. They give an answer to the specific question on the possibility of giving a polynomial upper bound for the lengths of derivations from a given word in the system $\mathbf\Sigma$ stated in the literature. The maximal possible number of steps in derivation sequences starting from a given word $W$ is denoted by $\mathbf D(W)$. The maximum of $\mathbf D(W)$ for all words of length $|W|=l$ is denoted by $\mathbf D(l)$. It is proved that the function $\mathbf D(W)$ on words $W$ of given length $|W|=m+2$ reaches its maximum only on words of the form $W=c^2b^m$ and $W=b^ma^2$. For these words, the following precise estimate is established: $$ \mathbf D(m+2)=\mathbf D(c^2b^m)=\mathbf D(b^ma^2) =\biggl\rceil\frac{3m^2}{2}\biggr\lceil+m+1\frac{3(m+1)^2}{2}, $$ where $\lceil{3m^2}/{2}\rceil$ for odd $|m|$ is the round-up of ${3m^2}/{2}$ to the nearest integer.
Keywords: word rewriting system, derivational complexity, Thue system, polynomial upper bound, left (right) divisibility of a word. 
@article{MZM_2012_92_1_a0,
     author = {S. I. Adian},
     title = {On a {Method} for {Proving} {Exact} {Bounds} on {Derivational} {Complexity} in {Thue} {Systems}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {3--18},
     publisher = {mathdoc},
     volume = {92},
     number = {1},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2012_92_1_a0/}
}
TY  - JOUR
AU  - S. I. Adian
TI  - On a Method for Proving Exact Bounds on Derivational Complexity in Thue Systems
JO  - Matematičeskie zametki
PY  - 2012
SP  - 3
EP  - 18
VL  - 92
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2012_92_1_a0/
LA  - ru
ID  - MZM_2012_92_1_a0
ER  - 
%0 Journal Article
%A S. I. Adian
%T On a Method for Proving Exact Bounds on Derivational Complexity in Thue Systems
%J Matematičeskie zametki
%D 2012
%P 3-18
%V 92
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2012_92_1_a0/
%G ru
%F MZM_2012_92_1_a0
S. I. Adian. On a Method for Proving Exact Bounds on Derivational Complexity in Thue Systems. Matematičeskie zametki, Tome 92 (2012) no. 1, pp. 3-18. http://geodesic.mathdoc.fr/item/MZM_2012_92_1_a0/

[1] S. I. Adyan, “Otsenka slozhnosti vyvoda v odnoi sisteme podstanovok”, Dokl. RAN, 428:3 (2009), 295–299 | MR | Zbl

[2] D. Hofbauer, J. Waldmann, “Termination of $\{aa\to bc,\,bb\to ac,\,cc\to ab\}$”, Inform. Process. Lett., 98:4 (2006), 156–158 | MR | Zbl

[3] S. I. Adyan, “Opredelyayuschie sootnosheniya i algoritmicheskie problemy dlya grupp i polugrupp”, Tr. MIAN SSSR, 85, M., 1966, 3–123 | MR | Zbl

[4] S. I. Adyan, Problema Bernsaida i tozhdestva v gruppakh, Nauka, M., 1975 | MR | Zbl

[5] H. Zantema, “Complexity of guided insertion-deletion in RNA-editing”, Language and Automata Theory and Applications, Lecture Notes in Comput. Sci., 6031, Springer-Verlag, Berlin, 2010, 608–619 | MR | Zbl