2025-11-15T04:52:11.684179

Dyck Words, Pattern Avoidance, and Automatic Sequences

Mol, Rampersad, Shallit
We study various aspects of Dyck words appearing in binary sequences, where $0$ is treated as a left parenthesis and $1$ as a right parenthesis. We show that binary words that are $7/3$-power-free have bounded nesting level, but this no longer holds for larger repetition exponents. We give an explicit characterization of the factors of the Thue-Morse word that are Dyck, and show how to count them. We also prove tight upper and lower bounds on $f(n)$, the number of Dyck factors of Thue-Morse of length $2n$.
academic

ডাইক শব্দ, প্যাটার্ন এড়ানো এবং স্বয়ংক্রিয় ক্রম

মৌলিক তথ্য

  • পেপার আইডি: 2301.06145
  • শিরোনাম: ডাইক শব্দ, প্যাটার্ন এড়ানো এবং স্বয়ংক্রিয় ক্রম
  • লেখক: লুকাস মল (থম্পসন রিভার্স বিশ্ববিদ্যালয়), নারাদ রামপার্সাদ (উইনিপেগ বিশ্ববিদ্যালয়), জেফ্রি শ্যালিট (ওয়াটারলু বিশ্ববিদ্যালয়)
  • শ্রেণীবিভাগ: cs.DM (বিচ্ছিন্ন গণিত), cs.FL (আনুষ্ঠানিক ভাষা), math.CO (সমন্বয়বিদ্যা)
  • প্রকাশিত জার্নাল: কমিউনিকেশনস ইন ম্যাথেমেটিক্স ৩৩ (২০২৫), নং ২, পেপার নং ৫
  • পেপার লিঙ্ক: https://arxiv.org/abs/2301.06145

সারসংক্ষেপ

এই পেপারটি দ্বিমুখী ক্রমে ডাইক শব্দের বিভিন্ন বৈশিষ্ট্য অধ্যয়ন করে, যেখানে ০ কে বাম বন্ধনী এবং ১ কে ডান বন্ধনী হিসাবে বিবেচনা করা হয়। গবেষণা দেখায় যে ৭/৩-শক্তিমুক্ত দ্বিমুখী শব্দগুলির সীমাবদ্ধ নেস্টিং স্তর রয়েছে, কিন্তু বৃহত্তর পুনরাবৃত্তি সূচকগুলির জন্য এই সম্পত্তি আর ধারণ করে না। পেপারটি থু-মোর্স শব্দে ডাইক ফ্যাক্টরগুলির একটি স্পষ্ট বৈশিষ্ট্য প্রদান করে এবং তাদের সংখ্যা গণনা করার পদ্ধতি প্রদর্শন করে। অতিরিক্তভাবে, দৈর্ঘ্য ২n এর থু-মোর্স ডাইক ফ্যাক্টরের সংখ্যা f(n) এর কঠোর উপরি এবং নিম্ন সীমা প্রমাণ করা হয়েছে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা

এই গবেষণার মূল প্রশ্ন হল অসীম দ্বিমুখী শব্দে ডাইক শব্দ ফ্যাক্টরগুলির কাঠামো এবং বৈশিষ্ট্য বোঝা। ডাইক শব্দগুলি আনুষ্ঠানিক ভাষা তত্ত্বে একটি মৌলিক ধারণা, যা ভারসাম্যপূর্ণ বন্ধনী স্ট্রিং প্রতিনিধিত্ব করে এবং কম্পিউটার বিজ্ঞান এবং গণিতে গুরুত্বপূর্ণ প্রয়োগ রয়েছে।

গবেষণার গুরুত্ব

