Об отношении совместимости в исчислении Ламбека и в его варианте с операциями замещения (1104173)
Текст из файла
ÌÎÑÊÎÂÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒèìåíè Ì. Â. ËÎÌÎÍÎÑÎÂÀÍà ïðàâàõ ðóêîïèñèÑîðîêèí Àëåêñåé Àíäðååâè÷Îá îòíîøåíèè ñîâìåñòèìîñòè â èñ÷èñëåíèè Ëàìáåêàè â åãî âàðèàíòå ñ îïåðàöèÿìè çàìåùåíèÿÑïåöèàëüíîñòü 01.01.06 ìàòåìàòè÷åñêàÿ ëîãèêà, àëãåáðàè òåîðèÿ ÷èñåëÄÈÑÑÅÐÒÀÖÈßíà ñîèñêàíèå ó÷¼íîé ñòåïåíè êàíäèäàòà ôèçèêî-ìàòåìàòè÷åñêèõ íàóêÍàó÷íûé ðóêîâîäèòåëü:ä.ô.-ì.í., ïðîôåññîð Ìàòè Ðåéíîâè÷ ÏåíòóñÌÎÑÊÂÀ 2014ÎãëàâëåíèåÂâåäåíèå124Èñ÷èñëåíèå Ëàìáåêà è ïîðîæäàþùèå ãðàììàòèêè1.1Èñ÷èñëåíèå Ëàìáåêà L . . . . .
. . . . . . . . . . . . . . . . 141.2Èñ÷èñëåíèå L∗1.3Ôîðìàëüíûå ÿçûêè è îïåðàöèè íàä íèìè . . . . . . . . . . 181.4Ìîäåëè èñ÷èñëåíèÿ Ëàìáåêà . . . . . . . . . . . . . . . . . 20. . . . . . . . . . . . . . . . . . . . . . . . . 18Âåðõíÿÿ îöåíêà äëèíû ñîâìåùàþùåãî òèïà â èñ÷èñëåíèèL3222.1Êðèòåðèé ñîâìåñòèìîñòè â èñ÷èñëåíèè Ëàìáåêà .
. . . . . 222.2Ñõåìà ïîñòðîåíèÿ ñîâìåùàþùåãî òèïà2.3Ïîñòðîåíèå ñîâìåùàþùåãî òèïà . . . . . . . . . . . . . . . 30. . . . . . . . . . . 25Íèæíÿÿ îöåíêà äëèíû ñîâìåùàþùåãî òèïà â èñ÷èñëåíèèL414403.1Ìóëüòèïëèêàòèâíàÿ öèêëè÷åñêàÿ ëèíåéíàÿ ëîãèêà . . . . . 403.2Îòíîøåíèå ñîâìåñòèìîñòè â èñ÷èñëåíèè MCLL . . . . . .
. 423.3Óïðîù¼ííûå ñåòè äîêàçàòåëüñòâà3.4Îöåíêè íà ÷èñëî âõîæäåíèé àòîìîâ â ñîâìåùàþùèé òèï . 473.5Äîêàçàòåëüñòâî íèæíåé îöåíêè . . . . . . . . . . . . . . . . 52. . . . . . . . . . . . . . 45Èñ÷èñëåíèå Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ574.1Èñ÷èñëåíèå Ëàìáåêà ñ åäèíèöåé . . . . . .
. . . . . . . . . 574.2Ðàçðûâíûå îïåðàöèè íàä ÿçûêàìè . . . . . . . . . . . . . . 58254.3Èñ÷èñëåíèå Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ . . . . . . . 594.4Ìîäåëè èñ÷èñëåíèÿ Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ. . 64Îòíîøåíèå ñîâìåñòèìîñòè â èñ÷èñëåíèè Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ5.166Îòíîøåíèå ñîâìåñòèìîñòè è èíòåðïðåòàöèÿ â ñâîáîäíîéàáåëåâîé ãðóïïå . . . . .
. . . . . . . . . . . . . . . . . . . . 665.26Äîêàçàòåëüñòâî êðèòåðèÿ ñîâìåñòèìîñòè . . . . . . . . . . 72Î ïåðåñå÷åíèè ÿçûêîâ, ïîðîæäàåìûõ ðàçðûâíûìè ãðàììàòèêàìè Ëàìáåêà, ñ àâòîìàòíûìè ÿçûêàìè846.1Ñåêâåíöèàëüíîå èñ÷èñëåíèå DL . . . . . . .
. . . . . . . . . 846.2Êàòåãîðèàëüíûå ãðàììàòèêè, îñíîâàííûå íà âàðèàíòàõèñ÷èñëåíèÿ Ëàìáåêà . . . . . . . . . . . . . . . . . . . . . . 916.3Êîíå÷íûå àâòîìàòû è çàäàâàåìûå èìè ÿçûêè . . . . . . . . 946.4Ïåðåñå÷åíèå ñ àâòîìàòíûìè ÿçûêàìè: îïèñàíèå êîíñòðóêöèè 956.5Äîêàçàòåëüñòâî êîððåêòíîñòè êîíñòðóêöèè . . . . . . . . .
98Ïðåäìåòíûé óêàçàòåëü108Ëèòåðàòóðà1163ÂâåäåíèåÎáùàÿ õàðàêòåðèñòèêà ðàáîòûÀêòóàëüíîñòü òåìûÄèññåðòàöèÿ ïîñâÿùåíà èññëåäîâàíèþ îòíîøåíèÿ ñîâìåñòèìîñòèâ ðàçëè÷íûõ âàðèàíòàõ èñ÷èñëåíèÿ Ëàìáåêà.  ðàáîòå ôîðìóëèðóþòñÿâåðõíÿÿ è íèæíÿÿ îöåíêà íà äëèíó ñîâìåùàþùåãî òèïà äëÿ èñ÷èñëåíèÿËàìáåêà L è äîêàçûâàåòñÿ êðèòåðèé ñîâìåñòèìîñòè òèïîâ äëÿ èñ÷èñëåíèÿ Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ.
Òàêæå â ðàáîòå èññëåäóåòñÿêëàññ ÿçûêîâ, ïîðîæäàåìûõ ãðàììàòèêàìè, îñíîâàííûìè íà èñ÷èñëåíèè Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ.Èñ÷èñëåíèå Ëàìáåêà L áûëî ââåäåíî È. Ëàìáåêîì â ðàáîòå [18]äëÿ ôîðìàëüíîãî îïèñàíèÿ ñèíòàêñèñà åñòåñòâåííûõ ÿçûêîâ.
Òèïû èñ÷èñëåíèÿ Ëàìáåêà ñòðîÿòñÿ èç ñ÷¼òíîãî ìíîæåñòâà ïðèìèòèâíûõ òèïîâñ ïîìîùüþ äâóìåñòíûõ ñâÿçîê óìíîæåíèÿ, à òàêæå ëåâîãî è ïðàâîãîäåëåíèÿ. Äâà òèïà A è B èñ÷èñëåíèÿ Ëàìáåêà íàçûâàþòñÿ ñîâìåñòèìûìè, åñëè ñóùåñòâóåò òàêîé òèï C , ÷òî îáå ñåêâåíöèè A → C è B → Cÿâëÿþòñÿ âûâîäèìûìè.  ýòîì ñëó÷àå òèï C íàçûâàåòñÿ ñîâìåùàþùèìäëÿ òèïîâ A è B . Îòíîøåíèå ñîâìåñòèìîñòè áûëî âïåðâûå ââåäåíî (ïîääðóãèì íàçâàíèåì) â ðàáîòå [18], ãäå áûëî äîêàçàíî, ÷òî îíî ÿâëÿåòñÿîòíîøåíèåì ýêâèâàëåíòíîñòè. ðàáîòå [27] áûë äîêàçàí êðèòåðèé ñîâìåñòèìîñòè òèïîâ â èñ÷èñëåíèè Ëàìáåêà è êîììóòàòèâíîì èñ÷èñëåíèè Ëàìáåêà, ñôîðìóëèðîâàííûé â òåðìèíàõ èíòåðïðåòàöèé òèïîâ èñ÷èñëåíèÿ Ëàìáåêà â ñâîáîäíîéãðóïïå, ïîðîæä¼ííîé ïðèìèòèâíûìè òèïàìè.
 ðàáîòàõ [11] è [20] áûëèïîëó÷åíû êðèòåðèè ñîâìåñòèìîñòè, ñîîòâåòñòâåííî, äëÿ íåàññîöèàòèâ4íîãî èñ÷èñëåíèÿ Ëàìáåêà NL è èñ÷èñëåíèÿ Ëàìáåêà-Ãðèøèíà LG. Ñëèíãâèñòè÷åñêîé òî÷êè çðåíèÿ ñîâìåñòèìîñòü òèïîâ îçíà÷àåò âîçìîæíîñòü ñîåäèíèòü ñîîòâåòñòâóþùèå èì ÿçûêîâûå âûðàæåíèÿ ñ ïîìîùüþñî÷èíèòåëüíîãî ñîþçà[33].  ðàáîòàõ [10] è [11] ðàññìàòðèâàëîñü ïðèìåíåíèå îòíîøåíèÿ ñîâìåñòèìîñòè äëÿ óíèôèêàöèè è àâòîìàòè÷åñêîãî ïîñòðîåíèÿ êàòåãîðèàëüíûõ ãðàììàòèê, îñíîâàííûõ íà èñ÷èñëåíèè Ëàìáåêà (òàêæå íàçûâàåìûõ ãðàììàòèêàìè Ëàìáåêà). Îäíàêî â çàäà÷àõ àâòîìàòè÷åñêîãî ïîñòðîåíèÿ ãðàììàòèê Ëàìáåêà îñíîâíóþ ðîëü èãðàåò íåñòîëüêî ôàêò ñóùåñòâîâàíèÿ ñîâìåùàþùåãî òèïà, ñêîëüêî àëãîðèòì åãîïîñòðîåíèÿ è îöåíêè íà åãî âîçìîæíóþ äëèíó. Òàêæå ïîñòðîåíèå ñîâìåùàþùåãî òèïà äëÿ çàäàííûõ ñîâìåñòèìûõ òèïîâ èñ÷èñëåíèÿ Ëàìáåêàÿâëÿåòñÿ îäíèì èç ýòàïîâ ïðåäëîæåííîãî â [37] àëãîðèòìà ïðèâåäåíèÿãðàììàòèêè Ëàìáåêà ê ýêâèâàëåíòíîé åé îäíîçíà÷íîé ãðàììàòèêå.Ìû äîêàæåì, ÷òî äëÿ ëþáûõ ñîâìåñòèìûõ òèïîâ èñ÷èñëåíèÿ Ëàìáåêà íàéä¼òñÿ ñîâìåùàþùèé òèï, ÷üÿ äëèíà îãðàíè÷åíà êâàäðàòè÷íûììíîãî÷ëåíîì îò äëèí èñõîäíûõ òèïîâ, è ïðåäëîæèì àëãîðèòì ïîñòðîåíèÿ ñîîòâåòñòâóþùåãî òèïà.
