Об отношении совместимости в исчислении Ламбека и в его варианте с операциями замещения

ÌÎÑÊÎÂÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒèìåíè Ì. Â. ËÎÌÎÍÎÑÎÂÀÍà ïðàâàõ ðóêîïèñèÑîðîêèí Àëåêñåé Àíäðååâè÷Îá îòíîøåíèè ñîâìåñòèìîñòè â èñ÷èñëåíèè Ëàìáåêàè â åãî âàðèàíòå ñ îïåðàöèÿìè çàìåùåíèÿÑïåöèàëüíîñòü 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], ãäå êîíòåêñòíî-ñâîáîäíûå ãðàììàòèêè ðàñøèðÿþòñÿçà ñ÷¼ò èñïîëüçîâàíèÿ ïåðåñå÷åíèÿ è äðóãèõ áóëåâûõ îïåðàöèé â ïðàâèëàõ ãðàììàòèêè.Ïîñêîëüêó ãðàììàòèêè Ëàìáåêà ïîðîæäàþò òîò æå êëàññ ÿçûêîâ, ÷òî è êîíòåêñòíî-ñâîáîäíûå ãðàììàòèêè, ðàññìàòðèâàëèñü ðàçëè÷íûå âàðèàíòû èõ ìîäèôèêàöèè.