2025-11-19T16:52:14.243866

Learning Weighted Automata over Number Rings, Concretely and Categorically

Aristote, van Gool, PetriÅan et al.

We develop a generic reduction procedure for active learning problems. Our approach is inspired by a recent polynomial-time reduction of the exact learning problem for weighted automata over integers to that for weighted automata over rationals (Buna-Marginean et al. 2024). Our procedure improves the efficiency of a category-theoretic automata learning algorithm, and poses new questions about the complexity of its implementation when instantiated to concrete categories. As our second main contribution, we address these complexity aspects in the concrete setting of learning weighted automata over number rings, that is, rings of integers in an algebraic number field. Assuming a full representation of a number ring OK, we obtain an exact learning algorithm of OK-weighted automata that runs in polynomial time in the size of the target automaton, the logarithm of the length of the longest counterexample, the degree of the number field, and the logarithm of its discriminant. Our algorithm produces an automaton that has at most one more state than the minimal one, and we prove that doing better requires solving the principal ideal problem, for which the best currently known algorithm is in quantum polynomial time.

academic

সংখ্যা বলয়ের উপর ভারিত স্বয়ংক্রিয় যন্ত্র শেখা, সুনির্দিষ্টভাবে এবং বিভাগীয়ভাবে

মৌলিক তথ্য

পত্র আইডি: 2504.16596
শিরোনাম: সংখ্যা বলয়ের উপর ভারিত স্বয়ংক্রিয় যন্ত্র শেখা, সুনির্দিষ্টভাবে এবং বিভাগীয়ভাবে
লেখক: কোয়েন্টিন অ্যারিস্টোট, স্যাম ভ্যান গুল, ড্যানিয়েলা পেট্রিশান, মাহসা শিরমোহাম্মাদি
শ্রেণীবিভাগ: cs.FL (আনুষ্ঠানিক ভাষা এবং স্বয়ংক্রিয় যন্ত্র তত্ত্ব)
প্রকাশনার সময়: ২০২৫ সালের ২৩ এপ্রিল (arXiv প্রাক-প্রিন্ট)
পত্র লিঙ্ক: https://arxiv.org/abs/2504.16596

সারসংক্ষেপ

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

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

সমস্যা পটভূমি

১. ধ্রুবক স্বয়ংক্রিয় যন্ত্র শেখা: অ্যাঙ্গলুইনের L* অ্যালগরিদম ন্যূনতম পর্যাপ্ত শিক্ষক (MAT) কাঠামোর অধীনে নির্ধারক সীমিত অবস্থা স্বয়ংক্রিয় যন্ত্র দক্ষতার সাথে শেখায়, যা গণনামূলক শেখার তত্ত্বের একটি ধ্রুবক ফলাফল।

२. ভারিত স্বয়ংক্রিয় যন্ত্র শেখার চ্যালেঞ্জ: শেখার অ্যালগরিদমকে আরও প্রকাশনীয় মডেলে প্রসারিত করা (যেমন ভারিত স্বয়ংক্রিয় যন্ত্র) চ্যালেঞ্জের মুখোমুখি হয়, বিশেষত যখন ওজন ক্ষেত্রে নয় বরং বলয়ে থাকে।

३. বিদ্যমান পদ্ধতির সীমাবদ্ধতা:

ক্ষেত্রের উপর ভারিত স্বয়ংক্রিয় যন্ত্রের জন্য, বহুপদী সময় শেখার অ্যালগরিদম রয়েছে
সাধারণ বলয়ের উপর ভারিত স্বয়ংক্রিয় যন্ত্রের জন্য, বিদ্যমান পদ্ধতিগুলি হয় অত্যধিক জটিল বা সীমিত প্রয়োগযোগ্যতা রয়েছে
বিভাগীয় পদ্ধতি সর্বজনীন হলেও সুনির্দিষ্ট বাস্তবায়নে সূচকীয় জটিলতা হতে পারে

গবেষণা প্রেরণা

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

মূল অবদান