Êðîìå òîãî, ìû ïîêàæåì, ÷òî äàííàÿ êâàäðàòè÷íàÿ îöåíêà ÿâëÿåòñÿ íåóëó÷øàåìîé ñ òî÷íîñòüþ äî ïîñòîÿííîãîìíîæèòåëÿ: áóäåò ïðåäúÿâëåíî ñåìåéñòâî ïàð ñîâìåñòèìûõ òèïîâ, ñîäåðæàùåå ïàðû òèïîâ ñêîëü óãîäíî áîëüøîé äëèíû, òàêîå ÷òî äëÿ êàæäîé èç ïàð äëèíà ñîâìåùàþùåãî òèïà îãðàíè÷åíà ñíèçó íåêîòîðûì äðóãèì êâàäðàòè÷íûì ìíîãî÷ëåíîì. Òàêæå ìû èññëåäóåì îòíîøåíèå ñîâìåñòèìîñòè äëÿ èñ÷èñëåíèÿ HDL, ÿâëÿþùåãîñÿ íåñåêâåíöèàëüíûì âàðèàíòîì èñ÷èñëåíèÿ Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿ, ââåä¼ííîãî â[21]. Ìû ïîêàæåì, ÷òî äâà òèïà äàííîãî èñ÷èñëåíèÿ ÿâëÿþòñÿ ñîâìåñòèìûìè â òîì è òîëüêî òîì ñëó÷àå, êîãäà ñîâïàäàþò èõ èíòåðïðåòàöèèâ ñâîáîäíîé àáåëåâîé ãðóïïå, ïîðîæä¼ííîé ïðèìèòèâíûìè òèïàìè.Îñíîâíûì ïðèëîæåíèåì èñ÷èñëåíèÿ Ëàìáåêà ñëóæàò êàòåãîðèàëüíûå ãðàììàòèêè, îñíîâàííûå íà èñ÷èñëåíèè Ëàìáåêà.
Îíè àêòèâíî èñïîëüçóþòñÿ äëÿ ôîðìàëüíîãî îïèñàíèÿ è ñèíòàêñè÷åñêîãî ðàçáîðà5åñòåñòâåííûõ ÿçûêîâ. Òàêæå äëÿ äàííûõ öåëåé ïðèìåíÿþòñÿ ãðàììàòèêè, îñíîâàííûå íà âàðèàíòàõ èñ÷èñëåíèÿ Ëàìáåêà, òàêèõ êàê íåàññîöèàòèâíîå èñ÷èñëåíèå NL è èñ÷èñëåíèå Ëàìáåêà ñ îïåðàöèÿìè çàìåùåíèÿDL.Äëÿ ñèíòàêñè÷åñêîãî îïèñàíèÿ åñòåñòâåííûõ ÿçûêîâ òàêæå ïðèìåíÿþòñÿ ââåä¼ííûå Í. Õîìñêèì â [6] ïîðîæäàþùèå ãðàììàòèêè. Íàèáîëåå âàæíûì êëàññîì ïîðîæäàþùèõ ãðàììàòèê ÿâëÿþòñÿ êîíòåêñòíîñâîáîäíûå ãðàììàòèêè, àêòèâíî èñïîëüçóþùèåñÿ äëÿ çàäàíèÿ ñèíòàêñèñà ÿçûêîâ ïðîãðàììèðîâàíèÿ ([2]).  òî æå âðåìÿ äëÿ îïèñàíèÿ åñòåñòâåííûõ ÿçûêîâ ãðàììàòèêè Ëàìáåêà è äðóãèå âàðèàíòû êàòåãîðèàëüíûõ ãðàììàòèê ÿâëÿþòñÿ áîëåå ïðåäïî÷òèòåëüíûìè.  ÷àñòíîñòè,ãðàììàòèêè Ëàìáåêà îáëàäàþò ñâîéñòâîì ëåêñèêàëèçàöèè, ÷òî ïîçâîëÿåò õðàíèòü âñþ íåîáõîäèìóþ ñèíòàêñè÷åñêóþ èíôîðìàöèþ â ñëîâàðå,à òàêæå åñòåñòâåííûì îáðàçîì ñîâìåùàòü ñèíòàêñè÷åñêèé è ñåìàíòè÷åñêèé àíàëèç (ñì., íàïðèìåð, [22], [16]).
 öåëîì, ïðîöåññ âûâîäà â êàòåãîðèàëüíûõ ãðàììàòèêàõ áîëåå òî÷íî îòðàæàåò ñèíòàêñè÷åñêèå ÿâëåíèÿ åñòåñòâåííîãî ÿçûêà, ÷åì ñîîòâåòñòâóþùèé ïðîöåññ â ïîðîæäàþùèõãðàììàòèêàõ.Åñëè ðàññìàòðèâàòü ãðàììàòèêè Ëàìáåêà òîëüêî ñ òî÷êè çðåíèÿïîðîæäàåìûõ èìè ÿçûêîâ, òî, êàê äîêàçàíî Ì. Ð. Ïåíòóñîì â [35], âñÿêèé òàêîé ÿçûê ÿâëÿåòñÿ êîíòåêñòíî-ñâîáîäíûì. Èç äàííîãî ðåçóëüòàòà,à òàêæå îáðàòíîé òåîðåìû, ïîëó÷åííîé ðàíåå Í. Ãàéôìàíîì â [5], âûòåêàåò, ÷òî êëàññ ÿçûêîâ, ïîðîæäàåìûõ ãðàììàòèêàìè, îñíîâàííûìè íàèñ÷èñëåíèè L, ñîâïàäàåò ñ êëàññîì êîíòåêñòíî-ñâîáîäíûõ ÿçûêîâ áåç ïóñòîãî ñëîâà.Õîðîøî èçâåñòíî (ñì., íàïðèìåð, [16]), ÷òî êîíòåêñòíî-ñâîáîäíûõãðàììàòèê íåäîñòàòî÷íî äëÿ ïîëíîöåííîãî àíàëèçà åñòåñòâåííûõ ÿçûêîâ.
