Lyndon so'zi - Lyndon word - Wikipedia

Yilda matematika, hududlarida kombinatorika va Kompyuter fanlari, a Lyndon so'zi bo'sh emas mag'lubiyat bu juda kichikroq leksikografik tartib hammasiga qaraganda aylanishlar. Lindon so'zlari matematik nomiga berilgan Rojer Lindon, ularni 1954 yilda tergov qilgan, ularni chaqirgan standart leksikografik ketma-ketliklar.[1] Anatoliy Shirshov 1953 yilda Lyndon so'zlarini ularni chaqirgan holda tanishtirdi muntazam so'zlar.[2] Lyndon so'zlari - bu alohida holat Zal so'zlari; Lyndon so'zlarining deyarli barcha xususiyatlari Hall so'zlari bilan o'rtoqlashadi.

Ta'riflar

Bir nechta teng ta'riflar mavjud.

A k-ary Lyndon so'zi n > 0 - bu n- belgi mag'lubiyat ustidan alifbo hajmi k, va bu noyob noyob element leksikografik buyurtma ichida multiset uning barcha aylanishlarini. Yakkama-yakka aylanish, Lindon so'zining ahamiyatsiz aylanishlaridan farq qilishi va shuning uchun aperiodic bo'lishini anglatadi.[3]

Shu bilan bir qatorda, bir so'z w Lindon so'zi, agar u bo'sh va leksikografik jihatdan uning tegishli qo'shimchalaridan qat'iyan kichikroq bo'lsa, ya'ni w < v barcha bo'sh bo'lmagan so'zlar uchun v shu kabi w = uv va siz bo'sh emas.

Boshqa bir tavsiflash quyidagicha: Lyndon so'zi bo'sh emasligi xususiyatiga ega va har doim ikkita bo'sh satrga bo'linib ketganda, chap satr har doim leksikografik jihatdan o'ng pastki satrdan kam bo'ladi. Ya'ni, agar w bu Lindon so'zi va w = uv bilan ikkita satrga har qanday faktorizatsiya siz va v bo'sh bo'lmagan deb tushundi, keyin siz < v. Ushbu ta'rif mag'lubiyatni anglatadi w uzunligi ≥ 2 - bu Lindon so'zi, agar Lindon so'zlari mavjud bo'lsa siz va v shu kabi siz < v va w = uv.[4] Bir nechta tanlov bo'lishi mumkin bo'lsa-da siz va v ushbu xususiyat bilan, deb nomlangan ma'lum bir tanlov mavjud standart faktorizatsiya, unda v iloji boricha uzoqroq.[5]

Hisoblash

Ikki belgili ikkilik alfavitdagi {0,1} Lyndon so'zlari uzunlik bo'yicha saralangan va keyin har bir uzunlik sinfi ichida leksikografik jihatdan boshlangan cheksiz ketma-ketlikni hosil qiladi.

0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ...

Ushbu ketma-ketlikka tegishli bo'lmagan birinchi qator "00" davriy bo'lgani uchun chiqarib tashlanadi (u "0" pastki satrining ikki marta takrorlanishidan iborat); ikkinchi tashlab qo'yilgan "10" qatori aperiodic, ammo uning almashtirish sinfida minimal emas, chunki u kichikroq "01" qatoriga tsiklik ravishda o'rnatilishi mumkin.

Bo'sh satr, shuningdek, Lyndon so'zining nol uzunlikdagi ta'rifiga javob beradi. Ikkala uzunlikdagi Lindon so'zlarining ikkala uzunlikdagi nol uzunligidan boshlangan so'zlari butun sonli ketma-ketlik

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... (ketma-ketlik A001037 ichida OEIS )

Lyndon so'zlari aperiodic bilan mos keladi marjon sinf vakillari va shu bilan hisoblashish mumkin Moroning marjonlarni hisoblash funktsiyasi.[3][6]

Avlod