१. সর্বজনীন হ্রাস অ্যালগরিদম: অ্যালগরিদম ३ প্রস্তাব করা হয়েছে, যা বিভাগীয় কাঠামোর অধীনে একটি সর্বজনীন হ্রাস পদ্ধতি যা একটি শেখার সমস্যা শ্রেণীকে আরও সহজে পরিচালনাযোগ্য শেখার সমস্যায় হ্রাস করে

२. সংখ্যা বলয়ে সুনির্দিষ্ট অ্যালগরিদম: অ্যালগরিদম ४ বিকাশ করা হয়েছে, যা সংখ্যা বলয় OK এর উপর ভারিত স্বয়ংক্রিয় যন্ত্রের বহুপদী সময় শেখার জন্য বিশেষভাবে ডিজাইন করা হয়েছে

३. প্রায় সর্বোত্তমতা ফলাফল: প্রমাণিত হয়েছে যে অ্যালগরিদম দ্বারা উত্পাদিত স্বয়ংক্রিয় যন্ত্রটি সর্বনিম্ন স্বয়ংক্রিয় যন্ত্রের চেয়ে সর্বাধিক একটি অবস্থা বেশি (প্রায় ন্যূনতমতা)

४. তাত্ত্বিক জটিলতা সীমানা: প্রমাণিত হয়েছে যে সম্পূর্ণ ন্যূনতম স্বয়ংক্রিয় যন্ত্র অর্জন করা প্রধান আদর্শ সমস্যা (PIP-কঠিন) সমাধানের সমতুল্য, সমস্যার তাত্ত্বিক নিম্ন সীমা প্রতিষ্ঠা করে

५. ফাটু সম্পত্তি সাধারণীকরণ: প্রমাণিত হয়েছে যে ডেডেকিন্ড ডোমেইনগুলি "প্রায় শক্তিশালী ফাটু বলয়", ধ্রুবক ফাটু সম্পত্তি সাধারণীকরণ করে

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

কাজের সংজ্ঞা

ইনপুট: একটি অজানা OK-ভারিত ভাষা L: Σ* → OK (oracle অ্যাক্সেসের মাধ্যমে) আউটপুট: একটি OK-ভারিত স্বয়ংক্রিয় যন্ত্র যা L গণনা করে সীমাবদ্ধতা: অ্যালগরিদম জটিলতা লক্ষ্য স্বয়ংক্রিয় যন্ত্রের আকার, দীর্ঘতম প্রতিবাদী দৈর্ঘ্যের লগারিদম, সংখ্যা ক্ষেত্রের ডিগ্রি এবং বিচারক লগারিদমের বহুপদী

মূল প্রযুক্তিগত কাঠামো

१. বিভাগীয় ভিত্তি

পত্রটি ফাংটর দৃষ্টিভঙ্গি গ্রহণ করে, স্বয়ংক্রিয় যন্ত্রকে ফাংটর A: I → C হিসাবে দেখে, যেখানে:

I হল বর্ণমালা Σ দ্বারা উত্পাদিত মুক্ত বিভাগ
C হল আউটপুট বিভাগ (যেমন মডিউল বিভাগ ModR)

२. সর্বজনীন হ্রাস অ্যালগরিদম (অ্যালগরিদম ३)

অ্যালগরিদম ধারণা:
१. "সহজ পরিচালনাযোগ্য" বিভাগ D-তে স্বয়ংক্রিয় যন্ত্র শিখুন
२. ফাংটর F: C → D এর মাধ্যমে সংযোগ স্থাপন করুন
३. ফলাফলকে লক্ষ্য বিভাগ C-তে টানতে ডান সহযোগী G: D → C ব্যবহার করুন

মূল অনুমান (অনুমান १२):

F নির্দিষ্ট morphism শ্রেণী সংরক্ষণ করে
F এর ডান সহযোগী রয়েছে
ইউনিট এবং কো-ইউনিট morphisms নির্দিষ্ট সম্পত্তি রয়েছে

३. সংখ্যা বলয়ে সুনির্দিষ্ট বাস্তবায়ন (অ্যালগরিদম ४)

ধাপ १: পশ্চাদ্বর্তী সংযোগ

