Шектеу - Set constraint

Бастап алынған шектеулерді орнатыңыз дерексіз түсіндіру туралы Коллатц алгоритм

Жылы математика және теориялық информатика, а шектеу қою - жиындарының арасындағы теңдеу немесе теңсіздік шарттар. Жүйелеріне ұқсасжылы )теңдеулер сандар арасында қойылған шектеулер жүйесін шешудің әдістері зерттеледі. Әр түрлі тәсілдер әр түрлі операторларды қабылдайды («∪», «∩», «» және функционалды қолдану сияқты)^{[1 ескерту]} жиындарда және әр түрлі (в) теңдеу қатынастары («=», «⊆» және «⊈» сияқты) жиынтық өрнектер арасында.

Жиынтық шектеулер жүйелері жиынтықтарды сипаттау үшін пайдалы (атап айтқанда шексіз) негізгі шарттар.^{[2 ескерту]}Олар бағдарламалық талдауда туындайды, дерексіз түсіндіру, және қорытынды шығару.

Ағаштың әдеттегі грамматикасына қатысы

Әрқайсысы ағаштың тұрақты грамматикасы жүйелі түрде оның минималды шешімі грамматиканың ағаш тіліне сәйкес болатындай етіп енгізілген жүйеге айналуы мүмкін.

Мысалы, ережелермен бірге грамматика (сәйкесінше кіші және үлкен регистрлердің әріптерімен көрсетілген терминальды және терминальды емес белгілер)

Bool_G	→ жалған
Bool_G	→ шын
BList_G	→ нөл
BList_G	→ минус(Bool_G,BList_G)
BList1_G	→ минус(шын,BList_G)
BList1_G	→ минус(жалған,BList1_G)

орнатылған қосу жүйесіне айналады (тұрақты және айнымалылар сәйкесінше кіші және бас әріптермен жазылады):

Bool_S	⊇ жалған
Bool_S	⊇ шын
BList_S	⊇ нөл
BList_S	⊇ минус(Bool_S,BList_S)
BList1_S	⊇ минус(шын,BList_S)
BList1_S	⊇ минус(жалған,BList1_S)

Бұл жүйенің минималды шешімі бар, яғни. («L(N) «ағаш емес тілге сәйкес келетін ағаш тілін белгілеу N жоғарыдағы ағаш грамматикасында):

Bool_S	= L(Bool_G)	= { жалған, шын }
BList_S	= L(BList_G)	= { нөл, минус(жалған,нөл), минус(шын,нөл), минус(жалған,минус(жалған,нөл)), ... }
BList1_S	= L(BList1_G)	= { нөл, минус(шын,нөл), минус(шын,минус(жалған,нөл)),... }

Жүйенің максималды шешімі тривиальды болып табылады; ол барлық айнымалыларға барлық терминдер жиынтығын тағайындайды.

Әдебиет

Айкен, А. (1995). Шектеулер қойыңыз: нәтижелер, қолданбалар және болашақ бағыттар (Техникалық есеп). Унив. Беркли.
Айкен, А., Козен, Д., Варди, М., Виммерс, Э.Л. (Мамыр 1993). Белгіленген шектеулердің күрделілігі (Техникалық есеп). Корнелл университетінің компьютерлік ғылымдар бөлімі. 93–1352.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Айкен, А., Козен, Д., Варди, М., Виммерс, Э.Л. (1994). «Белгіленген шектеулердің күрделілігі». Информатика логикасы93. LNCS. 832. Спрингер. 1-17 бет.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Айкен, А., Виммерс, Э.Л. (1992). «Белгіленген шектеулер жүйесін шешу (кеңейтілген реферат)». IEEE информатикадағы логика бойынша жетінші жыл сайынғы симпозиум. 329–340 бб.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Бахмаир, Лео, Ганцингер, Харальд, Валдманн, Уве (1992). Жиынтық шектеулер - Монадалық класс (Техникалық есеп). Max-Planck-Institut für Informatik. б. 13. CiteSeerX 10.1.1.32.3739. MPI-I-92-240.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Бахмаир, Лео, Ганцингер, Харальд, Валдманн, Уве (1993). «Белгіленген шектеулер - монадалық класс». Информатикадағы логика бойынша IEEE сегіз жылдық симпозиумы. 75-83 бет.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Charatonik, W. (1994 ж. Қыркүйек). «Кейбір теңдеулер теорияларына шектеулер қойыңыз». Proc. 1-ші инт. Конф. Есептеу логикасындағы шектеулер туралы (CCL). LNCS. 845. Спрингер. 304-319 бет.
Чаратоник, Витольд; Подельский, Андреас (2002). «Шектеуді қиылысумен орнатыңыз». Ақпарат және есептеу. 179 (2): 213–229. дои:10.1006 / inco.2001.2952.
Чаратоник, В., Подельский, А. (1998). Тобиас Нипков (ред.). Бірлескен шектеулер. LNCS 1379. Springer-Verlag. 211–225 бб.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Charatonik, W., Talbot, J.-M. (2002). Тисон, С. (ред.) Проекциямен атомдық шектеулер. LNCS 2378. Springer. 311-325 бб.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Джиллерон, Р., Тисон, С., Томмаси, М. (1993). «Ағаш автоматтарын пайдаланып шектеулер жүйесін шешу». Информатиканың теориялық аспектілері бойынша 10-жылдық симпозиум. LNCS. 665. Спрингер. 505-514 бб.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Хайнце, Н., Джаффар, Дж. (1990). «Белгіленген шектеулер сыныбы бойынша шешім қабылдау рәсімі (кеңейтілген реферат)». Информатикадағы логика бойынша IEEE бесінші симпозиумы. 42-51 бет.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Хайнце, Н., Джаффар, Дж. (Ақпан 1991). Белгіленген шектеулер класы үшін шешім қабылдау рәсімі (Техникалық есеп). Карнеги Меллон университетінің информатика мектебі.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Козен, Д. (1993). «Белгіленген шектеулердің логикалық аспектілері» (PDF). Информатика логикасы93. LNCS. 832. 175–188 беттер.
Козен, Д. (1994). «Шектеу мен логикалық бағдарламалауды орнату». CCL. LNCS. 845.
Декстер Козен (1998). «Шектеу мен логикалық бағдарламалауды орнату». Ақпарат және есептеу. 142: 2–25. дои:10.1006 / inco.1997.2694.
Урибе, Т.Е. (1992). «Белгіленген шектеулерді пайдаланып сұрыпталған унификация». Proc. CADE – 11. LNCS. 607. 163–177 беттер.

