Kanal tizimi (informatika) - Channel system (computer science) - Wikipedia

Yilda Kompyuter fanlari, a kanal tizimi a cheklangan davlat mashinasi o'xshash cheklangan holatdagi mashinani aloqa qilish unda bir-biri bilan aloqa qiladigan ko'plab tizimlar o'rniga o'zi bilan aloqa qiladigan yagona tizim mavjud. A kanal tizimi ga o'xshash pastga tushirish avtomati bu erda stek o'rniga navbat ishlatiladi. Ushbu navbatlar chaqiriladi kanallar. Intuitiv ravishda har bir kanal yuboriladigan va ketma-ketlikda o'qiladigan xabarlarning ketma-ketligini aks ettiradi.

Ta'rif

Kanal tizimi

Rasmiy ravishda, a kanal tizimi (yoki mukammal kanal tizimi) tople sifatida aniqlanadi bilan:

  • cheklangan to'plam davlatlarni boshqarish,
  • an dastlabki holat,
  • cheklangan alifbo (yozuvlarning soddaligi uchun, ruxsat bering ),
  • cheklangan to'plam kanallar,
  • ning cheklangan alifbosi xabarlar,
  • bilan o'tish qoidalarining cheklangan to'plami alifbo ustida cheklangan (bo'sh bo'lishi mumkin) so'zlar to'plami .[1]

Muallifga qarab, a kanal tizimi boshlang'ich holatga ega emas va bo'sh alifboga ega bo'lishi mumkin.[2]

Konfiguratsiya

A konfiguratsiya yoki global davlat kanal tizimining a ga tegishli koridor . Intuitiv ravishda, konfiguratsiya yugurish holatini bildiradi va bu uning - kanalda so'z bor .

Dastlabki konfiguratsiya , bilan bo'sh so'z.

Qadam

Intuitiv ravishda o'tish tizim holatni boshqarish uchun ketishi mumkinligini anglatadi ga yozish orqali kanalning oxirigacha . Xuddi shunday tizim holatni boshqarish uchun ketishi mumkinligini anglatadi ga olib tashlash orqali so'zni boshlash .

Rasmiy ravishda, konfiguratsiya berilgan va o'tish , mukammal qadam bor , bu erda qadam xat qo'shiladi oxirigacha - so'z. Xuddi shunday, o'tish ham berilgan , mukammal qadam bor bu erda birinchi harf - so'z va qadam davomida olib tashlangan.

Yugurish

A mukammal yugurish bu mukammal qadam, shaklning ketma-ketligi . Biz ruxsat berdik dan boshlangan mukammal yugurish borligini bildiring va tugaydi .

Tillar

Mukammal yoki yo'qolgan kanal tizimi berilgan , bir nechta tillar aniqlanishi mumkin.

Bir so'z tugadi tomonidan qabul qilinadi agar bu yugurish yorliqlarini birlashtirish bo'lsa . Tomonidan belgilangan til tomonidan qabul qilingan so'zlar to'plamidir .

Ning erishish mumkin bo'lgan konfiguratsiyasi to'plami , belgilangan konfiguratsiya to'plami sifatida aniqlanadi dastlabki holatdan erishish mumkin. Ya'ni. konfiguratsiyalar to'plami sifatida shu kabi .

Kanal berilgan , ning kanali koreyslar to'plamidir shu kabi .

Kanal tizimi va Turing mashinasi

Mukammal kanal tizimi bilan bog'liq muammolarning ko'pini hal qilib bo'lmaydi[1]:92.[3]:22 Buning sababi, bunday mashina a ning ishlashini simulyatsiya qilishi mumkin Turing mashinasi. Ushbu simulyatsiya endi chizilgan.

Berilgan Turing mashinasi , mukammal kanal tizimi mavjud Shunday qilib, har qanday yugurish uzunlik yugurish orqali simulyatsiya qilinishi mumkin uzunlik . Intuitiv ravishda ushbu simulyatsiya shunchaki simulyatsiya qilingan Turing mashinasining butun lentasini kanalda bo'lishidan iborat. Keyin tarkib kanali to'liq o'qiladi va darhol kanalda qayta yoziladi, faqat bitta istisno bilan, Turing mashinasini hisoblash qismini qadamini taqlid qilish uchun Turing mashinasining boshini ifodalovchi qismi o'zgartiriladi.

Variantlar

Kanal tizimlarining bir nechta variantlari kiritildi. Quyida keltirilgan ikkita variant Turing mashinasini simulyatsiya qilishga imkon bermaydi va shu bilan bir nechta qiziqish muammosini hal qilishga imkon beradi.