স্বয়ংক্রিয় যন্ত্র A এর পশ্চাদ্বর্তী স্থানের ভিত্তি B গণনা করুন
ম্যাট্রিক্স B দ্বারা A সংযোগ করে A' পান

ধাপ २: সামনের মডিউল উত্পাদন

অ্যালগরিদম ५ কল করুন A' এর সামনের OK-মডিউলের উত্পাদক সেট গণনা করতে
দুই-পর্যায়ের কৌশল ব্যবহার করুন:
- প্রথম পর্যায়: K-তে র্যাঙ্ক বৃদ্ধিকারী শব্দ খুঁজুন
- দ্বিতীয় পর্যায়: OK-তে মডিউল উত্পাদন সম্পূর্ণ করুন

ধাপ ३: সিউডো-ভিত্তি গণনা

সিউডো হার্মাইট স্ট্যান্ডার্ড ফর্ম (pseudo-HNF) ব্যবহার করে উত্পাদক সেট থেকে সিউডো-ভিত্তি গণনা করুন
সিউডো-ভিত্তি ফর্ম: {(ai, vi) | १ ≤ i ≤ ℓ}, যেখানে ai হল ভগ্নাংশ আদর্শ

ধাপ ४: প্রায় ন্যূনতম উত্পাদক সেট

অ্যালগরিদম ६ দ্বারা সিউডো-ভিত্তিকে আকার সর্বাধিক ℓ+१ এর উত্পাদক সেটে রূপান্তরিত করুন
আদর্শ কারণ পরিমার্জন এবং চীনা অবশেষ উপপাদ্য ব্যবহার করুন

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

१. দুই-পর্যায়ের উত্পাদন কৌশল: প্রথমে K ক্ষেত্রে র্যাঙ্ক নির্ধারণ করুন, তারপর OK পরিবেশে মডিউল কাঠামো সম্পূর্ণ করুন, সূচকীয় জটিলতা এড়ান

२. সিউডো-ভিত্তি প্রযুক্তি: ডেডেকিন্ড ডোমেইনের কাঠামো তত্ত্ব ব্যবহার করে, সিউডো-ভিত্তির মাধ্যমে অ-প্রধান আদর্শ ডোমেইনের পরিস্থিতি পরিচালনা করুন

३. বিভাগীয় তত্ত্ব এবং সুনির্দিষ্ট অ্যালগরিদমের সমন্বয়: বিমূর্ত বিভাগীয় কাঠামোকে বাস্তবায়নযোগ্য বহুপদী অ্যালগরিদমে সুনির্দিষ্ট করুন

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

তাত্ত্বিক যাচাইকরণ

পত্রটি প্রধানত তাত্ত্বিক কাজ, নিম্নলিখিত উপায়ে যাচাই করা হয়:

१. জটিলতা বিশ্লেষণ: অ্যালগরিদম ४ এবং অ্যালগরিদম ५ এর সময় জটিলতার বিস্তারিত বিশ্লেষণ २. সঠিকতা প্রমাণ: উপপাদ্য १८ এর মাধ্যমে সর্বজনীন অ্যালগরিদমের সঠিকতা প্রমাণ করুন ३. উদাহরণ যাচাইকরণ: সুনির্দিষ্ট উদাহরণ প্রদান করুন (যেমন উদাহরণ १) Zi√५ এ পরিস্থিতি ব্যাখ্যা করতে

জটিলতা সীমানা

উপপাদ্য २: OK এর সম্পূর্ণ প্রতিনিধিত্ব দেওয়া, OK-ভারিত স্বয়ংক্রিয় যন্ত্রের নির্ভুল শেখা নিম্নলিখিত পরামিতিগুলির বহুপদী সময়ে সমাধানযোগ্য:

লক্ষ্য স্বয়ংক্রিয় যন্ত্রের আকার
দীর্ঘতম প্রতিবাদী দৈর্ঘ্যের লগারিদম
সংখ্যা ক্ষেত্রের ডিগ্রি d
বিচারক ΔK এর লগারিদম

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

প্রধান তাত্ত্বিক ফলাফল

