D:\User\sbornik_38_pdf\1.DVI


Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè è âû÷èñëèòåëüíîé òåõíèêè 38, 7, 2012.

Î ìåòîäå íàõîæäåíèÿ òî÷íûõ îöåíîê äëèí âûâîäîâ
â ñèñòåìàõ Òóý

Ñ. È. Àäÿí
Ìàòåìàòè÷åñêèé èíñòèòóò èì. Â.À.Ñòåêëîâà ÐÀÍ

E-mail: sia@mi.ras.ru

 äîêëàäå ðàññìàòðèâàåòñÿ ñèñòåì îäíîñòîðîííèõ ïîäñòàíîâîê Òóý â àëôàâèòå èç
òðåõ áóêâ

§ = ha; b; c j a2 ! bc; b2 ! ac; c2 ! abi: ( 1 )
 ýòîé ñèñòåìå § äîïóñêàþòñÿ ïîäñòàíîâêè âèäà

Xa2Y ! XbcY; Xb2Y ! XacY; Xc2Y ! XabY; ( 2 )

ãäå X, Y – ïðîèçâîëüíûå ñëîâà.

 çàìåòêå [1] Ä.Õîôìàíà è Äæ.Âàëäìàíà áûëî äîêàçàíî, ÷òî äëÿ ëþáîãî ñëîâà W
íà÷èíàþùàÿñÿ ñ íåãî öåïî÷êà âûâîäà ñèñòåìû § îáðûâàåòñÿ, ò.å. ÷åðåç êîíå÷íîå
÷èñëî øàãîâ ïîëó÷àåòñÿ ñëîâî, ê êîòîðîìó íå ïðèìåíèìà íè îäíà èç òðåõ ïîäñòàíîâîê.
Äîêàçàòåëüñòâî ýòîãî ðåçóëüòàòà ïîçâîëèëî àâòîðàì äàòü ýêñïîíåíöèàëüíóþ âåðõíþþ
îöåíêó ìàêñèìàëüíî âîçìîæíîé äëèíû âûâîäà äëÿ äàííîãî èñõîäíîãî ñëîâà. Áûë
ïîñòàâëåí âîïðîñ î ñóùåñòâîâàíèè ïîëèíîìèàëüíîé âåðõíåé îöåíêè ýòîé ôóíêöèè.

Ìû äîêàçûâàåì, ÷òî ìàêñèìàëüíàÿ äëèíà D( W) öåïî÷êè âûâîäà, íà÷èíàþùåéñÿ ñî
ñëîâà W , íà ìíîæåñòâå âñåõ ñëîâ äàííîé äëèíû jW j = m+2 äîñòèãàåò ñâîåãî ìàêñèìóìà
òîëüêî íà ñëîâàõ âèäà W = c2bm è W = bma2.

Âû÷èñëåíî òî÷íîå çíà÷åíèå ôóíêöèè D( c2bm ) = D( bma2 ) . Îíî ðàâíî 3
2
m2 + m + 1

ïðè m = 2 t; è 3
2
m2 + m + 3

2
ïðè m = 2 t + 1 .

Ïîäðîáíîå äîêàçàòåëüñòâî ýòîãî ðåçóëüòàòà îïóáëèêîâàíî â ñòàòüå äîêëàä÷èêà [2].

Ñïèñîê ëèòåðàòóðû

[1] D. Hofbauer, J. Waldmann. Termination of fa2 ! bc; b2 ! ac; c2 ! abg. Information
Processing Letters, Vol. 98, Issue 4, May 2006.

[2] Ñ. È. Àäÿí, “Î ìåòîäå íàõîæäåíèÿ òî÷íûõ îöåíîê äëèí âûâîäîâ â ñèñòåìàõ Òóý”,
Ìàòåì. çàìåòêè, 92:1 (2012), 3–18.

[3] Ñ. È. Àäÿí. ”Îïðåäåëÿþùèå ñîîòíîøåíèÿ è àëãîðèòìè÷åñêèå ïðîáëåìû äëÿ ãðóïï
è ïîëóãðóïï”. Òðóäû ÌÈÀÍ ÑÑÑÐ, 1966, ò. bf85.

7