Bitta kanalli mashina

Bir kanalli mashina - bu bitta kanaldan foydalanadigan kanal tizimidir. Xuddi shu ta'rif kanal tizimining barcha variantlari uchun ham amal qiladi.

Hisoblagich mashinasi

Agar kanal tizimining alifbosi bitta xabarni o'z ichiga olgan bo'lsa, unda har bir kanal asosan hisoblagich hisoblanadi. Shundan kelib chiqadiki, ushbu tizimlar aslida Minsky mashinalari. Biz bunday tizimlarni chaqiramiz hisoblagichlar. Xuddi shu ta'rif kanal tizimining barcha variantlari uchun amal qiladi.[4]:337

To'liq ko'rsatilgan protokol

A to'liq ko'rsatilgan protokol (CSP) kanal tizimi sifatida aniq belgilanadi. Biroq, qadam va yugurish tushunchalari boshqacha tarzda belgilanadi.

CSP ikki turdagi qadamlarni qabul qiladi. Yuqorida tavsiflangan mukammal qadamlar va a xabarlarni yo'qotish o'tish qadam. Xabarlarni yo'qotish bosqichiga o'tishni belgilaymiz .

Bo'shliq

A yo'qotish kanallari tizimi yoki yo'qolish xatosiga qodir bo'lgan mashina bu to'liq ko'rsatilgan protokolning kengaytmasi bo'lib, unda harflar har qanday joyda yo'qolishi mumkin.

Yo'qotilgan kanal tizimi ikki xil bosqichni tan oladi. Yuqorida tavsiflangan mukammal qadamlar va yo'qotish bosqichi. Biz yo'qotadigan qadamni belgilaymiz, .

Kanallar ularga xabar yuborilishi bilanoq bo'shatilgan yugurish ushbu ta'rifga muvofiq amal qiladi. Shu sababli, ushbu tizimlarga ba'zi adolatli shartlar kiritilishi mumkin.

Kanalning adolatliligi

Kanalga xabar berilgan , "Run" ga nisbatan kanallar yarmarkasi deb aytiladi agar, agar xat yuboriladigan cheksiz ko'p qadamlar mavjud bo'lsa unda xat o'qiladigan cheksiz ko'p qadamlar mavjud . [5]:88

Hisoblash, agar u har bir kanalga nisbatan kanalli bo'lsa, adolatli deb aytiladi .

Xolislik

Xolislik sharti - bu kanal va xat ham ko'rib chiqiladigan kanalning adolat shartini cheklash.

Xabar berilgan va kanal , yugurish nisbatan xolis deyiladi va agar unda cheksiz ko'p qadamlar mavjud bo'lsa yuboriladi unda cheksiz ko'p qadamlar mavjud dan o'qiladi . [5]:83

Hisoblash kanalga nisbatan xolis deyiladi agar u nisbatan xolis bo'lsa va xabarlar . Bu aytilgan xolis agar bu har bir kanalga nisbatan xolis bo'lsa .

Xabar adolatli

Xabarning adolat xususiyati xolislikka o'xshaydi, ammo cheksiz sonli qadam bo'lsa, shart bajarilishi kerak. o'qilishi mumkin. Rasmiy ravishda, yugurish, xabarlarga nisbatan faire deb ataladi va agar unda cheksiz ko'p qadamlar mavjud bo'lsa yuboriladi va cheksiz ko'p qadam bir holatda sodir bo'ladi Shunday qilib o'tish mavjud , unda cheksiz ko'p qadamlar mavjud dan o'qiladi . [5]:88

Cheklanish

Ikkala mukammal qadam o'rtasida olib tashlangan harflar soni chegaralangan bo'lsa, chopish cheklangan yo'qotishlarga olib keladi deyiladi.[4]:339

Xatolarni kiritish

A xato kiritishga qodir bo'lgan mashina har qanday joyda harflar paydo bo'lishi mumkin bo'lgan kanal tizimining kengaytmasi.

Xatolikka yo'l qo'yadigan mashina ikki xil bosqichni tan oladi. Yuqorida tavsiflangan mukammal qadamlar va qo'shilish bosqichlari. Qo'shishni bosqichma-bosqich belgilaymiz .[3]:25

Ikki nusxadagi xatolar

A takrorlash xatosiga qodir bo'lgan mashina bu xato kiritishga qodir bo'lgan mashinaning kengaytmasi bo'lib, unda kiritilgan xat oldingi xatning nusxasi hisoblanadi.

