Об отношении совместимости в исчислении Ламбека и в его варианте с операциями замещения (1104173), страница 2
Текст из файла (страница 2)
 ÷àñòíîñòè, â ðàáîòå Ì. Êàíàäçàâûïðåäëàãàëîñü ðàñøèðèòü èñ÷èñëåíèå Ëàìáåêà çà ñ÷¼ò àääèòèâíûõ ñâÿçîê äëÿ ïåðåñå÷åíèÿ è îáúåäèíåíèÿ ([14]).  êàòåãîðèàëüíûõ ãðàììàòèêàõ çàâèñèìîñòåé (categorial dependency grammars, [9]) À. Äèêîâñêîãîè Ì. Äåõòÿðÿ ôðàãìåíò èñ÷èñëåíèÿ Ëàìáåêà îáîãàùàåòñÿ çà ñ÷¼ò ââåäåíèÿ ñòðóêòóðû çàâèñèìîñòåé. Ã. Ìîððèëë è Õ.-Ì. Ìåðåíñèàíî ([21])äîáàâèëè ê ñòàíäàðòíûì ñâÿçêàì èñ÷èñëåíèÿ Ëàìáåêà îïåðàöèè çàìåùåíèÿ, îïóñêàíèÿ è ïîäíÿòèÿ. Êàê ïîêàçàíî â ðàáîòå [24], ïîëó÷åííîåèñ÷èñëåíèå DL ïîçâîëÿåò ìîäåëèðîâàòü áîëüøèíñòâî èçâåñòíûõ íåïðî-7åêòèâíûõ ñèíòàêñè÷åñêèõ êîíñòðóêöèé.Öåëü ðàáîòûÏîëó÷åíèå àëãîðèòìà ïîñòðîåíèÿ ñîâìåùàþùåãî òèïà äëÿ ïàðûñîâìåñòèìûõ òèïîâ â èñ÷èñëåíèè Ëàìáåêà; ïîëó÷åíèå íèæíåé è âåðõíåéîöåíêè íà ìèíèìàëüíóþ äëèíó ñîâìåùàþùåãî òèïà äëÿ çàäàííûõ òèïîâ èñ÷èñëåíèÿ Ëàìáåêà â çàâèñèìîñòè îò èõ äëèíû; àëãåáðàè÷åñêàÿ õàðàêòåðèçàöèÿ ñîâìåñòèìîñòè â èñ÷èñëåíèè Ëàìáåêà ñ k îïåðàöèÿìè çàìåùåíèÿ; àëãåáðàè÷åñêàÿ õàðàêòåðèçàöèÿ ñîâìåñòèìîñòè â èñ÷èñëåíèèËàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ; äîêàçàòåëüñòâî çàìêíóòîñòè êëàññàÿçûêîâ, ïîðîæäàåìûõ ðàçðûâíûìè ãðàììàòèêàìè Ëàìáåêà, îòíîñèòåëüíî ïåðåñå÷åíèÿ ñ àâòîìàòíûìè ÿçûêàìè, íå ñîäåðæàùèìè ïóñòîãî ñëîâà;ïîëó÷åíèå àëãîðèòìà ïîñòðîåíèÿ ðàçðûâíîé ãðàììàòèêè Ëàìáåêà äëÿçàäàíèÿ ïåðåñå÷åíèÿ ÿçûêà, ïîðîæäàåìîãî íåêîòîðîé ðàçðûâíîé ãðàììàòèêîé Ëàìáåêà è àâòîìàòíîãî ÿçûêà, íå ñîäåðæàùåãî ïóñòîãî ñëîâà.Ìåòîäû èññëåäîâàíèÿ ðàáîòå ïðèìåíÿþòñÿ ìåòîäû àëãåáðû, òåîðèè äîêàçàòåëüñòâ,òåîðèè ãðàôîâ è òåîðèè àëãîðèòìîâ.