১. তাত্ত্বিক তাৎপর্য: ডাইক ভাষা প্রসঙ্গ-মুক্ত ভাষার একটি সাধারণ উদাহরণ, স্বয়ংক্রিয় ক্রমে এর বিতরণ অধ্যয়ন করা আনুষ্ঠানিক ভাষা এবং অটোমেটা তত্ত্বের গভীর সংযোগ বোঝাতে সহায়তা করে ২. সমন্বয়বিদ্যার মূল্য: প্যাটার্ন এড়ানো এবং শক্তি এড়ানো সমন্বয়বিদ্যাগত শব্দবিজ্ঞানের মূল গবেষণা দিক, এই গবেষণা এই ধারণাগুলিকে ডাইক শব্দের সাথে একত্রিত করে ३. গণনামূলক প্রয়োগ: স্বয়ংক্রিয় ক্রমগুলি অ্যালগরিদম এবং গণনামূলক জটিলতা তত্ত্বে ব্যাপক প্রয়োগ রয়েছে, তাদের ডাইক ফ্যাক্টরগুলির বৈশিষ্ট্য বোঝা ব্যবহারিক তাৎপর্য রাখে

বিদ্যমান গবেষণার সীমাবদ্ধতা

  • নির্দিষ্ট স্বয়ংক্রিয় ক্রমে ডাইক ফ্যাক্টরগুলির পদ্ধতিগত বৈশিষ্ট্যের অভাব
  • শক্তি এড়ানো এবং নেস্টিং স্তরের সম্পর্কের পরিমাণগত বিশ্লেষণ অপর্যাপ্ত
  • স্বয়ংক্রিয় ক্রম ডাইক ফ্যাক্টর গণনার কার্যকর অ্যালগরিদম অনুপস্থিত

মূল অবদান

१. শক্তি এড়ানো এবং নেস্টিং স্তরের সম্পর্ক: প্রমাণ করা হয়েছে যে ৭/३-শক্তিমুক্ত ডাইক শব্দগুলির নেস্টিং স্তর সর্বাধিক ३, কিন্তু ৭/३⁺-শক্তিমুক্ত ডাইক শব্দগুলির মধ্যে নির্বিচারে বড় নেস্টিং স্তর বিদ্যমান २. থু-মোর্স শব্দের ডাইক ফ্যাক্টর বৈশিষ্ট্য: থু-মোর্স ক্রমে সমস্ত ডাইক ফ্যাক্টরগুলির সম্পূর্ণ বৈশিষ্ট্য প্রদান করা হয়েছে: h(x) ফর্ম, যেখানে x কিছু তিন-মুখী ক্রম s এর একটি ফ্যাক্টর ३. স্বয়ংক্রিয় ক্রমের সাধারণ তত্ত্ব: চলমান এবং সিঙ্ক্রোনাস স্বয়ংক্রিয় ক্রম ডাইক ফ্যাক্টরগুলির সিদ্ধান্তযোগ্যতা তত্ত্বের কাঠামো প্রতিষ্ঠা করা হয়েছে ४. নির্ভুল গণনা ফলাফল: প্রমাণ করা হয়েছে যে থু-মোর্স ক্রমে দৈর্ঘ্য २n এর ডাইক ফ্যাক্টরের সংখ্যা d(n) এর কঠোর উপরি এবং নিম্ন সীমা: d(n) ≤ n এবং d(n) ≥ n/२

পদ্ধতির বিস্তারিত ব্যাখ্যা

কাজের সংজ্ঞা

দ্বিমুখী শব্দ w = w१..n দেওয়া হলে, যদি ० কে বাম বন্ধনী এবং १ কে ডান বন্ধনী হিসাবে বিবেচনা করা হয় তখন w ভারসাম্যপূর্ণ বন্ধনী স্ট্রিং প্রতিনিধিত্ব করে, তাহলে w কে ডাইক শব্দ বলা হয়। আনুষ্ঠানিকভাবে, w একটি ডাইক শব্দ যখন এবং শুধুমাত্র যখন:

  • B(w) = |w|₀ - |w|₁ = ० (ভারসাম্য শর্ত)
  • সমস্ত উপসর্গ w' এর জন্য, B(w') ≥ ० (অ-নেতিবাচকতা শর্ত)