Xatolikka yo'l qo'yadigan mashina ikki xil bosqichni tan oladi. Yuqorida tavsiflangan mukammal qadamlar va takroriy qadamlar. Qo'shishni bosqichma-bosqich belgilaymiz .[3]:26

A takrorlanmaydigan mashina takrorlash xatosiga qodir - bu har bir kanalda harflar maxsus yangi # harfi va xabar alifbosidan oddiy harf bilan almashinishini ta'minlaydigan mashinadir. Agar bu "caes" bo'lmasa, demak u takrorlangan va "rad" bo'lgan deganidir. Ushbu jarayon har qanday kanal tizimini takrorlashda xatolikka yo'l qo'yadigan mashinaga kodlash imkonini beradi, shu bilan birga uni xatolarga yo'l qo'ymaslikka majbur qiladi. Kanal tizimlari mashinalarni simulyatsiya qilishi mumkinligi sababli, takrorlashda xatolikka yo'l qo'yadigan mashinalar Turing mashinasini taqlid qilishi mumkin.

Xususiyatlari

Yo'qotish mumkin bo'lgan konfiguratsiyalar to'plami yo'qolgan kanal mashinalari uchun taniqli[3]:23 va xatolarni kiritishga qodir bo'lgan mashinalar[3]:26. Uni takrorlashda xatolikka yo'l qo'yadigan mashina uchun rekursiv ravishda sanab o'tish mumkin[3]:27.

Muammolar va ularning murakkabligi

Ushbu bo'limda kanal tizimidagi muammolar ro'yxati va bunday tizimlarning variantlariga nisbatan ularning murakkabligi hal etilishi mumkin.

Tugatish muammosi

The tugatish muammosi kanal tizimiga qarab qaror qabul qilishdan iborat va dastlabki konfiguratsiya hamma ishlaydi dan boshlab cheklangan. Tizim hisoblagich bo'lsa ham, mukammal kanal tizimlarida bu muammoni hal qilib bo'lmaydi[4] yoki u bitta kanalli mashina bo'lganda[3]:26.

Bu muammo hal qiluvchi lekin emasibtidoiy rekursiv yo'qotish kanallari tizimi ustidan.[2]:10 Ushbu muammo xatolarni kiritishga qodir bo'lgan mashina uchun juda muhimdir[3]:26.

Reachability muammosi

The erishish imkoniyati muammo kanal tizimini hisobga olgan holda qaror qabul qilishdan iborat va ikkita dastlabki konfiguratsiya va yugurish bormi dan ga . Ushbu muammoni mukammal kanal tizimlarida hal qilish mumkin emas hal qiluvchi lekin emasibtidoiy rekursiv yo'qotish kanallari tizimi ustidan.[2]:10 Ushbu muammo xatolarni kiritishga qodir bo'lgan mashina oldida hal qilinadi.[3]:26

Reachability muammosi

The muammoni echish vorisiz erishish mumkin bo'lgan konfiguratsiya mavjudligini hal qilishdan iborat. Ushbu muammoni yo'qotish kanallari tizimiga nisbatan hal qilish mumkin[2]:10 va xatolarni kiritishga qodir bo'lgan mashina ustida juda ahamiyatli[3]:26. Bundan tashqari, taymer mashinasida ham hal qilinadi.[6]

Modelni tekshirish muammosi

The modelni tekshirish muammosi tizim berilganligi to'g'risida qaror qabul qilishdan iborat va a CTL * * -formula yoki a LTL -formula yoki a tomonidan belgilangan til bo'ladimi qondiradi . Ushbu muammoni yo'qotish kanallari tizimiga nisbatan hal qilib bo'lmaydi.[3]:23[5]

Takroriy holat muammosi

The takrorlanadigan davlat muammosi kanal tizimiga qarab qaror qabul qilishdan iborat va dastlabki konfiguratsiya va davlat mavjudmi yoki yo'qmi , boshlab , davlat orqali cheksiz tez-tez borish . Ushbu muammoni yo'qotish kanallari tizimida, hatto bitta kanalda ham hal qilish mumkin emas.[3]:23[5]:80

Ekvivalent cheklangan davlat mashinasi

Tizim berilgan , a ni hisoblaydigan algoritm yo'q cheklangan davlat mashinasi vakili yo'qotuvchi kanal tizimining sinfi uchun.[3]:24 Ushbu muammo xato kiritishga qodir bo'lgan mashina oldida hal qilinadi.[3]:26