Íàïðèìåð, îíè íå ïîçâîëÿþò ðàññìàòðèâàòü òàê íàçûâàåìûå íåïðîåêòèâíûå çàâèñèìîñòè, à òàêæå íåïðèìåíèìû â ñëó÷àå ÿçûêîâ ñî ñâîáîäíûì ïîðÿäêîì ñëîâ, òàêèõ êàê ðóññêèé èëè ÿïîíñêèé. Äëÿ ðåøåíèÿ6äàííîé ïðîáëåìû áûëè ïðåäëîæåíû ðàçëè÷íûå ôîðìàëèçìû, ïîçâîëÿþùèå ìîäåëèðîâàòü ðàçðûâíûå ñèíòàêñè÷åñêèå ñòðóêòóðû, íî ïðè ýòîìñîõðàíÿþùèå òàêèå ïîëåçíûå ñâîéñòâà êîíòåêñòíî-ñâîáîäíûõ ãðàììàòèê, êàê ïîëèíîìèàëüíàÿ ñëîæíîñòü ðàçáîðà è íåçàâèñèìîñòü âûâîäàâ ãðàììàòèêå îò êîíòåêñòà.
Ñðåäè íàèáîëåå âàæíûõ òèïîâ ãðàììàòèêìîæíî íàçâàòü âåðøèííûå ãðàììàòèêè Ê. Ïîëëàðäà ([29]), ãðàììàòèêèïðèñîåäèíÿåìûõ äåðåâüåâ À. Éîñè è È. Øàáñà (tree-adjoining grammars,[13]), ìíîæåñòâåííûå êîíòåêñòíî-ñâîáîäíûå ãðàììàòèêè, ââåä¼ííûå âðàáîòå Õ. Ñåêè è äð. (multiple context-free grammars, [31]), à òàêæå âëîæåííûå ìíîæåñòâåííûå êîíòåêñòíî-ñâîáîäíûå ãðàììàòèêè (well-nestedmultiple context-free grammars, [15]). Îòìåòèì, ÷òî äëÿ âñåõ óïîìÿíóòûõ ôîðìàëèçìîâ óâåëè÷åíèå ìíîæåñòâà ïîðîæäàåìûõ ÿçûêîâ â ñðàâíåíèè ñ êîíòåêñòíî-ñâîáîäíûìè ãðàììàòèêàìè äîñòèãàåòñÿ çà ñ÷¼ò òîãî, ÷òî âûâîäèìûìè îáúåêòàìè ÿâëÿþòñÿ íå ñëîâà, êàê â êîíòåêñòíîñâîáîäíûõ ãðàììàòèêàõ, à êîðòåæè ñëîâ èëè äåðåâüÿ. Òàêæå ñëåäóåòîòìåòèòü êîíúþíêòèâíûå è áóëåâû ãðàììàòèêè À. Îõîòèíà, ðàññìàòðèâàåìûå â [25] è [26], ãäå êîíòåêñòíî-ñâîáîäíûå ãðàììàòèêè ðàñøèðÿþòñÿçà ñ÷¼ò èñïîëüçîâàíèÿ ïåðåñå÷åíèÿ è äðóãèõ áóëåâûõ îïåðàöèé â ïðàâèëàõ ãðàììàòèêè.Ïîñêîëüêó ãðàììàòèêè Ëàìáåêà ïîðîæäàþò òîò æå êëàññ ÿçûêîâ, ÷òî è êîíòåêñòíî-ñâîáîäíûå ãðàììàòèêè, ðàññìàòðèâàëèñü ðàçëè÷íûå âàðèàíòû èõ ìîäèôèêàöèè.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
