ریاضیات

مثالها [ ویرایش ]

بگذارید Σ یک مجموعه محدود باشد ("الفبا") و اجازه دهید A مجموعه ای از تمام عبارات منظم بیش از Σ باشد. ما دو عبارت منظم را اگر یک زبان را توصیف کنند برابر می دانیم . سپس A جبر کلین را تشکیل می دهد. در حقیقت ، این یک جبر کلین آزاد است به این معنا که هر معادله ای در میان عبارات منظم از بدیهیات جبر کلین پیروی می کند و بنابراین در هر جبر کلین معتبر است.

باز هم بگذارید Σ یک الفبا باشد. بگذارید A مجموعه ای از همه زبانهای معمولی بیش از Σ باشد (یا مجموعه ای از همه زبانهای فاقد زمینه بیش از Σ باشد ؛ یا مجموعه ای از همه زبانهای بازگشتی بیش از Σ باشد ؛ یا مجموعه همه زبانها در بالای Σ باشد). سپس اتحاد (به صورت + نوشته شده است) و الحاق (به صورت · نوشته شده) از دو عنصر A دوباره متعلق به A است ، و همین طور عملیات ستاره Kleene که روی هر عنصر A اعمال می شود . ما یک جبر کلین A بدست می آوریم که 0 مجموعه خالی است و 1 مجموعه ای است که فقط شامل رشته خالی است.

اجازه دهید M یک مونوئید با عنصر هویت e و اجازه دهید A مجموعه ای از تمام زیر مجموعه های M باشد. برای دو جمله زیر مجموعه های S و T ، اجازه دهید S + T شود صنفی S و T و تنظیم ST = { ST  : ها در S و T در T }. S * به عنوان زیر مونوی M تولید شده توسط S تعریف می شود ، که می تواند به عنوان { e توصیف شود} ∪ S ∪ SS ∪ SSS ∪ ... سپس A جبری کلین تشکیل می دهد که 0 مجموعه خالی است و 1 برابر { e } است. یک ساخت مشابه می تواند برای هر دسته کوچک انجام شود .

زیرفضاهای خطی از یک unital جبر بیش از یک میدان جبر کلین تشکیل می دهد. با توجه به زیر فضاهای خطی V و W ، V + W را به عنوان جمع دو زیر فضایی تعریف کنید و 0 را به عنوان زیر فضایی پیش پا افتاده {0} تعریف کنید. تعریف V · W = طول {V · W | v ∈ V ، w ∈ W} ، دهانه خطی حاصل از بردارها از V و W به ترتیب. تعریف 1 = دهانه {I} ، دهانه واحد جبر. بسته شدن V است مجموع مستقیم تمام قدرت از V .

فرض کنید M مجموعه ای است و مجموعه ای از تمام است رابطه دوتایی در M . با در نظر گرفتن + به عنوان اتحادیه ، به عنوان ترکیب و * به عنوان بسته شدن انتقالی انعکاسی ، یک جبر کلین بدست می آوریم.

هر جبر بولی با عملیات و  در صورت استفاده از آن به جبر کلین تبدیل می شود  برای + ، برای · و تنظیم * = 1 برای همه .

برای اجرای الگوریتم Floyd-Warshall می توان از جبر کلین کاملاً متفاوتی استفاده کرد ، برای محاسبه کوتاهترین طول مسیر برای هر دو رأس یک نمودار جهت دار وزنی ، توسط الگوریتم کلین ، محاسبه یک عبارت منظم برای هر دو حالت یک اتومات محدود قطعی . با استفاده از خط اعداد واقعي توسعه يافته ، a + b را حداقل a و b و ab بدست آوريد تا جمع معمولي a و b باشد (با جمع + ∞ و −∞ به صورت + defined تعريف شود). a *به عنوان عدد صفر واقعی برای a منفی و −∞ برای a منفی تعریف شده است . این یک جبر کلین با عنصر صفر + ∞ و یک عنصر عدد واقعی صفر است. یک نمودار جهت دار وزنی را می توان بعنوان یک اتومات محدود قطعی در نظر گرفت ، که هر انتقال بر اساس وزن آن برچسب گذاری شده است. برای هر دو گره نمودار (حالت های اتومات) ، عبارات منظم محاسبه شده از الگوریتم کلین ، در این جبر کلین خاص ، تا کوتاهترین طول مسیر بین گره ها ارزیابی می شوند. [4]