নেস্টিং স্তর N(w) সমস্ত উপসর্গে B(w') এর সর্বোচ্চ মান হিসাবে সংজ্ঞায়িত করা হয়।

মূল পদ্ধতি

१. শক্তি এড়ানো বিশ্লেষণ পদ্ধতি

আবেগপূর্ণ এবং গঠনমূলক প্রমাণ ব্যবহার করা হয়:

  • উপপাদ্য २.१: ७/३-শক্তিমুক্ত ডাইক শব্দগুলির কাঠামো বিশ্লেষণ করে, তাদের নেস্টিং স্তর ≤ ३ প্রমাণ করা হয়েছে
  • উপপাদ্য २.९: বিশেষ রূপান্তর f এবং g তৈরি করা হয়েছে, যাতে f(gᵗ(२)) যেকোনো বড় নেস্টিং স্তরের ७/३⁺-শক্তিমুক্ত ডাইক শব্দ উৎপন্ন করে

२. অটোমেটা তত্ত্ব পদ্ধতি

ওয়ালনাট উপপাদ্য প্রমাণকারী ব্যবহার করে গণনামূলক যাচাইকরণ:

morphism f "0->00100110100110010110010011001011001101
           1->00101100110100110110011010010110011011
           2->00101101001101001011001101001011010011"
morphism g "0->022012 1->022112 2->202101"

३. রৈখিক প্রতিনিধিত্ব তত্ত্ব

চলমান এবং সিঙ্ক্রোনাস k-স্বয়ংক্রিয় ক্রমের জন্য, প্রথম-ক্রমের যুক্তি সূত্র তৈরি করা হয়:

  • ভারসাম্য ফাংশন: Bal(i,n,x) ≡ ∃y,z N₀(i,n,y) ∧ N₁(i,n,z) ∧ ((y<z ∧ x=०) | (y≥z ∧ y=x+z))
  • ডাইক সিদ্ধান্ত: Dyck(i,n) ≡ ভারসাম্যতা ∧ অ-নেতিবাচকতা শর্ত

প্রযুক্তিগত উদ্ভাবনী পয়েন্ট

१. রূপান্তর নির্মাণ কৌশল: বিশেষ ६-একীভূত রূপান্তর g এবং ३८-একীভূত রূপান্তর f ডিজাইন করা হয়েছে, নেস্টিং স্তরের নির্ভুল নিয়ন্ত্রণ অর্জন করা হয়েছে २. সিঙ্ক্রোনাস ক্রম তত্ত্ব: চলমান এবং সিঙ্ক্রোনাস ধারণাগুলি ডাইক ভাষা বিশ্লেষণে প্রসারিত করা হয়েছে, সিদ্ধান্তযোগ্যতার কাঠামো প্রতিষ্ঠা করা হয়েছে ३. রৈখিক প্রতিনিধিত্ব ন্যূনতমকরণ: শুটজেনবার্গার অ্যালগরিদম ব্যবহার করে থু-মোর্স ডাইক ফ্যাক্টর গণনার রৈখিক প্রতিনিধিত্ব র্যাঙ্ক २९ থেকে র্যাঙ্ক ७ এ হ্রাস করা হয়েছে

পরীক্ষামূলক সেটআপ

গণনামূলক সরঞ্জাম

  • ওয়ালনাট উপপাদ্য প্রমাণকারী: স্বয়ংক্রিয় ক্রমের প্রথম-ক্রমের যুক্তি যাচাইকরণের জন্য
  • রৈখিক বীজগণিত সিস্টেম: ম্যাট্রিক্স অপারেশন এবং রৈখিক প্রতিনিধিত্ব গণনার জন্য
  • প্রতীকী গণনা: পুনরাবৃত্তি সম্পর্ক এবং অ্যাসিম্পটোটিক আচরণ যাচাইকরণের জন্য

যাচাইকরণ পদ্ধতি

१. ছোট-স্কেল যাচাইকরণ: n < २९ এর ক্ষেত্রে সরাসরি গণনা যাচাইকরণ २. আবেগপূর্ণ প্রমাণ: গাণিতিক আবেগ ব্যবহার করে সাধারণ ফলাফল প্রমাণ ३. কম্পিউটার-সহায়ক: বড় আকারের গণনা যাচাইকরণের জন্য ওয়ালনাট ব্যবহার (যেমন १३० GB মেমরি, २०३२१ সেকেন্ড CPU সময়)

পরীক্ষামূলক ফলাফল

প্রধান পরিমাণগত ফলাফল

१. নেস্টিং স্তরের সীমা

  • উপরি সীমা: ७/३-শক্তিমুক্ত ডাইক শব্দের নেস্টিং স্তর ≤ ३
  • নিম্ন সীমা: ७/३⁺-শক্তিমুক্ত ডাইক শব্দগুলির মধ্যে যেকোনো বড় নেস্টিং স্তর বিদ্যমান

२. থু-মোর্স ডাইক ফ্যাক্টর গণনা

নির্ভুল পুনরাবৃত্তি সম্পর্ক:

  • d(२n) = २d(n)
  • d(४n+३) = २d(n) + d(२n+१) + q(n)
  • d(८n+१) = २d(२n+१) + d(४n+१) - q(n)
  • d(८n+५) = २d(n) + d(२n+१) + २d(२n+२)

যেখানে q(n) একটি २-স্বয়ংক্রিয় ক্রম, १ ≤ q(n) ≤ २।

३. কঠোর সীমা সংজ্ঞা

  • উপরি সীমা: d(n) ≤ n, যখন n = ३·२ⁱ সমতা ধারণ করে
  • নিম্ন সীমা: d(n) ≥ n/२, যখন n = २ⁱ সমতা ধারণ করে
  • বিজোড় ক্ষেত্র: n বিজোড় হলে, d(n) ≥ (n+३)/२

४. অ্যাসিম্পটোটিক গড় মূল্য

∑₀≤ᵢ<₂ₙ d(i) = १९·४ⁿ/४८ - २ⁿ/४ + ५/३, গড় মূল্য (१९/२४)n

নির্দিষ্ট সংখ্যাগত ফলাফল

প্রথম २१ পদের d(n) মূল্য:

n01234567891011121314151617181920
d(n)1123246648881291213814161416

অন্যান্য ক্রমের ফলাফল

  • ফিবোনাচ্চি ক্রম: শুধুমাত্র ডাইক ফ্যাক্টর ०१ এবং ०१०१
  • পর্যায়ক্রমিক দ্বিগুণ ক্রম: শুধুমাত্র ডাইক ফ্যাক্টর ०१, ०१०१, ०१०१०१
  • রুডিন-শ্যাপিরো ক্রম: যেকোনো বড় নেস্টিং স্তরের ডাইক ফ্যাক্টর বিদ্যমান

সম্পর্কিত কাজ

আনুষ্ঠানিক ভাষা তত্ত্ব

এই গবেষণা চমস্কি এবং শুটজেনবার্গারের প্রসঙ্গ-মুক্ত ভাষা তত্ত্বের ভিত্তিতে প্রতিষ্ঠিত, বিশেষত ডাইক ভাষার বীজগণিত তত্ত্ব।

সমন্বয়বিদ্যাগত শব্দবিজ্ঞান

  • শক্তি এড়ানো তত্ত্ব: থু এর ওভারল্যাপ-মুক্ত শব্দের যুগান্তকারী কাজ উত্তরাধিকার সূত্র
  • স্বয়ংক্রিয় ক্রম: কোবহ্যামের k-স্বয়ংক্রিয় ক্রম তত্ত্ব এবং সাম্প্রতিক সিঙ্ক্রোনাস ক্রম ধারণার উপর ভিত্তি করে

গণনামূলক পদ্ধতি

  • ওয়ালনাট সিস্টেম: মাউসাভি এবং শ্যালিট দ্বারা উন্নত স্বয়ংক্রিয় উপপাদ্য প্রমাণকারী সরঞ্জাম ব্যবহার করা হয়েছে
  • রৈখিক প্রতিনিধিত্ব: বার্সটেল এবং রিউটেনাউয়ারের অ-বিনিময়যোগ্য যুক্তিসঙ্গত সিরিজ তত্ত্ব প্রয়োগ করা হয়েছে

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. সমালোচনামূলক সূচক ঘটনা: ७/३ ডাইক শব্দের নেস্টিং স্তরের সীমাবদ্ধতার সমালোচনামূলক সূচক, শক্তি এড়ানো এবং কাঠামোগত জটিলতার গভীর সংযোগ প্রতিফলিত করে २. স্বয়ংক্রিয় ক্রমের সার্বজনীনতা: চলমান এবং সিঙ্ক্রোনাস বৈশিষ্ট্য স্বয়ংক্রিয় ক্রমে ডাইক ফ্যাক্টর অধ্যয়নের জন্য একটি একীভূত কাঠামো প্রদান করে ३. নির্ভুল গণনা তত্ত্ব: থু-মোর্স ক্রমের ডাইক ফ্যাক্টর গণনা k-নিয়মিত ক্রমের সমৃদ্ধ কাঠামো প্রদর্শন করে

সীমাবদ্ধতা

१. গণনামূলক জটিলতা: বড় আকারের ওয়ালনাট গণনার জন্য বিশাল সম্পদ প্রয়োজন (१३० GB মেমরি) २. বিশেষ ক্রম নির্ভরতা: কিছু ফলাফল (যেমন চলমান এবং সিঙ্ক্রোনাস বৈশিষ্ট্য) ক্রমের বিশেষ বৈশিষ্ট্যের উপর নির্ভর করে ३. সাধারণীকরণের ডিগ্রি: কিছু ফলাফল শুধুমাত্র নির্দিষ্ট স্বয়ংক্রিয় ক্রম শ্রেণীর জন্য প্রযোজ্য

ভবিষ্যত দিকনির্দেশনা

१. উচ্চতর মাত্রা সম্প্রসারণ: স্বয়ংক্রিয় ক্রমে উচ্চ-মাত্রিক ডাইক ভাষার বিতরণ অধ্যয়ন २. অন্যান্য প্যাটার্ন: অন্যান্য প্রসঙ্গ-মুক্ত প্যাটার্নের এড়ানো সমস্যায় সম্প্রসারণ ३. অ্যালগরিদম অপ্টিমাইজেশন: আরও দক্ষ ডাইক ফ্যাক্টর গণনা অ্যালগরিদম বিকাশ

গভীর মূল্যায়ন

সুবিধা

१. তাত্ত্বিক গভীরতা: শক্তি এড়ানো, স্বয়ংক্রিয় ক্রম এবং আনুষ্ঠানিক ভাষা তত্ত্বকে জৈবিকভাবে একত্রিত করা হয়েছে, গভীর তাত্ত্বিক দক্ষতা প্রদর্শন করে २. পদ্ধতি উদ্ভাবন: রূপান্তর নির্মাণ এবং রৈখিক প্রতিনিধিত্ব কৌশলের চতুর প্রয়োগ, বিশেষত নেস্টিং স্তরের নির্ভুল নিয়ন্ত্রণ ३. গণনামূলক কঠোরতা: ব্যাপক কম্পিউটার-সহায়ক যাচাইকরণ ব্যবহার করা হয়েছে, ফলাফলের নির্ভরযোগ্যতা বৃদ্ধি করে ४. ফলাফল সম্পূর্ণতা: অস্তিত্ব থেকে গণনা পর্যন্ত সম্পূর্ণ তাত্ত্বিক চিত্র প্রদান করা হয়েছে

অপূর্ণতা

१. গণনামূলক সম্পদ: কিছু প্রমাণ বড় আকারের গণনার উপর নির্ভর করে, যা ফলাফলের যাচাইযোগ্যতা সীমিত করতে পারে २. সাধারণীকরণযোগ্যতা: কিছু প্রযুক্তিগত পদ্ধতি আরও সাধারণ ক্রম শ্রেণীতে সম্প্রসারণ করা কঠিন হতে পারে ३. প্রয়োগ-ভিত্তিক: তাত্ত্বিক ফলাফলের ব্যবহারিক প্রয়োগ মূল্য আরও অন্বেষণের প্রয়োজন

প্রভাব

१. শৃঙ্খলা অতিক্রম: সমন্বয় গণিত, আনুষ্ঠানিক ভাষা তত্ত্ব এবং অটোমেটা তত্ত্বের আন্তঃ বিকাশ প্রচার করে २. পদ্ধতিগত অবদান: স্বয়ংক্রিয় ক্রমে কাঠামোগত প্যাটার্ন অধ্যয়নের জন্য নতুন বিশ্লেষণ কাঠামো প্রদান করে ३. গণনামূলক সরঞ্জাম: আধুনিক উপপাদ্য প্রমাণকারী সরঞ্জামের সমন্বয়বিদ্যাগত সমস্যায় শক্তিশালী প্রয়োগ প্রদর্শন করে

প্রযোজ্য পরিস্থিতি

१. তাত্ত্বিক গবেষণা: সমন্বয়বিদ্যাগত শব্দবিজ্ঞান এবং আনুষ্ঠানিক ভাষা তত্ত্বের গভীর গবেষণার জন্য উপযুক্ত २. অ্যালগরিদম ডিজাইন: কাঠামোগত ক্রম প্রক্রিয়াকরণ অ্যালগরিদম ডিজাইনের জন্য তাত্ত্বিক ভিত্তি প্রদান করে ३. শিক্ষামূলক প্রয়োগ: আধুনিক গাণিতিক গণনা পদ্ধতি প্রদর্শনের জন্য একটি উৎকৃষ্ট কেস স্টাডি হিসাবে কাজ করতে পারে

রেফারেন্স

এই পেপারটি আনুষ্ঠানিক ভাষা তত্ত্ব, সমন্বয় গণিত এবং অটোমেটা তত্ত্বের গুরুত্বপূর্ণ সাহিত্য উদ্ধৃত করে, যার মধ্যে রয়েছে:

  • চমস্কি এবং শুটজেনবার্গারের প্রসঙ্গ-মুক্ত ভাষা তত্ত্ব
  • থু এর ওভারল্যাপ-মুক্ত শব্দের যুগান্তকারী কাজ
  • অ্যালাউচে এবং শ্যালিটের k-নিয়মিত ক্রম তত্ত্ব
  • বার্সটেল এবং রিউটেনাউয়ারের অ-বিনিময়যোগ্য যুক্তিসঙ্গত সিরিজ
  • আধুনিক গণনামূলক সরঞ্জাম ওয়ালনাটের সম্পর্কিত সাহিত্য

সামগ্রিক মূল্যায়ন: এটি তাত্ত্বিক গভীরতা এবং প্রযুক্তিগত উদ্ভাবনের দিক থেকে চমৎকার পারফরম্যান্স প্রদর্শন করে এমন একটি পেপার, যা গণিতের একাধিক শাখার ধারণা এবং পদ্ধতিকে সফলভাবে জৈবিকভাবে একত্রিত করে, স্বয়ংক্রিয় ক্রমে কাঠামোগত প্যাটার্ন বোঝার জন্য গুরুত্বপূর্ণ অবদান প্রদান করে। যদিও গণনামূলক জটিলতা এবং সাধারণীকরণযোগ্যতার দিক থেকে নির্দিষ্ট সীমাবদ্ধতা রয়েছে, তবে এর তাত্ত্বিক মূল্য এবং পদ্ধতিগত তাৎপর্য উল্লেখযোগ্য।