Duval (1988) samaradorlikni ta'minlaydi algoritm Lindonning uzun so'zlarini ro'yxati uchun n berilgan alfavit kattaligi bilan s yilda leksikografik tartib. Agar w ketma-ketlikdagi so'zlardan biri, keyin keyingi so'z w quyidagi bosqichlarda topish mumkin:

  1. Belgilarni takrorlang w yangi so'z hosil qilish x uzunligi aniq n, qaerda menning belgisi x holatidagi belgi bilan bir xil (men mod uzunligi (w)) ning w.
  2. Ning oxirgi belgisi ekan x alifboning tartiblangan tartibidagi oxirgi belgi bo'lib, uni olib tashlang va qisqartirilgan so'z hosil qiling.
  3. Ning oxirgi qolgan belgisini almashtiring x alifboning tartiblangan tartibida uning vorisi tomonidan.

So'zning vorisini yaratish uchun eng yomon vaqt w ushbu protsedura bo'yicha O (nAmmo, agar yaratilgan so'zlar an ichida saqlansa qator uzunlik nva qurilish x dan w oxiriga belgi qo'shish orqali amalga oshiriladi w o'rniga yangi nusxasini yaratish orqali w, keyin vorisni yaratish uchun o'rtacha vaqt w (har bir so'z teng ehtimollik bilan) doimiydir. Shunday qilib, barcha Lindon so'zlarining ketma-ketligi ko'pi bilan n ketma-ketlik uzunligiga mutanosib vaqt ichida hosil bo'lishi mumkin.[7] Ushbu ketma-ketlikdagi so'zlarning doimiy qismi to'liq uzunlikka ega n, shuning uchun xuddi shu protsedura yordamida uzunlikdagi so'zlarni samarali ravishda yaratish mumkin n yoki uzunligi bo'linadigan so'zlar n, ushbu mezonlarga mos kelmaydigan yaratilgan so'zlarni filtrlash orqali.

Standart faktorizatsiya

Ga ko'ra Chen-Foks-Lindon teoremasi, har bir mag'lubiyat Lindon so'zlari ketma-ketligini biriktirish orqali o'ziga xos tarzda tuzilishi mumkin, shunday qilib ketma-ketlikdagi so'zlar leksikografik jihatdan ko'paytirilmaydi.[8] Ushbu ketma-ketlikdagi so'nggi Lindon so'zi ushbu qatorning leksikografik jihatdan eng kichik qo'shimchasidir.[9] Lindon so'zlarining ko'payib ketmaydigan ketma-ketligiga faktorizatsiya (Lindon faktorizatsiyasi deb ataladigan) quyidagicha tuzilishi mumkin. chiziqli vaqt.[9] Lindon faktorizatsiyalari .ning biekativ variantining bir qismi sifatida ishlatilishi mumkin Burrows-Wheeler konvertatsiyasi uchun ma'lumotlarni siqish,[10] va uchun algoritmlarda raqamli geometriya.[11]

Bunday faktorizatsiyani cheklangan ikkilik daraxtlar sifatida yozish mumkin, barglari alifbo bilan belgilanadi va har bir o'ng tomonga ketma-ketlikda oxirgi Lindon so'zi beriladi.[12] Bunday daraxtlarni ba'zan chaqirishadi standart qavslar va a elementlarining faktorizatsiyasi sifatida qabul qilinishi mumkin bepul guruh yoki a uchun asosiy elementlar sifatida bepul algebra. Ushbu daraxtlar alohida holatdir Zal daraxtlari (Lyndon so'zlari Hall so'zlarining alohida hodisasi bo'lgani kabi) va shunga o'xshash Hall so'zlari standart tartibni ta'minlaydi, kommutatorni yig'ish jarayoni guruhlar uchun va yolg'on algebralari uchun asos.[13][14][15]Haqiqatan ham, ular paydo bo'lgan kommutatorlar uchun aniq qurilishni ta'minlaydi Punkare - Birxoff - Vitt teoremasi qurilishi uchun zarur universal o'ralgan algebralar.

Lyndonning har bir so'zini a deb tushunish mumkin almashtirish, qo'shimchaning standart almashinuvi.

Duval algoritmi

Duval (1983) chiziqli vaqt va doimiy fazoda ishlaydigan standart faktorizatsiyani topish algoritmini ishlab chiqdi. Lyndon so'zini iloji boricha uzoqroq topishga harakat qilib, mag'lubiyatga takrorlanadi. Bittasini topgach, uni natijalar ro'yxatiga qo'shadi va mag'lubiyatning qolgan qismini qidirishga kirishadi. Natijada paydo bo'lgan satrlar ro'yxati berilgan satrning standart faktorizatsiyasi hisoblanadi. Algoritmning yanada rasmiy tavsifi keladi.

Ip berilgan S uzunlik N, quyidagi bosqichlarni bajarish kerak:

  1. Ruxsat bering m allaqachon to'plangan belgilarga qo'shilishi kerak bo'lgan nomzodning belgisi bo'lishi kerak. Dastlab, m = 1 (satrdagi belgilar ko'rsatkichlari noldan boshlanadi).
  2. Ruxsat bering k biz boshqalarni solishtiradigan belgining ko'rsatkichi bo'ling. Dastlab, k = 0.
  3. Esa k va m dan kam N, taqqoslash S [k] (the k- ipning uchinchi belgisi S) ga S [m]. Uchta natijalar mavjud:
    1. S [k] ga teng S [m]: ilova qiling S [m] joriy yig'ilgan belgilarga. O'sish k va m.
    2. S [k] dan kam S [m]: agar qo'shsak S [m] hozirgi yig'ilgan belgilarga biz Lyndon so'zini olamiz. Ammo biz buni natijalar ro'yxatiga hali qo'sha olmaymiz, chunki bu katta Lindon so'zining bir qismi bo'lishi mumkin. Shunday qilib, faqat o'sish m va sozlang k 0 ga, shuning uchun keyingi belgi satrdagi birinchisiga taqqoslanadi.
    3. S [k] dan katta S [m]: agar qo'shsak S [m] hozirgi yig'ilgan belgilar uchun bu na Lindon so'zi va na birinchisining boshlanishi bo'ladi. Shunday qilib, birinchisini qo'shing m-k natija ro'yxatiga to'plangan belgilar, ularni satrdan olib tashlang, o'rnating m 1 ga va k 0 ga, shunda ular mos ravishda satrning ikkinchi va birinchi belgisini ko'rsatadilar.
  4. Qachon m> N, bu mohiyatan minus cheksizlikka duch kelishga o'xshaydi, shuning uchun birinchisini qo'shing m-k belgilar qatoridan chiqarilgandan so'ng natijalar ro'yxatiga to'plangan belgilar, o'rnatilgan m 1 ga va k ga o'ting va oldingi bosqichga qayting.
  5. Qo'shish S natijalar ro'yxatiga.

Bruijn ketma-ketliklariga ulanish

Agar kishi birlashtirsa, leksikografik tartibda, berilgan sonni ajratuvchi uzunlikka ega bo'lgan barcha Lindon so'zlari n, natija a de Bruijn ketma-ketligi, har bir mumkin bo'lgan uzunlik -n ketma-ketlik, uning yonma-yon ketma-ketliklaridan biri sifatida to'liq bir marta paydo bo'ladi. Masalan, uzunligi to'rtga bo'linadigan ikkilik Lindon so'zlarining birikmasi

0 0001 0011 01 0111 1

Ushbu qurilish Lyndon so'zlarini samarali yaratish bilan birgalikda ma'lum bir Bruijn ketma-ketligini yaratish uchun samarali usulni taqdim etadi. chiziqli vaqt va logaritmik bo'shliq.[16]

Qo'shimcha xususiyatlar va ilovalar

Lyndon so'zlari tavsifiga dastur mavjud bepul algebralar, ma'lum darajadagi bir hil qism uchun asos yaratishda; bu Lindonning ushbu so'zlarni kiritish uchun asl motivatsiyasi edi.[4] Lyndon so'zlarini alohida holat sifatida tushunish mumkin Zal to'plamlari.[4]

Eng yaxshi uchun p, kamaytirilmaydigan son monik polinomlar daraja d maydon ustidan uzunlikdagi Lindon so'zlari soni bilan bir xil d alifbosida p belgilar; ular aniq yozishmalarga joylashtirilishi mumkin.[17]

Radford teoremasida a aralash algebra 0 xarakterli maydon ustida Lindon so'zlari ustida polinom algebra sifatida qarash mumkin. Aniqrog'i, ruxsat bering A alifbo bo'ling, ruxsat bering k 0 ga xos bo'lgan maydon (yoki umuman olganda, komutativ b-algebra) bo'lsin va bo'lsin R bepul noncommutative bo'ling k-algebra k ⟨ xa | a ∈ A ⟩. So'zlar tugadi A keyin "noaniq monomiallar" (ya'ni. ning mahsulotlari) bilan aniqlanishi mumkin xa) ichida R; ya'ni biz so'zni aniqlaymiz (a1,a2,...,an) monomial bilan xa1xa2...xan. Shunday qilib, so'zlar tugadi A shakl k-vektor fazosi R. Keyin, a aralashtirish mahsuloti belgilanadi R; bu k-sh bilan belgilanadigan va so'zlar bo'yicha rekursiv ravishda belgilanadigan ikkilamchi, assotsiativ va komutativ mahsulot.

1 sh v = v har qanday so'z uchun v;
siz sh 1 = siz har qanday so'z uchun siz;
ua sh vb = (siz sh vb)a + (ua sh v)b har qanday kishi uchun a,b ∈ A va har qanday so'zlar siz va v.

The aralash algebra alifboda A qo'shimchalar guruhi deb belgilangan R ko'paytirish sifatida sh bilan ta'minlangan. Radford teoremasi[18] endi Lindon so'zlari ushbu aralash algebraning algebraik jihatdan mustaqil elementlari ekanligini va uni yaratishini ta'kidlamoqda; Shunday qilib, aralash algebra polinom halqasi uchun izomorfdir k, Lyndon so'zlariga mos keladigan noaniqliklar bilan.[18]

Shuningdek qarang

Izohlar

  1. ^ Lyndon (1954).
  2. ^ Shirshov (1953).
  3. ^ a b Berstel va Perrin (2007); Melancon (2001).
  4. ^ a b v Melancon (2001).
  5. ^ Berstel va Perrin (2007).
  6. ^ Ruski (2003) Lyndon so'zlari va shunga o'xshash bir qator tushunchalar uchun ushbu sanoqlarning tafsilotlarini taqdim etadi.
  7. ^ Berstel va Pochkiola (1994).
  8. ^ Melancon (2001). Berstel va Perrin (2007) yozing, garchi bu odatda hisobga olinadigan bo'lsa Chen, Fox va Lindon (1958), va ushbu maqoladagi natijalardan kelib chiqadigan bo'lsak, u qadar aniq aytilmagan Shuttsenberger (1965). Bu aniq shakllangan Shirshov (1958), qarang Shutzenberger va Sherman (1963).
  9. ^ a b Duval (1983).
  10. ^ Gil va Skott (2009); Kufleitner (2009).
  11. ^ Brlek va boshq. (2009).
  12. ^ Emi Glen "Lyndon so'zlarining kombinatorikasi " (2012)
  13. ^ Gay Melancon, (1992) "Hall daraxtlari va Hall so'zlari kombinatorikasi ", Kombinatorik nazariya jurnali, 59A(2) 285-308 betlar.
  14. ^ Gay Melancon va Kristof Reutenauer (1989), "Lindon so'zlari, bepul algebralar va aralashmalar", Kanada matematika jurnali. 41, № 4, 577-591-betlar.
  15. ^ Kristof Xolveg va Kristof Reutenauer, "Lyndon so'zlari, almashtirishlar va daraxtlar ", (2003) LaCIM
  16. ^ Ga binoan Berstel va Perrin (2007), shu tarzda hosil qilingan ketma-ketlik birinchi marta (boshqa avlod usuli bilan) tomonidan tasvirlangan Martin (1934) va u bilan Lindon so'zlari o'rtasidagi bog'liqlik kuzatilgan Fredriksen va Mayorana (1978).
  17. ^ Sulaymon V. Golomb (1969) "Kamaytirilgan polinomlar, sinxronlashtiruvchi kodlar, ibtidoiy marjonlarni va siklotomik algebra", Proc. Conf kombinatorial matematika va uning qo'llanilishi, s.358-370 (Shimoliy Karolina universiteti).
  18. ^ a b Radford (1979)

Adabiyotlar