خصوصیات [ ویرایش ]

0 ≤: صفر کوچکترین عنصر است برای همه در .

مجموع + b است که کوچکترین کران از و ب : ما باید ≤ + ب و ب ≤ + ب و اگر X یک عنصر از است با ≤ X و b ≤ X ، پس از آن + b ≤ X . به طور مشابه، 1 + ... + N است که حداقل بالای عناصر محدود 1، ... ، a n .

ضرب و جمع یکنواخت هستند: اگر a ≤ b ، پس

• a + x ≤ b + x ،

• تبر ≤ bx ، و

• xa ≤ xb

برای همه X در .

در مورد عملیات ستاره ، ما داریم

• 0 * = 1 و 1 * = 1 ،

• ≤ ب دلالت * ≤ ب * (یکنواختی)،

• N ≤ * برای هر عدد طبیعی n را ، که در آن N به عنوان تعریف N ضرب برابر از ،

• ( a * ) ( a * ) = a * ،

• ( a * ) * = a * ،

• 1 + a ( a * ) = a * = 1 + ( a * ) a ،

• ax = xb به معنی ( a * ) x = x ( b * ) است ،

• (( ab ) * ) a = a (( ba ) * ) ،

• ( a + b ) * = a * ( b ( a * )) * ، و

• pq = 1 = qp دلالت بر q ( a * ) p = ( qap ) * دارد . [5]

اگر A جبر کلین باشد و n یک عدد طبیعی باشد ، می توان مجموعه (M n ( A  متشکل از تمام ماتریس های n -by- n را با ورودی های A در نظر گرفت . با استفاده از مفاهیم معمولی جمع و ضرب ماتریس ، می توان عملکردی * منحصر به فرد تعریف کرد تا (M n ( A  به یک جبر کلین تبدیل شود.

تاریخچه [ ویرایش ]

کلین عبارات منظمی را ارائه داد و برخی از قوانین جبری آنها را بیان کرد. [6] [7] اگرچه او جبرهای کلین را تعریف نکرده است ، اما وی برای تصمیم گیری برای معادل سازی عبارات منظم درخواست کرد. [8] ردکو ثابت کرد که هیچ مجموعه محدودی از بدیهیات معادله ای نمی تواند جبر زبانهای منظم را مشخص کند. [9] Salomaa بدیهی سازی کاملی از این جبر ارائه داد ، البته به قوانین استنباط مسئله ای بستگی دارد. [10] مسئله تهیه مجموعه کاملی از بدیهیات ، که استخراج همه معادلات را در میان عبارات منظم امکان پذیر می کند ، توسط جان هورتون کانوی تحت عنوان جبرهای منظم مورد بررسی قرار گرفت . [11]با این حال ، بخش عمده ای از درمان او بی حد و حصر بود. در سال 1981 ، كوزن يك سيستم استنتاجي كاملاً معادله اي براي جبر زبان هاي معمول را ارائه داد. [12] در سال 1994 ، وی سیستم بدیهی فوق الذکر را ارائه داد ، که از برابری های بدون قید و شرط و شرط استفاده می کند [13] و از نظر معادله ای برای جبر زبانهای منظم کامل است ، یعنی دو عبارت منظم a و b فقط یک زبان را نشان می دهند اگر a = b از بدیهیات فوق پیروی می کند. [14]

تعمیم (یا ارتباط با ساختارهای دیگر) [ ویرایش ]

جبری کلین مورد خاصی از سمینارهای بسته است که سمینارهای شبه منظم یا سمینارهای لمان نیز نامیده می شود ، سمینارهایی که در آنها هر عنصر حداقل یک شبه معکوس دارد که معادله را برآورده می کند: a * = aa * + 1 = a * a + 1. این شبه معکوس لزوماً منحصر به فرد نیست. [15] [16] در جبر کلین ، a * کمترین راه حل برای معادلات ثابت است: X = aX + 1 و X = Xa + 1. [16]

سمیرم های بسته و جبرهای کلین در مشکلات مسیر جبری ظاهر می شوند ، این مسئله تعمیم کوتاه ترین مساله مسیر است. [16]

همچنین به [ ویرایش ] مراجعه کنید

• جبر عمل

• ساختار جبری

• ستاره کلین

• عبارت منظم

• سمینار کردن ستاره

• جبر ارزشیابی