Теріс шектеулер туралы әдебиеттер

Айкен, А., Козен, Д., Виммерс, Э.Л. (Маусым 1993). Теріс шектеулері бар жиынтық шектеулер жүйесінің шешімділігі (Техникалық есеп). Корнелл университетінің компьютерлік ғылымдар бөлімі. 93–1362.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Charatonik, W., Pacholski, L. (Jul 1994). «Теңдікке қатысты теріс шектеулер». Информатикадағы логика бойынша IEEE тоғызыншы жыл сайынғы симпозиум. 128–136 бет.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Р.Гиллерон; С.Тисон; М.Томмаси (1993). «Теріс ішкі қатынастарымен қойылған шектеулер жүйесін шешу». 34-ші симптомның материалдары. Информатика негіздері туралы. 372-380 бб.
Джиллерон, Р., Тисон, С., Томмаси, М. (1993). Теріс ішкі қатынастарымен қойылған шектеулер жүйесін шешу (Техникалық есеп). Laboratoire d'Informatique Fondamentale de Lille. IT 247.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
Стефанссон, К. (1993 ж. Тамыз). Теріс шектеулері бар жиынтық шектеулер жүйесі NEXPTIME-толық болып табылады (Техникалық есеп). Корнелл университетінің компьютерлік ғылымдар бөлімі. 93–1380.
Стефанссон, К. (1994). «Теріс шектеулері бар жиынтық шектеулер жүйесі NEXPTIME-толық». Информатикадағы логика бойынша IEEE тоғызыншы жыл сайынғы симпозиум. 137–141 бб.

Ескертулер

^ Егер f болып табылады n-ary функциясы бір мерзімде қабылданған символ, содан кейін «f(E₁,...,E_n) «жиынтықты білдіретін жиынтық өрнек { f(т₁,...,т_n) : т₁∈E₁ және ... және т_n∈E_n }, қайда E₁,...,E_n ретімен өрнектер орнатылады.
^ Бұл мысалы сипаттауға ұқсас. а рационалды сан теңдеудің шешімі ретінде а⋅х + б = 0, бірге бүтін коэффициенттер а, б.

Бұл математикалық логика - қатысты мақала а бұта. Сіз Уикипедияға көмектесе аласыз оны кеңейту.

P ≟ NP

Бұл теориялық информатика - қатысты мақала а бұта. Сіз Уикипедияға көмектесе аласыз оны кеңейту.

[1] Егер f болып табылады n-ary функциясы бір мерзімде қабылданған символ, содан кейін «f(E₁,...,E_n) «жиынтықты білдіретін жиынтық өрнек { f(т₁,...,т_n) : т₁∈E₁ және ... және т_n∈E_n }, қайда E₁,...,E_n ретімен өрнектер орнатылады.

[2] Бұл мысалы сипаттауға ұқсас. а рационалды сан теңдеудің шешімі ретінде а⋅х + б = 0, бірге бүтін коэффициенттер а, б.

[1 ескерту]

[2 ескерту]