Âê̾ | ¥Ó¥ë¥Ç¥£¥ó¥°¥Ñ¥º¥ë¤Î·×»»Ê£»¨¤µ |
Ãø¼Ô | *¾¾°æ ͦÂÀ, ´äËÜ Ãè¤ (¹ÅçÂç³ØÂç³Ø±¡¹©³Ø¸¦µæ²Ê¾ðÊ󹩳ØÀ칶) |
¥¡¼¥ï¡¼¥É | ¥Ó¥ë¥Ç¥£¥ó¥°¥Ñ¥º¥ë, ¥Ú¥ó¥·¥ë¥Ñ¥º¥ë, NP´°Á´ |
¥¢¥Ö¥¹¥È¥é¥¯¥È | ¥Ó¥ë¥Ç¥£¥ó¥°¥Ñ¥º¥ë¤ÏÌð°õ¤ÎÊý¸þ¤«¤é¿ô»ú¤Î¿ô¤À¤±¥Ó¥ë¤¬¸«¤¨¤ë¤è¤¦¤Ë¹â¤µ¤Î°ã¤¦¥Ó¥ë¤òʤ٤ë¥Ñ¥º¥ë¤Ç¤¢¤ë. ¹â¤¤¥Ó¥ë¤¬¼êÁ°¤Ë¤¯¤ë¤ÈÄ㤤¥Ó¥ë¤Ï¸«¤¨¤Ê¤¯¤Ê¤ë.N*N¥µ¥¤¥º¤ÎÈ×Ì̤ǰìÈÖÂ礤¤¿ô»ú¡Ê°ìÈֹ⤤¥Ó¥ë¡Ë¤ÏN¤Ç¤¢¤ë¡£¹Ô¤ÈÎó¤Ë¤Ï¥Þ¥¹¤Î¿ô¤À¤±°ã¤¦¹â¤µ¤Î¥Ó¥ë¤¬Â¸ºß¤¹¤ë¤Î¤Ç¡¢¹Ô¤ÈÎó¤Ç³Æ¿ô»ú¤Ï¤½¤ì¤¾¤ì°ìÅÙ¤º¤Ä»È¤ï¤ì¤ë. °Ê¾å¤Î¥ë¡¼¥ë¤òÍѤ¤¤Æ,Í¿¤¨¤é¤ì¤¿ÌäÂ꤫¤é²ò¤òƳ¤½Ð¤¹¤³¤È¤¬¤³¤Î¥²¡¼¥à¤ÎÌÜŪ¤Ç¤¢¤ë. ËܹƤǤϥӥë¥Ç¥£¥ó¥°¥Ñ¥º¥ë¤ÎNP´°Á´À¤ò¼¨¤¹. |
Âê̾ | GLL¹½Ê¸²òÀÏË¡»ë³Ð²½¥Ä¡¼¥ë¤Î³«È¯ |
Ãø¼Ô | *²Ï¸ý ͺÂç, °ËÆ£ ¶Ç (»³¸ýÂç³ØÂç³Ø±¡Íý¹©³Ø¸¦µæ²Ê) |
¥¡¼¥ï¡¼¥É | ¹½Ê¸²òÀÏ |
¥¢¥Ö¥¹¥È¥é¥¯¥È | GLL ¹½Ê¸²òÀÏË¡¤È¤Ï¡¤Ê¸Ë¡¤ÎÈó·èÄêŪ¤ÊÉôʬ¤ËÂФ·¤ÆÊ£¿ô¤Î¥×¥í¥»¥¹¤òÊÂÎóŪ¤ËºîÆ°¤µ¤»¡¤²òÀϤËɬÍפʥǡ¼¥¿¤ò°ì¤Ä¤Î¥°¥é¥Õ¾õ¥¹¥¿¥Ã¥¯¤Ë³ÊǼ¤·¤Ê¤¬¤é²òÀϤò¹Ô¤¦¹½Ê¸²òÀÏË¡¤Ç¤¢¤ë[1]¡¥Ëܸ¦µæ¤Ç¤Ï, ʸˡÁ«°Ü¿Þ, ¤½¤ÎʸˡÁ«°Ü¿Þ¾å¤Ë¤ª¤±¤ëGLL ¹½Ê¸²òÀÏË¡¤ÎÁ´Æ°ºîÅÀ¤ÎÁ«°Üµ°À׿ޡ¤¥°¥é¥Õ¾õ¥¹¥¿¥Ã¥¯¿Þ¤Î£³ÅÀ¤òÍѤ¤¤ÆGLL ¹½Ê¸²òÀÏË¡¤òľ´¶Åª¤Ë¤ï¤«¤ê¤ä¤¹¤¯¤¹¤ë¤¿¤á¤Î»ë³Ð²½¤òÄó°Æ¤·¡¤¤½¤ì¤é¤Î»ë³Ð²½¤µ¤ì¤¿GLL ¹½Ê¸²òÀÏ´ï¤ò¼ÂÁõ¤¹¤ë. |
Âê̾ | ¥³¥Ô¡¼²ó¿ô¸ÂÄê¥Ñ¥¿¡¼¥óʸ̮¼«Í³Ê¸Ë¡ |
Ãø¼Ô | *²ÏÌî ÍÛÂÀ, ¶ÌÌÚ ½¨Ëá (»³¸ýÂç³Ø¹©³ØÉô), °ËÆ£ ¶Ç (»³¸ýÂç³ØÂç³Ø±¡Íý¹©³Ø¸¦µæ²Ê) |
¥¡¼¥ï¡¼¥É | ʸ̮¼«Í³Ê¸Ë¡, ³ÈÄ¥Àµµ¬É½¸½ |
¥¢¥Ö¥¹¥È¥é¥¯¥È | ¥Ñ¥¿¡¼¥óɽ¸½(pattern expression) ¤Ïregex Åù¤Ë¤ª¤±¤ë¸åÊý »²¾È(back reference) ¤Îµ¡Ç½¤ò·Á¼°²½¤¹¤ë¤¿¤á¤ËƳÆþ¤µ¤ì¤¿ ³ÈÄ¥Àµµ¬É½¸½¤Ç¤¢¤ë[1, 2]¡¥¥Ñ¥¿¡¼¥óʸ̮¼«Í³Ê¸Ë¡(pattern context-free grammar) ¤Ï¥Ñ¥¿¡¼¥óɽ¸½¤Î¹Í¤¨Êý¤òʸ̮¼«Í³ ʸˡ¤ËÂФ·¤ÆƳÆþ¤·¤¿¤â¤Î¤Ç¤¢¤ë[3]¡¥ Ëܸ¦µæ¤Ç¤Ï¡¤¤Þ¤ºÀþ·Áʸˡ¤ÈÀµµ¬Ê¸Ë¡¤Ë¥³¥Ô¡¼µ¡Ç½¤ò»ý ¤¿¤»¤¿¾ì¹ç¤Ë¤Ï¡¤¸À¸ìÀ¸À®Ç½ÎϤϸþ¾å¤·¤Ê¤¤¤³¤È¤ò¼¨¤¹¡¥ ¤Þ¤¿¡¤¥Ñ¥¿¡¼¥óɽ¸½¤ò¤½¤ì¤ÈÅù²Á¤Ê¥Ñ¥¿¡¼¥óCFG ¤ËÊÑ´¹¤¹ ¤ë¼êË¡¤ò¼¨¤¹¡¥ºÇ¸å¤Ë¡¤¥Ñ¥¿¡¼¥óɽ¸½¸À¸ì¤ËÂФ¹¤ëÈ¿ÉüÊä Âê¤ò¾Ò²ð¤·¡¤¤½¤ÎŬ±þÎã¤òµó¤²¤¿¸å¤Ë¡¤¥³¥Ô¡¼²ó¿ô¤¬1 ²ó ¤Ç¤¢¤ë¤è¤¦¤Ê¥Ñ¥¿¡¼¥óʸ̮¼«Í³Ê¸Ë¡¤ËÂФ¹¤ëÈ¿ÉüÊäÂê¤ò¾Ú ÌÀ¤¹¤ë¡¥ |
Âê̾ | 3¼¡¸µLarger than Life ¥»¥ë¥ª¡¼¥È¥Þ¥È¥ó¤Ë¤ª¤±¤ë¥Ð¥°¤Îõº÷ |
Ãø¼Ô | *µ×ÊÝÅÄ ÃÒÂç (¹ÅçÂç³ØÂç³Ø±¡¹©³Ø¸¦µæ²Ê¾ðÊ󹩳ØÀ칶), º£°æ ¹îĪ (¹ÅçÂç³ØÂç³Ø±¡¹©³Ø¸¦µæ±¡) |
¥¡¼¥ï¡¼¥É | ¥»¥ë¥ª¡¼¥È¥Þ¥È¥ó, ¥é¥¤¥Õ¥²¡¼¥à |
¥¢¥Ö¥¹¥È¥é¥¯¥È | ¥»¥ë¥ª¡¼¥È¥Þ¥È¥ó¤È¤Ï¡¤¶õ´Ö¾å¤Ë°ìÍͤËʤó¤À¥»¥ë¤È´Êñ¤Êµ¬Â§¤Ë¤è¤ë¡¢Î¥»¶Åª·×»»¥â¥Ç¥ë¤Ç¤¢¤ë¡£2¼¡¸µ¥»¥ë¥ª¡¼¥È¥Þ¥È¥ó¤Î¥ë¡¼¥ë¤Î°ì¤Ä¤Ç¤¢¤ëLarger than Life(LtL)¤Ï5¤Ä¤Î¥Ñ¥é¥á¡¼¥¿¤Çɽ¤µ¤ì¡¢¤½¤ÎÃͤˤè¤êÈó¾ï¤Ë¿Íͤʥѥ¿¡¼¥ó¤ò»ý¤Ä¡£LtL¤Ë¤Ï¥Ð¥°¤È¸Æ¤Ð¤ì¤ëÆÃÊ̤ʰÜÆ°¥Ñ¥¿¡¼¥ó¤¬Â¸ºß¤¹¤ë¡£Ëܸ¦µæ¤Ï3¼¡¸µ¤Ë³ÈÄ¥¤·¤¿LtL¤Ë¤ª¤¤¤Æ¡¢¥Ð¥°¤¬À¸À®¤µ¤ì¤ë¾ò·ï¤òËþ¤¿¤¹¥Ñ¥é¥á¡¼¥¿¤ÎÈϰϤòõº÷¤·¡¢¿·¤¿¤Ê¥Ð¥°¤òȯ¸«¤·¤¿¡£ |
Âê̾ | Á´¾Î¾õÂ֤ΤߤÎ1Êý¸þ¸òÂåÀ¥Þ¥ë¥Á¥×¥í¥»¥Ã¥µÍ¸Â¥ª¡¼¥È¥Þ¥È¥ó |
Ãø¼Ô | *µ×ËÜ ½ã¼ù (ÆÁ»³¹©¶È¹âÅùÀìÌç³Ø¹»¾ðÊóÅŻҹ©³ØÀ칶), µÁ±Ê ¾ï¹¨ (ÆÁ»³¹©¶È¹âÅùÀìÌç³Ø¹»¾ðÊóÅŻҹ©³Ø²Ê), ºäËÜ âÃ¿Í (µÜºêÂç³Ø¹©³ØÉô) |
¥¡¼¥ï¡¼¥É | ¥Þ¥ë¥Á¥×¥í¥»¥Ã¥µÍ¸Â¥ª¡¼¥È¥Þ¥È¥ó, ¸òÂåÀ·×»», 1Êý¸þ·×»», Á´¾Î¾õÂÖ |
¥¢¥Ö¥¹¥È¥é¥¯¥È | ¥Þ¥ë¥Á¥×¥í¥»¥Ã¥µÍ¸Â¥ª¡¼¥È¥Þ¥È¥ó(MPFA)¤Ï, Ê£¿ô¤Î͸¥ª¡¼¥È¥Þ¥È¥ó¤È¥¹¥¤¥Ã¥Á¥ó¥°´Ø¿ô¤Ë¤è¤ê¹½À®¤µ¤ì¤Æ¤ª¤ê, ºÇ¤âñ½ã¤ÊÊÂÎó·×»»¥â¥Ç¥ë¤Î1¤Ä¤È¹Í¤¨¤ë¤³¤È¤¬¤Ç¤¤ë.¤³¤ì¤Þ¤Ç¤ËMPFA¤Ë¤ª¤±¤ë·èÄêÀ¤ª¤è¤ÓÈó·èÄêÀ·×»»¤Ë¤Ä¤¤¤Æ¤Î¸¦µæ¤¬¤Ê¤µ¤ì¤Æ¤¤¤ë¤¬, ¸òÂåÀ·×»»¤Ë¤Ä¤¤¤Æ¤Ï¤Û¤È¤ó¤É¹Í»¡¤µ¤ì¤Æ¤¤¤Ê¤¤. Ëܸ¦µæ¤Ç¤ÏÁ´¾Î¾õÂÖ¤À¤±¤ËÀ©¸Â¤µ¤ì¤¿1Êý¸þ¸òÂåÀMPFA¤Î´ðËÜŪ¤ÊÀ¼Á¤Ë¤Ä¤¤¤Æ¹Í»¡¤·, ¡¥×¥í¥»¥Ã¥µ¿ô¤Ë´ð¤Å¤¯¼õÍýǽÎϤγ¬ÁØÀ¤¬Â¸ºß¤¹¤ë¤³¤È, ¢Á´¾Î¾õÂ֤ΤߤθòÂåÀ¤Ï·èÄêÀ¤è¤ê¤â¿¿¤Ë¼õÍýǽÎϤ¬¹â¤¤¤³¤È, £Èó·èÄêÀ¤ÈÁ´¾Î¾õÂ֤ΤߤθòÂåÀ¤Î¼õÍýǽÎϤÏÈæ³ÓÉÔǽ¤Ç¤¢¤ë¤³¤È¤ò¼¨¤·¤Æ¤¤¤ë. ¤Þ¤¿, ´ØÏ¢¤¹¤ë̤²ò·èÌäÂê¤òÄ󼨤·¤Æ¤¤¤ë. |