१. প্রায় সর্বোত্তমতা (উপাদান १०): ডেডেকিন্ড ডোমেইন R এর জন্য, যদি L র্যাঙ্ক n এর একটি R-ভারিত ভাষা হয়, তবে সর্বাধিক n+१ অবস্থার একটি R-ভারিত স্বয়ংক্রিয় যন্ত্র বিদ্যমান যা L গণনা করে

२. জটিলতা নিম্ন সীমা (উপাদান २६): OK-ভারিত স্বয়ংক্রিয় যন্ত্র অবস্থা-ন্যূনতম কিনা তা নির্ধারণ করা PIP-কঠিন

३. ফাটু সম্পত্তি সাধারণীকরণ (অনুসিদ্ধান্ত १६): ডেডেকিন্ড ডোমেইনগুলি প্রায় শক্তিশালী ফাটু বলয়

সুনির্দিষ্ট উদাহরণ বিশ্লেষণ

উদাহরণ १: সংখ্যা বলয় R = Zi√५ এ:

একটি ३-অবস্থার R-ভারিত স্বয়ংক্রিয় যন্ত্র নির্মাণ করা হয়েছে
একটি সমতুল্য २-অবস্থার K-ভারিত স্বয়ংক্রিয় যন্ত্র বিদ্যমান (K = Q(i√५))
শক্তিশালী ফাটু সম্পত্তি সর্বদা সত্য নয় তা প্রদর্শন করে, কিন্তু প্রায় শক্তিশালী ফাটু সম্পত্তি সত্য

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

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

१. সংখ্যা বলয়ের উপর ভারিত স্বয়ংক্রিয় যন্ত্র শেখার প্রথম বহুপদী সময় অ্যালগরিদম বিকাশ করা হয়েছে २. সম্পূর্ণ ন্যূনতম স্বয়ংক্রিয় যন্ত্র অর্জনের কঠিনতা প্রমাণ করা হয়েছে (PIP-কঠিন) ३. বিভাগীয় তত্ত্ব এবং সুনির্দিষ্ট অ্যালগরিদমের মধ্যে সেতু প্রতিষ্ঠা করা হয়েছে

সীমাবদ্ধতা

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

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

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

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

সুবিধা

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

অপূর্ণতা

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

প্রভাব

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

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

१. ক্রিপ্টোগ্রাফি: জালি ক্রিপ্টোগ্রাফিতে সংখ্যা বলয়ের প্রয়োগ २. প্রতীকী গণনা: বীজগণিত সংখ্যা ক্ষেত্রে গণনামূলক সমস্যা ३. তাত্ত্বিক গবেষণা: আরও স্বয়ংক্রিয় যন্ত্র শেখার গবেষণার জন্য ভিত্তি প্রদান করে

প্রযুক্তিগত বিবরণ পরিপূরক

সংখ্যা বলয়ের প্রতিনিধিত্ব

পত্রটি OK এর "সম্পূর্ণ প্রতিনিধিত্ব" প্রয়োজন যার মধ্যে রয়েছে:

অবিচ্ছেদ্য ভিত্তি Ω = {ω१,...,ωd}
প্রাথমিক উপাদান θ এবং এর ন্যূনতম বহুপদী
জটিলতা পরিমাপ CK = d⁴(log d + log ΔK)

অ্যালগরিদম জটিলতা

মূল জটিলতা সীমানা আসে:

সিউডো HNF গণনা: বহুপদী সময় (Biasse-Fieker-Hofmann)
কঠোর বর্ধনশীল শৃঙ্খল দৈর্ঘ্য: লেম্মা २४ দ্বারা log(N(d)) হিসাবে সীমাবদ্ধ
আদর্শ অপারেশন: CK-তে বহুপদী সময়

এই পত্রটি তাত্ত্বিক কম্পিউটার বিজ্ঞান ক্ষেত্রে গুরুত্বপূর্ণ অবদান রাখে, বিশেষত স্বয়ংক্রিয় যন্ত্র শেখা এবং বীজগণিত গণনার ছেদ ক্ষেত্রে। যদিও ব্যবহারিকতা যাচাইকরণের জন্য অপেক্ষা করছে, এর তাত্ত্বিক মূল্য এবং পদ্ধতিগত তাৎপর্য উল্লেখযোগ্য।