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

Authors

  • محمد حسن
  • جميل محمد

Abstract

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

  1. إذا كان Qn فضاء الحالات لحاسبة دورية منتهية An، و π تجزئة لـ Qn، عندئذ π تشكل (sp  –تجزئة) للفضاء Qn إذا وفقط إذا كان r,sπ = π بالنسبة لبعض الأعداد الصحيحة r, s حيث  r.s = n.
  2. إذا كانت r',s'π و r,sπ SP)– تجزئتان) منفصلتان لفضاء الحالات Qn لحاسبة دورية منتهية An، عندئذ يكون = 0 r',s'π o r,sπ إذا وفقط إذا كان .GCD(r,r')=1
  3. يوجد  SP)– تجزئتين) منفصلتين غير تافهتين ''π و 'π لفضاء الحالات Qn (2n ≥ )، بحيث يكون 0=''π'oπ، إذا وفقط إذا كان العدد n قابلاً للقسمة على عددين أوليين مختلفين على الأقل.
  4. إذا كان Qn فضاء الحالات لحاسبة دورية منتهية الحالات (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 Qn of the finite-state cyclic machine An, when n is a natural number ≥ 2 and An=(Qn, 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 Qn is the state space for the finite–state cyclic machine An and π is a partition of Qn, then π is an SP-partition of Qn 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 Qn 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 Qn such that,  π ' o π " = 0 if, and only if, n is divisible by at least two distinct primes.
  4. If Qn 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π

Downloads

Published

2018-12-09

How to Cite

1.
حسن م, محمد ج. تحليل فضاء الحالات للحاسبات الدورية المنتهية. TUJ-BA [Internet]. 2018Dec.9 [cited 2024Jul.14];33(1). Available from: https://journal.tishreen.edu.sy/index.php/bassnc/article/view/5199

Most read articles by the same author(s)