این مقاله در مورد جبر کلین با یک عمل بسته شدن است - تعمیم عبارات منظم. برای جبر کلین همراه با تکامل - تعمیم منطق سه گانه کلین - ، به جبر کلین (با تکامل) مراجعه کنید .

در ریاضیات ، یک کلین جبر ( / K L eɪ N من / KLAY -nee ؛ به نام بعد از استیون کول کلین ) یک idempotent (و در نتیجه پاره مرتب) است semiring عطا با یک اپراتور بسته شدن . [1] عملکردهای شناخته شده از عبارات منظم را تعمیم می دهد .

 

فهرست

تعریف [ ویرایش ]

در ادبیات تعاریف مختلفی از جبر کلین و ساختارهای مرتبط ارائه شده است. [2] در اینجا ما تعریفی را ارائه خواهیم داد که به نظر می رسد امروزه رایج ترین باشد.

کلین جبر است مجموعه ای همراه با دو عملیات دودویی +: × → و ·: × → و یک تابع *  : → ، نوشته شده به عنوان + ب ، AB و * به ترتیب، به طوری که بدیهیات زیر راضی هستند

  • Associativity از + و ·: + ( ب + ج ) = ( + ب ) + ج و ( پیش از میلاد ) = ( AB ) ج برای همه ، ب ، ج در .
  • اشتراک پذیری +: a + b = b + a برای همه a ، b در A
  • توزیع : a ( b + c ) = ( ab ) + ( ac ) و ( b + c ) a = ( ba ) + ( ca ) برای همه a ، b ، c در A
  • عناصر هویت برای + و ·: یک عنصر 0 در A وجود دارد به طوری که برای همه a در A : a + 0 = 0 + a = a . یک عنصر 1 در A وجود دارد به طوری که برای همه a در A : a 1 = 1 a = a .
  • نابودی توسط 0: 0 = 0 = 0 برای همه در .

بدیهیات بالا تعریف semiring . ما بیشتر نیاز داریم:

  • + است idempotent : + = برای همه در .

اکنون می توان یک ترتیب جزئی ≤ در A با تنظیم a ≤ b تنظیم کرد اگر و فقط اگر a + b = b (یا معادل آن: a ≤ b اگر و فقط اگر x در A وجود داشته باشد به طوری که a + x = b با هر تعریفی ، a ≤ b ≤ a به معنی a = b است . با استفاده از این سفارش ما می توانیم چهار بدیهیات گذشته در مورد عملیات تدوین و فرموله * :

  • 1 + ( * ) ≤ * برای همه در .
  • 1 + ( * ) ≤ * برای همه در .
  • اگر a و x در A باشند به طوری که ax ≤ x ، پس a * x ≤ x
  • اگر a و x در A باشند به طوری که xa ≤ x ، پس x ( a * ) ≤ x [3]

به طور شهودی ، باید یک + b را "اتحاد" یا "حداقل بالاترین حد" a و b و ab در نظر بگیریم که ضربی یکنواخت است ، به این معنا که a ≤ b به معنی ax ≤ bx است . ایده پشت اپراتور ستاره است * = 1 + + AA + AAA + ... از نقطه نظر تئوری زبان برنامه نویسی ، همچنین ممکن است تفسیر + به عنوان "انتخاب"، · عنوان "توالی" و * عنوان "تکرار" .

منبع

https://en.wikipedia.org/wiki/Kleene_algebra