Cheklov muammosi

The cheklov muammosi erishish mumkin bo'lgan konfiguratsiya to'plamining cheklanganligini aniqlashdan iborat. Ya'ni. har bir kanal tarkibining uzunligi chegaralangan. Ushbu muammo xatolarni kiritishga qodir bo'lgan mashina uchun juda muhimdir[3]:26. Bundan tashqari, taymer mashinasida ham hal qilinadi.[6]

Oxir-oqibat mulk

The oxir-oqibat xususiyati, yoki muqarrarlik xususiyati muammo kanal tizimini hisobga olgan holda qaror qabul qilishdan iborat va to'plam Hammasi bajariladimi, konfiguratsiyalar dan boshlab ning konfiguratsiyasidan o'tadi . Ushbu muammoni xolislik bilan yo'qotadigan kanal tizimi uchun hal qilish mumkin emas[5]:84 va boshqa ikkita adolatli cheklovlar bilan.[5]:87

Xavfsizlik xususiyati

The xavfsizlik xususiyati muammo kanal tizimini hisobga olgan holda qaror qabul qilishdan iborat va oddiy to'plam yo'qmi

Strukturaviy tugatish

The tarkibiy tugatish muammo kanal tizimini hisobga olgan holda qaror qabul qilishdan iborat agar tugatish muammosi mavjud bo'lsa har bir dastlabki konfiguratsiya uchun. Ushbu muammoni hatto qarshi mashinada ham hal qilish mumkin emas.[4]:342

Ierarxik davlat mashinasi bilan aloqa o'rnatish

Ierarxik holat mashinalari - bu davlatlarning o'zi boshqa mashinalar bo'lishi mumkin bo'lgan cheklangan davlat mashinalari. Aloqa qiluvchi cheklangan davlat mashinasi bir-biriga o'xshashligi bilan ajralib turadiganligi sababli, a-dagi eng muhim xususiyat davlatning ierarxik mashinasini aloqa qilish bu ierarxiya va bir vaqtda yashashning mavjudligidir. Bu juda mos deb topilgan edi, chunki bu mashina ichidagi o'zaro ta'sirni anglatadi.

Shu bilan birga, iyerarxiya va bir vaqtda yashashning o'zaro bog'liqligi, tilni inklyuziya qilish, til ekvivalenti va barcha universallikka zarar etkazishi isbotlangan.[7]

Adabiyotlar

  1. ^ a b Abdulla, Parosh Aziz; Jonsson, Bengt (1996). "Ishonchsiz kanallar bilan dasturlarni tekshirish". Axborot va hisoblash. 127 (2): 91–101. doi:10.1006 / inco.1996.0053.
  2. ^ a b v d Schnoebelen, Ph (2002 yil 15 sentyabr). "Yo'qotilgan kanal tizimlarini tekshirish primitiv rekursiv murakkablikka ega". Axborotni qayta ishlash xatlari. 83 (5): 251–261. doi:10.1016 / S0020-0190 (01) 00337-4.
  3. ^ a b v d e f g h men j k l m n o Séce, Jerar; Finkel, Alen (1996 yil 10-yanvar). "Ishonchsiz kanallarni mukammal kanallardan ko'ra tekshirish osonroq". Axborot va hisoblash. 124 (1): 20–31. doi:10.1006 / inco.1996.0003.
  4. ^ a b v d Mayr, Richard (2008 yil 17 mart). "Ishonchsiz hisoblashda hal qilinmaydigan muammolar". Nazariy kompyuter fanlari. 297 (1–3): 337–354. doi:10.1016 / S0304-3975 (02) 00646-1.
  5. ^ a b v d e f g Abdulla, Parosh Aziz; Jonsson, Bengt (1996 yil 10 oktyabr). "Ishonchsiz kanallari bo'lgan dasturlar uchun hal etilmaydigan tekshiruv muammolari". Axborot va hisoblash. 130 (1): 71–90. doi:10.1006 / inco.1996.0083.
  6. ^ a b Rozier, Lui E.; Gouda, Mohamed G (1983). Muayyan sonli davlat mashinalari bilan aloqa qilish sinfining rivojlanishini hal qilish (Hisobot).
  7. ^ Alur, Rajeev; Kannan, Sampat; Yannakakis, Mixalis. "Ierarxik davlat mashinalari bilan aloqa o'rnatish", avtomatika, tillar va dasturlash. Praga: ICALP, 1999 yil