تحليل فضاء الحالات للحاسبات الدورية المنتهية

Abstract

ندرس في هذا البحث التحليل الشبكي (sp  –تجزئة ) لفضاء الحالات Q_n لحاسبة دورية منتهية
A_n=(Q_n , X , Y , δ_n , λ_n)_، حيث n عدد طبيعي (2n ≥ ). يشمل هذا البحث على نتائج تميز هذا النوع من التجزئات، بالإضافة إلي تعيين العمليات الجبرية على الشبكة، وذلك بدلالة العوامل الموجبة للعدد الصحيح n. وتتلخص بما يلي:

1. إذا كان Q_n فضاء الحالات لحاسبة دورية منتهية A_n، و π تجزئة لـ Q_n، عندئذ π تشكل (sp  –تجزئة) للفضاء Q_n إذا وفقط إذا كان _r,sπ = π بالنسبة لبعض الأعداد الصحيحة r, s حيث  r.s = n.
2. إذا كانت _r',s'π و _r,sπ SP)– تجزئتان) منفصلتان لفضاء الحالات Q_n لحاسبة دورية منتهية A_n، عندئذ يكون = 0 _r',s'π o _r,sπ إذا وفقط إذا كان .GCD(r,r')=1
3. يوجد  SP)– تجزئتين) منفصلتين غير تافهتين ^''π و ^'π لفضاء الحالات Q_n (2n ≥ )، بحيث يكون 0=^''π^'oπ، إذا وفقط إذا كان العدد n قابلاً للقسمة على عددين أوليين مختلفين على الأقل.
4. إذا كان Q_n فضاء الحالات لحاسبة دورية منتهية الحالات (n ≥ 2)، و r, s, r^', s^' أعداداً طبيعية، بحيثr.s=n=r'.s'  و D=D(s, s^') ترمز للمضاعف المشترك الأصغر للعددين s, s^'، وكذلكd = d(s, s^') القاسم المشترك الأكبر لهما، عندئذ تتحقق المساويتان التاليتان:

= π _n/D, _{D ' r',s} π  o  _r,s π

= π _{n/d , d ' r',s} π  +  _r,s π

The decomposition of the sublattice of SP-Partitions of the state space Q_n of the finite-state cyclic machine A_n, when n is a natural number ≥ 2 and A_n=(Q_n, X, Y, δ_n, λ_n). A simple characterization of these SP-Partitions, as well as the Lattice operations, is obtained in terms of the positive factors of n. We brief these results as follows:

1. If Q_n is the state space for the finite–state cyclic machine A_n and π is a partition of Q_n, then π is an SP-partition of Q_n if, and only if, π = π _{r, s} for some positive integers r, s such that r.s = n.
2. If  π _{r, s} , π _{r' ,s'} are two distinct SP–partitions of the state space Q_n then π _r,s o π _r',s' = 0 (the zero partition) if, and only if, GCD (r, r') = 1.
3. For  n  ≥ 2, there exist two distinct non-trivial partitions π ^'and π ^"of the state space Q_n such that,  π ^' o π ^" = 0 if, and only if, n is divisible by at least two distinct primes.
4. If Q_n is the state space of the finite–state cyclic machine (n ≥ 2 ), and r, s, r', s' natural numbers such that r.s = n = r'. s', and D = D (s , s') denote the least common multiple of common divisor of s and s' and d = d (s , s^') be their greatest common divisor, then the following equations hold:

= π_n/D , _{D ' r',s}π  o   _r,sπ

= π_{n/d , d ' r',s}π  + _r,sπ