Äëÿ äîêàçàòåëüñòâà âåðõíåé îöåíêè íà äëèíó ñîâìåùàþùåãî òèïà â èñ÷èñëåíèè Ëàìáåêà àâòîðîì êîíñòðóêòèâíî ñòðîèòñÿ ñîâìåùàþùèé òèï, ïðè ýòîì êàæäîìó òèïó ñòàâèòñÿ â ñîîòâåòñòâèå íåñêîëüêî ñîâìåñòèìûõ ñ íèì òèïîâ ñïåöèàëüíîãîâèäà. Äëÿ äîêàçàòåëüñòâà íèæíåé îöåíêè íà äëèíó ñîâìåùàþùåãî òèïà â èñ÷èñëåíèè Ëàìáåêà èñïîëüçóåòñÿ íåîáõîäèìîå óñëîâèå âûâîäèìîñòè, âûðàæåííîå â ãðàôè÷åñêîé ôîðìå (òàê íàçûâàåìûå ñåòè äîêàçà-òåëüñòâà ). Ïðè äîêàçàòåëüñòâå êðèòåðèÿ ñîâìåñòèìîñòè â èñ÷èñëåíèèËàìáåêà ñ k îïåðàöèÿìè çàìåùåíèÿ âíà÷àëå äëÿ êàæäîãî òèïà àâòîðîì ñòðîèòñÿ ñîâìåñòèìûé ñ íèì òèï ñïåöèàëüíîãî âèäà, ïîñëå ÷åãî ñïîìîùüþ àëãåáðàè÷åñêèõ ìåòîäîâ èññëåäóþòñÿ êëàññû ýêâèâàëåíòíîñòèïî îòíîøåíèþ ñîâìåñòèìîñòè.
Äëÿ äîêàçàòåëüñòâà çàìêíóòîñòè êëàññàÿçûêîâ, ïîðîæäàåìûõ ðàçðûâíûìè ãðàììàòèêàìè Ëàìáåêà, îòíîñèòåëüíî ïåðåñå÷åíèÿ ñ àâòîìàòíûìè ÿçûêàìè, íå ñîäåðæàùèìè ïóñòîãî ñëîâà,8àâòîðîì èñïîëüçóþòñÿ ñâîéñòâà âûâîäîâ â èñ÷èñëåíèè Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ äëÿ ñåêâåíöèé ñïåöèàëüíîãî âèäà.Íàó÷íàÿ íîâèçíàÐåçóëüòàòû äèññåðòàöèè ÿâëÿþòñÿ íîâûìè.  äèññåðòàöèè ïîëó÷åíû ñëåäóþùèå îñíîâíûå ðåçóëüòàòû:1.
Äëÿ ëþáûõ äâóõ ñîâìåñòèìûõ òèïîâ èñ÷èñëåíèÿ Ëàìáåêà ñóùåñòâóåò ñîâìåùàþùåé òèï, ÷üÿ äëèíà íå ïðåâîñõîäèò íåêîòîðîãî ôèêñèðîâàííîãî êâàäðàòè÷íîãî ìíîãî÷ëåíà îò äëèí èñõîäíûõ òèïîâ.2. Ñóùåñòâóåò áåñêîíå÷íîå ñåìåéñòâî ïàð ñîâìåñòèìûõ òèïîâ, ñîäåðæàùåå ïàðû òèïîâ ñêîëü óãîäíî áîëüøîé äëèíû, òàêîå ÷òî äëÿ êàæäîé èç ïàð äëèíà ñîâìåùàþùåãî òèïà îãðàíè÷åíà ñíèçó íåêîòîðûìôèêñèðîâàííûì êâàäðàòè÷íûì ìíîãî÷ëåíîì îò äëèí èñõîäíûõ òèïîâ.3. Òèïû èñ÷èñëåíèÿ Ëàìáåêà ñ k îïåðàöèÿìè çàìåùåíèÿ ñîâìåñòèìûòîãäà è òîëüêî òîãäà, êîãäà ñîâïàäàþò èõ èíòåðïðåòàöèè â ñâîáîäíîéàáåëåâîé ãðóïïå, ïîðîæä¼ííîé ïðèìèòèâíûìè òèïàìè.4. Òèïû èñ÷èñëåíèÿ Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ ñîâìåñòèìû òîãäà è òîëüêî òîãäà, êîãäà ñîâïàäàþò èõ èíòåðïðåòàöèè â ñâîáîäíîéàáåëåâîé ãðóïïå, ïîðîæä¼ííîé ïðèìèòèâíûìè òèïàìè.5.
Êëàññ ÿçûêîâ, ïîðîæäàåìûõ ðàçðûâíûìè ãðàììàòèêàìè Ëàìáåêà,çàìêíóò îòíîñèòåëüíî ïåðåñå÷åíèÿ ñ àâòîìàòíûìè ÿçûêàìè, íå ñîäåðæàùèìè ïóñòîãî ñëîâà.Òåîðåòè÷åñêàÿ è ïðàêòè÷åñêàÿ öåííîñòüÐàáîòà èìååò òåîðåòè÷åñêèé õàðàêòåð. Ïîëó÷åííûå â íåé ðåçóëüòàòû ïðåäñòàâëÿþò èíòåðåñ äëÿ ìàòåìàòè÷åñêîé ëèíãâèñòèêè. Îíè ìîãóò áûòü èñïîëüçîâàíû ïðè èññëåäîâàíèè ñâîéñòâ ãðàììàòèê, îñíîâàííûõ íà âàðèàíòàõ èñ÷èñëåíèÿ Ëàìáåêà. Ïîëó÷åííûå ðåçóëüòàòû ìîãóòáûòü ïîëåçíû ñïåöèàëèñòàì, ðàáîòàþùèì â ÌÃÓ èì. Ì.
Â. Ëîìîíîñîâà(Ìîñêâà), Ìàòåìàòè÷åñêîì èíñòèòóòå èì. Â. À. Ñòåêëîâà ÐÀÍ (Ìîñêâà),ÈÏÏÈ èì. À. À. Õàðêåâè÷à ÐÀÍ (Ìîñêâà), ÏÎÌÈ èì. Â. À. Ñòåêëî9âà ÐÀÍ (Ñàíêò-Ïåòåðáóðã), Èíñòèòóòå ìàòåìàòèêè èì. Ñ. Ë. ÑîáîëåâàÑÎ ÐÀÍ (Íîâîñèáèðñê), Óðàëüñêîì ôåäåðàëüíîì óíèâåðñèòåòå (Åêàòåðèíáóðã), Òâåðñêîì ãîñóäàðñòâåííîì óíèâåðñèòåòå (Òâåðü) è äðóãèõíàó÷íûõ öåíòðàõ.Àïðîáàöèÿ ðàáîòûÐåçóëüòàòû äèññåðòàöèè äîêëàäûâàëèñü íà ñëåäóþùèõ ñåìèíàðàõè ìåæäóíàðîäíûõ êîíôåðåíöèÿõ:• íà ñåìèíàðå ¾Àëãîðèòìè÷åñêèå âîïðîñû àëãåáðû è ëîãèêè¿ ïîä ðóêîâîäñòâîì àêàäåìèêà ÐÀÍ Ñ. È.
Àäÿíà, Ìîñêâà, Ðîññèÿ, 18 äåêàáðÿ2012 ãîäà è 25 ìàðòà 2014 ãîäà;• íà Ìîñêîâñêèõ ÷òåíèÿõ ïî êîíñòðóêòèâíîé ëîãèêå è ïðåäñòàâëåíèþçíàíèé, Ìîñêâà, Ðîññèÿ, 3031 ìàÿ 2012 ãîäà;• íà ìåæäóíàðîäíîé êîíôåðåíöèè ¾Ìàëüöåâñêèå ÷òåíèÿ¿, Íîâîñèáèðñê, Ðîññèÿ, 1216 íîÿáðÿ 2012 ãîäà;• íà ìåæäóíàðîäíîé êîíôåðåíöèè ¾Òåîðåòè÷åñêàÿ èíôîðìàòèêà âÐîññèè¿ (Computer Science in Russia 2013), Åêàòåðèíáóðã, Ðîññèÿ,2429 èþíÿ 2013 ãîäà;• íà ìåæäóíàðîäíîé êîíôåðåíöèè ¾Ôîðìàëüíûå ãðàììàòèêè¿ (Formal Grammar 2013), Äþññåëüäîðô, Ãåðìàíèÿ, 1011 àâãóñòà 2013ãîäà.ÏóáëèêàöèèÎñíîâíûå ðåçóëüòàòû äèññåðòàöèè îïóáëèêîâàíû â ðàáîòàõ [38][41], èç íèõ ïåðâûå òðè â æóðíàëàõ èç ïåðå÷íÿ ÂÀÊ.Ñòðóêòóðà ðàáîòûÐàáîòà ñîñòîèò èç ââåäåíèÿ, 6 ãëàâ, ñîäåðæàùèõ 23 ðàçäåëà, ïðåäìåòíîãî óêàçàòåëÿ è ñïèñêà ëèòåðàòóðû.
Áèáëèîãðàôèÿ ñîäåðæèò 41 íàèìåíîâàíèé. Òåêñò äèññåðòàöèè èçëîæåí íà 120 ñòðàíèöàõ.10Êðàòêîå ñîäåðæàíèå äèññåðòàöèèÃëàâà 1èìååò âñïîìîãàòåëüíûé õàðàêòåð.  íåé ââîäÿòñÿ îñíîâ-íûå ïîíÿòèÿ, íåîáõîäèìûå äëÿ äàëüíåéøåãî èçëîæåíèÿ, à òàêæå ôîðìóëèðóþòñÿ èçâåñòíûå ðàíåå ðåçóëüòàòû. Âðàçäåëå 1.1ôîðìóëèðóåòñÿàêñèîìàòèêà èñ÷èñëåíèÿ Ëàìáåêà L è ïðîñòåéøèå ñâîéñòâà âûâîäèìîñòèâ äàííîì èñ÷èñëåíèè, à òàêæå ââîäÿòñÿ ïîíÿòèÿ ïîäòèïà è âõîæäåíèÿïîäòèïà â òèï.
 ðàçäåëå1.2îïðåäåëÿåòñÿ èñ÷èñëåíèå Ëàìáåêà L∗ , äî-ïóñêàþùåå ïóñòûå àíòåöåäåíòû. Âðàçäåëå 1.3ââîäèòñÿ ïîíÿòèå ôîð-ìàëüíîãî ÿçûêà è îïðåäåëÿþòñÿ îñíîâíûå îïåðàöèè íàä ôîðìàëüíûìèÿçûêàìè. Âðàçäåëå 1.4îïðåäåëÿþòñÿ ÿçûêîâûå ìîäåëè äëÿ èñ÷èñëå-íèÿ Ëàìáåêà.Ãëàâà 2ïîñâÿùåíà äîêàçàòåëüñòâó âåðõíåé îöåíêè íà äëèíó ñîâ-ìåùàþùåãî òèïà â èñ÷èñëåíèè Ëàìáåêà L. Âðàçäåëå 2.1ââîäèòñÿ îò-íîøåíèå ñîâìåñòèìîñòè â èñ÷èñëåíèè Ëàìáåêà, îïðåäåëÿåòñÿ ïîíÿòèåñîâìåùàþùåãî òèïà è ïðèâîäèòñÿ êðèòåðèé ñîâìåñòèìîñòè â èñ÷èñëåíèè Ëàìáåêà. Âðàçäåëå 2.2ìåùàþùåãî òèïà. Ðàçäåëîïèñûâàåòñÿ îáùàÿ ñõåìà ïîñòðîåíèÿ ñîâ-ðàçäåë 2.3ñîäåðæèò àëãîðèòì ïîñòðîåíèÿñîâìåùàþùåãî òèïà è äîêàçàòåëüñòâî òîãî, ÷òî äëèíà ïîñòðîåííîãî òèïàíå ïðåâîñõîäèò íåêîòîðîãî êâàäðàòè÷íîãî ïîëèíîìà îò äëèí èñõîäíûõòèïîâ.Ãëàâà 3ïîñâÿùåíà äîêàçàòåëüñòâó êâàäðàòè÷íîé íèæíåé îöåí-êè íà äëèíó ñîâìåùàþùåãî òèïà â èñ÷èñëåíèè Ëàìáåêà.
 ðàçäåëå3.1ôîðìóëèðóåòñÿ èñ÷èñëåíèå äëÿ ìóëüòèïëèêàòèâíîé öèêëè÷åñêîé ëèíåéíîé ëîãèêè MCLL, ÿâëÿþùåéñÿ êîíñåðâàòèâíûì ðàñøèðåíèåì èñ÷èñëåíèÿ Ëàìáåêà. Âðàçäåëå 3.2ââîäèòñÿ îòíîøåíèå ñîâìåñòèìîñòè äëÿäàííîãî èñ÷èñëåíèÿ. Òàêæå â äàííîì ðàçäåëå äîêàçûâàåòñÿ, ÷òî íèæíÿÿîöåíêà íà äëèíó ñîâìåùàþùåé ôîðìóëû â ìóëüòèïëèêàòèâíîé öèêëè÷åñêîé ëèíåéíîé ëîãèêå òàêæå ÿâëÿåòñÿ íèæíåé îöåíêîé íà äëèíó ñîâìåùàþùåãî òèïà â èñ÷èñëåíèè Ëàìáåêà.
