الطبقية من الثناء: $ \ $ $ لا يتزامن مع $ \ sim_ \ أوميغا دولار

cs.stackexchange https://cs.stackexchange.com/questions/129635

سؤال

أنا أقرأ ورقة Sangiorgi على أصول الحرق .

التعريف 2.5، في الصفحة 5، يحدد الطبقية من الثناء :

دع $ W $ تكون حالات LTS. وضعنا:

  • $ \ sim_0 \ overset {\ text {def}} {=} w \ times w $

  • $ s \ sim_ {n + 1} t $ ، for $ n \ geq 0 $ < / span>، إذا:

    (1) لجميع $ s ^ \ prime $ مع $ s \ overset {\ mu} {\ charnarrow } s ^ \ prime $ ، هناك $ t ^ \ prime $ مثل هذا $ t \ overset { \ MU} {\ rawrow} t ^ \ prime $ و $ s ^ \ prime \ sim_n t ^ \ prime $ ؛

    (2) الحديث، وهذا هو، كلما لجميع $ t ^ \ prime $ مع $ t \ gotset {\ mu} {\ charnarrow} t ^ \ prime $ ، هناك $ s ^ \ prime $ مثل هذا $ s \ overset {\ mu} {\ charnarrow} s ^ \ prime $ و $ s ^ \ prime \ sim_n t ^ \ prime $ .

  • li>

    $ \ sim_ \ omega \ overset {\ text {def}} {=} \ bigcap_ {n \ geq 0} \ sim_n $

يتبع الورقة مع ملاحظة أنه، بشكل عام، $ \ sim_ \ Omega $ لا يتزامن مع $ \ SIM $ (التثدي المعتاد)، ويوفر المثال التالي (مثال 2.6 في الورق) لتسليط الضوء على ذلك:

نأخذ LTS مع $ \ {a \} $ باسم مجموعة (arrow)، ومجموعة الدول هي $ \ {a ^ 0، a ^ 1، dots، a ^ \ omega، s، t \} $ ، وظيفة الانتقال $ \ Overet {a} {\ ignarrow} $ هو الأقل وظيفة بحيث:

  • $ a ^ \ omega \ overset {a} {\ charnarrow} a ^ \ omega $
  • $ \ forall n \ geq 1، a ^ n \ overset {a} {\ charnarrow} a ^ {n-1} $
  • li> $ \ forall n \ in \ mathbb {n}، s \ overset {a} {\ charnarrow} a ^ {n} $
  • $ \ forall n \ in \ mathbb {n}، t \ overset {a} {\ charnarrow} a ^ {n} $
  • $ t \ overset {a} {\ charnarrow} a ^ {\ omega} $

الذي تمثل في هذه الصورة:

 تمثيل LTS المحدد أعلاه

المثال ثم الولايات:

من السهل إثباتها، عن طريق التعريفي على $ n $ ، أي، لجميع $ n $ ، $ s \ sim_n t $ ، وبالتالي أيضا $ s \ sim_ \ omega t $ .

ومع ذلك، لا أفهم كيفية حدوث ذلك، حتى بالنسبة ل $ \ sim_1 $ : $ s \ sim_1 t $ إذا (من البند (2)): كلما للجميع $ t ^ \ prime $ مع $ t \ overset {\ mu} {\ charnarrow} t $ ، هناك $ s ^ \ prime $ مثل هذا $ s \ overset {\ mu} {\ mu} {\ mu} arnarrow} s ^ \ prime $ و $ s ^ \ prime \ sim_0 t ^ \ prime $ . دعونا نأخذ $ a ^ \ omega $ ك $ t ^ \ Prime $ ، لدينا بالفعل $ T \ overset {a} {\ charnarrow} a ^ \ omega $ . لذلك، علينا أن نجد $ s ^ \ prime $ مثل $ s \ overset {a} {\ charnarrow} s ^ \ Prime $ و $ s ^ \ prime \ sim_0 a ^ \ omega $ .

من هنا سؤدي: الحالة التي تناسب مثل $ s ^ \ prime $ ، منذ $ s \ not \ Overet {a} {\ ignarrow} a ^ \ omega $ ؟

هل كانت مفيدة؟

المحلول

وجدت إجابة سؤالي عند كتابة ذلك، والتي تثبت مرة أخرى فعالية الواجهة بشكل صحيح السؤال الذي لدينا.


لإظهار أن $ s \ sim_1 t $ ، لتعيين $ a ^ \ omega $ ، يمكن للمرء أن يأخذ أي $ a ^ i $ نريد (مثل $ a ^ 0 $ ): بحكم التعريف ، $ \ sim_0 \ overset {\ text {def}} {=} w \ times w $ ، وبالتالي لدينا بالفعل هذا $ s \ overset {a} {\ ignarrow} a ^ 0 $ و $ a ^ 0 \ sim_0 a ^ \ omega $ .

شيء يجب ملاحظته هو أنه لكل $ n $ ، لدينا $ a ^ \ omega \ sim_n a ^ M $ ل $ m \ geq n $ . لذلك، لإظهار أن $ s \ sim_ {n + 1} t ، لإظهار العنصر (2)، يمكن للمرء أن يأخذ ببساطة $ a ^ n $ $ s ^ \ prime $ عندما نأخذ $ a ^ \ omega $ ك $ t ^ \ prime $ . بقية الدليل تافهة.

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top