Âðàçäåëå 3.3ââîäèòñÿ ïîíÿ-òèå óïðîù¼ííîé ñåòè äîêàçàòåëüñòâà äëÿ èñ÷èñëåíèÿ MCLL, íà îñíîâå11êîòîðîãî âðàçäåëå 3.4ïðèâîäÿòñÿ íèæíèå îöåíêè íà ÷èñëî âõîæäå-íèé ïåðåìåííûõ â ñîâìåùàþùèå ôîðìóëû. Ñ ïîìîùüþ äàííûõ îöåíîêâðàçäåëå 3.5äîêàçûâàåòñÿ êâàäðàòè÷íàÿ îöåíêà íà äëèíó ñîâìåùàþ-ùåãî òèïà â èñ÷èñëåíèÿõ L∗ è L.Âíèÿ. Âãëàâå 4ââîäèòñÿ èñ÷èñëåíèå Ëàìáåêà ñ îïåðàöèÿìè çàìåùå-ðàçäåëå 4.1îïðåäåëÿåòñÿ èñ÷èñëåíèå Ëàìáåêà ñ åäèíèöåé L1 ,ÿâëÿþùååñÿ êîíñåðâàòèâíûì ðàñøèðåíèåì èñ÷èñëåíèÿ L∗ , ïðè ýòîì äëÿèñ÷èñëåíèÿ L1 ïðèâîäèòñÿ íåñåêâåíöèàëüíàÿ àêñèîìàòèêà. Â4.2ðàçäåëåîïðåäåëÿþòñÿ ðàçðûâíûå îïåðàöèè íàä ôîðìàëüíûìè ÿçûêàìè.
Âðàçäåëå 4.3ïîñâÿù¼í íåñåêâåíöèàëüíîìó èñ÷èñëåíèþ Ëàìáåêà ñ îïå-ðàöèÿìè çàìåùåíèÿ, êîòîðîå îáîçíà÷àåòñÿ ÷åðåç HDL è ÿâëÿåòñÿ êîíñåðâàòèâíûì ðàñøèðåíèåì èñ÷èñëåíèÿ L1 , à òàêæå åãî ôðàãìåíòàì HDLk .Ðàçäåë 4.4ïîñâÿù¼í ÿçûêîâûì ìîäåëÿì èñ÷èñëåíèÿ Ëàìáåêà ñ îïåðà-öèÿìè çàìåùåíèÿ.Ãëàâà 5ïîñâÿùåíà äîêàçàòåëüñòâó êðèòåðèÿ ñîâìåñòèìîñòè â èñ-÷èñëåíèè HDL, à òàêæå â åãî ôðàãìåíòå HDLk , íàçûâàåìîì èñ÷èñëåíèåìËàìáåêà ñ k îïåðàöèÿìè çàìåùåíèÿ.  ðàçäåëå 5.1 ââîäèòñÿ îòíîøåíèåñîâìåñòèìîñòè äëÿ èñ÷èñëåíèé HDL è HDLk , à òàêæå ïîíÿòèå èíòåðïðåòàöèè â ñâîáîäíîé àáåëåâîé ãðóïïå äëÿ òèïîâ äàííûõ èñ÷èñëåíèé. Âðàçäåëå 5.2äîêàçûâàåòñÿ, ÷òî ðàâåíñòâî èíòåðïðåòàöèé â ñâîáîäíîéàáåëåâîé ãðóïïå ÿâëÿåòñÿ êðèòåðèåì ñîâìåñòèìîñòè òèïîâ â èñ÷èñëåíèè Ëàìáåêà c k îïåðàöèÿìè çàìåùåíèÿ, à òàêæå â ïîëíîì èñ÷èñëåíèèËàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ.Âãëàâå 6äîêàçûâàåòñÿ, ÷òî ìíîæåñòâî ÿçûêîâ, ðàñïîçíàâàåìûõãðàììàòèêàìè, îñíîâàííûìè íà ñåêâåíöèàëüíîì èñ÷èñëåíèè Ëàìáåêà ñîïåðàöèÿìè çàìåùåíèÿ DL, çàìêíóòî îòíîñèòåëüíî ïåðåñå÷åíèÿ ñ àâòîìàòíûìè ÿçûêàìè, íå ñîäåðæàùèìè ïóñòîãî ñëîâà.
Âðàçäåëå 6.1ââîäèòñÿ ñåêâåíöèàëüíûé âàðèàíò DL èñ÷èñëåíèÿ Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ, ýêâèâàëåíòíûé íåñåêâåíöèàëüíîìó èñ÷èñëåíèþ HDL. Âðàçäåëå 6.2ïðèâîäèòñÿ ïîíÿòèå ãðàììàòèêè Ëàìáåêà, à òàêæå ãðàììà-12òèêè, îñíîâàííîé íà èñ÷èñëåíèè DL.  ðàçäåëåàâòîìàòíûõ ÿçûêîâ.Ðàçäåë 6.46.3îïðåäåëÿåòñÿ êëàñññîäåðæèò àëãîðèòì ïîñòðîåíèÿ ãðàì-ìàòèêè äëÿ ïåðåñå÷åíèÿ ÿçûêà, çàäàííîãî ãðàììàòèêîé, îñíîâàííîé íàèñ÷èñëåíèè DL, è àâòîìàòíîãî ÿçûêà áåç ïóñòîãî ñëîâà, à â ðàçäåëå6.5äîêàçûâàåòñÿ êîððåêòíîñòü äàííîãî àëãîðèòìà.ÁëàãîäàðíîñòèÀâòîð áëàãîäàðèò ñâîåãî íàó÷íîãî ðóêîâîäèòåëÿ ïðîôåññîðàÌ. Ð.
Ïåíòóñà çà âñåñòîðîííþþ ïîääåðæêó è ïîñòîÿííîå âíèìàíèå ê ðàáîòå, ê.ô.-ì.í. C. Ë. Êóçíåöîâà çà ïëîäîòâîðíûå îáñóæäåíèÿ, à òàêæåâåñü êîëëåêòèâ êàôåäðû ìàòåìàòè÷åñêîé ëîãèêè è òåîðèè àëãîðèòìîâçà òâîð÷åñêóþ àòìîñôåðó, ñïîñîáñòâóþùóþ ðàáîòå.13Ãëàâà 1Èñ÷èñëåíèå Ëàìáåêà è ïîðîæäàþùèåãðàììàòèêè1.1Èñ÷èñëåíèå ËàìáåêàLÎïðåäåëèì èñ÷èñëåíèå Ëàìáåêà L, âïåðâûå ââåä¼ííîå â ðàáîòå [18].Ïóñòü çàôèêñèðîâàíî ñ÷¼òíîå ìíîæåñòâî Pr, íàçûâàåìîå ìíîæåñòâîìïðèìèòèâíûõ òèïîâ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
