๐Ÿ”™ Back to Top

Sat Jun 27 20:31:12 JST 2015

ใ“ใ“ใพใง่€ƒใˆใŸใ“ใจใฎใพใจใ‚

kMMGใฎใ‚ขใƒซใ‚ดใƒชใ‚บใƒ ใซใ€ \(L^{\leq \ell}(p)\) ใ‚’ใƒ’ใƒฅใƒผใƒชใ‚นใƒ†ใ‚ฃใƒƒใ‚ฏ้–ขๆ•ฐใจใ—ใฆๅฐŽๅ…ฅใ™ใ‚‹. ใ‚ใ‚‹ใ„ใฏ ๆœ€็ต‚็š„ใซๅพ—ใ‚‰ใ‚Œใ‚‹ \(P\) ใซๅฏพใ—ใฆ \(L^{\leq \ell}(P)\) ใ‚’ๆœ€ๅฐๅŒ–ใ™ใ‚‹ใŸใ‚ใฎ่ฒชๆฌฒๆณ•ใ‚‚่€ƒใˆใ‚‰ใ‚Œใ‚‹.

\(L^{\leq \ell}(P)\) ใ‚’็›ดๆŽฅๆฑ‚ใ‚ใ‚‹ใ‚ˆใ‚Šๅ…ˆใซ \(L^{\leq \ell}(p)\) ใ‚’ๆฑ‚ใ‚ใ‚‹ใ“ใจใ‚’่€ƒใˆใŸ. ใ•ใ‚‰ใซ \(L^{= \ell}(p)\) ใ‚’่จˆ็ฎ—ใ™ใ‚‹ใ“ใจใพใงใซ้‚„ๅ…ƒใ™ใ‚‹.

ใƒ‘ใ‚ฟใƒผใƒณ \(p\) ใซๅฏพใ—ใฆใ€ ่‡ชๆ˜Žใซใ€ ่จ€่ชž \(L(p)\) ใ‚’ๅ—็†ใ™ใ‚‹้žๆฑบๅฎšๆ€งๆœ‰้™ใ‚ชใƒผใƒˆใƒžใƒˆใƒณ (NFA) ใฏๆง‹ๆˆใงใใ‚‹. ใ“ใฎNFAใฎ็Šถๆ…‹ๆ•ฐใฏใ€ใƒ‘ใ‚ฟใƒผใƒณ้•ท \(|p|\) ใฎไบŒๅ€ใงๆŠ‘ใˆใ‚‰ใ‚Œใ‚‹. ๅŽณๅฏ†ใซ่จ€ใˆใฐใ€\(p\) ไธญใฎ \(\diamond\) ใŒ2ใคใฎ็Šถๆ…‹ใซๅค‰ๆ›ใ•ใ‚Œใฆใ€ ใใฎไป–ใฎ่ฆ็ด ใฏใกใ‚‡ใ†ใฉ1ใคใฎ็Šถๆ…‹ใซๅค‰ๆ›ใ•ใ‚Œใ‚‹. (่ชคใ‚Š. ๅŽณๅฏ†ใซใ€็Šถๆ…‹ๆ•ฐใฏใ€€\(1 + |p|\) ใ . ไธ€ใคใฎ็Šถๆ…‹ใ‹ใ‚‰ใชใ‚‹NFAใซใคใ„ใฆใ€ๅ„่ฆ็ด ใฏใกใ‚‡ใ†ใฉไธ€ใคใฎ็Šถๆ…‹ใ‚’่ฟฝๅŠ ใ™ใ‚‹ใ“ใจใ—ใ‹ใ—ใชใ„.) ๆ•™็ง‘ๆ›ธ็š„ใซใ€NFAใ‹ใ‚‰ๆฑบๅฎšๆ€งๆœ‰้™ใ‚ชใƒผใƒˆใƒžใƒˆใƒณ (DFA) ใ‚‚ใพใŸใ€ๆง‹ๆˆใงใใ‚‹. ใ—ใ‹ใ—ใชใŒใ‚‰ใ€ไธ€่ˆฌ็š„ใซใฏใ€ใ“ใฎDFAใฎ็Šถๆ…‹ๆ•ฐใฏใ€NFAใฎ็Šถๆ…‹ๆ•ฐใฎๆŒ‡ๆ•ฐใ‚’ๆœ€ๅคงใงๆŒใกใ†ใ‚‹.

็„กๆ›–ๆ˜งๆœ‰้™ใ‚ชใƒผใƒˆใƒžใƒˆใƒณ (UFA) ใจใฏใ€ๆฌกใฎ2ใคใ‚’ๆบ€ใŸใ™ๆœ‰้™ใ‚ชใƒผใƒˆใƒžใƒˆใƒณใงใ‚ใ‚‹.

  1. ไปปๆ„ใฎ็Šถๆ…‹ใ€็Šถๆ…‹ใ€่ชž \((p, q, w)\) ใซใคใ„ใฆใ€UFAใฎไธŠใงใ€\(p \rightarrow^w q\) ใจใ„ใ†ใƒ‘ใ‚นใฏ้ซ˜ใ€…ไธ€ใคใ ใ‘ๅญ˜ๅœจใ™ใ‚‹.
  2. UFAใŒๅ—็†ใ™ใ‚‹่ชž \(w\) ใซใคใ„ใฆใ€\(p \rightarrow^w q\) ใจใ„ใ†ใƒ‘ใ‚นใ‚’ไฝœใ‚‹ๅˆๆœŸ็Šถๆ…‹ \(p\) ใจ็ต‚ไบ†็Šถๆ…‹ \(q\) ใฎ็ต„ใฏไธ€ๆ„ใงใ‚ใ‚‹ใ“ใจ.

ๆ˜Žใ‚‰ใ‹ใซใ€ไธ€่ˆฌใซNFAใฏUFAใจใฏ้™ใ‚‰ใชใใ€ใพใŸใ€ไธ€่ˆฌใซDFAใฏUFAใงใ‚ใ‚‹.

ใ•ใฆใ€UFAใฎไธŠใงใฏใ€ใใ‚ŒใŒๅ—็†ใ™ใ‚‹่จ€่ชž \(L\) ใซๅฏพใ—ใฆ \(\# L^{= \ell}\) ใฏๆฌกใฎใ‚ˆใ†ใซใ—ใฆ่จˆ็ฎ—ใงใใ‚‹.

UFAใฎ้šฃๆŽฅ่กŒๅˆ—ใ‚’ๆฌกใฎใ‚ˆใ†ใซๅฎš็พฉใ™ใ‚‹.

\((M)_{pq} =\) \(p \rightarrow^a q\) ใจใ„ใ†้ท็งปใ‚’ใชใ™ใ‚ขใƒซใƒ•ใ‚กใƒ™ใƒƒใƒˆ \(a\) ใฎๆ•ฐ

ใ“ใฎ่กŒๅˆ—ใ‚’ \(k\)ไน—ใ—ใฆๅพ—ใ‚‰ใ‚Œใ‚‹่กŒๅˆ— \(M^k\) ใฎ \(pq\) ๆˆๅˆ†ใฏใ€\(p \rightarrow q\) ใจใ„ใ†ใƒ‘ใ‚นใง้•ทใ•ใŒ \(k\) ใฎ่ชžใฎๆ•ฐใซ็›ธๅฝ“ใ™ใ‚‹.

UFAใฎ็Šถๆ…‹ๆ•ฐใ‚’ \(m\) ใจใ™ใ‚‹ใจใ€\(M\) ใฏ \(m \times m\) ่กŒๅˆ—ใงใ‚ใฃใฆใ€ ใใฎ \(k\) ไน—ใฏ่กŒๅˆ—ไน—็ฎ—ใซใคใ„ใฆใฏ็ด ๆœดใซ่จˆ็ฎ—ใ™ใ‚‹ใ“ใจใง \(O(m^3 \log k)\) ใ‹ใ‹ใ‚‹.

ใจใ„ใ†ใ‚ใ‘ใงใ€

ใ€Œใƒ‘ใ‚ฟใƒผใƒณ \(p\)ใ€ โ†’ ใ€Œ\(L(p)\) ใ‚’ๅ—็†ใ™ใ‚‹NFAใ€ โ†’ ใ€ŒๅŒ็ญ‰ใชDFAใ€ โ†’ ใ€Œ้šฃๆŽฅ่กŒๅˆ—ใ€

ใ“ใ‚Œใงใ€่จˆ็ฎ—ใŒใงใใ‚‹.

ๆœ€็ต‚็š„ใซๆฌฒใ—ใ„ใฎใฏใ€\(\#L^{\leq \ell}\) ใงใ‚ใฃใฆใ€ ใ“ใ‚Œใ‚’ \(\#L^{= 1} + \#L^{= 2} + \cdots \#L^{= \ell}\) ใจ่จˆ็ฎ—ใ™ใ‚‹ไบˆๅฎšใชใฎใงใ€ ๅ…จไฝ“ใจใ—ใฆ \(O(m^3 \ell)\) ใจใ„ใ†ใ“ใจใซใชใ‚‹.

่ฟฝ่จ˜ (Tue Jun 30 20:31:34 JST 2015)

็›ดๆŽฅ \(M^k\) ใ‚’ๆฑ‚ใ‚ใ‚‹ใ‚“ใ˜ใ‚ƒใชใใฆใ€ ๅˆๆœŸใƒ™ใ‚ฏใƒˆใƒซ: \(V = [1, 0 .. 0]\) (ๅˆๆœŸ็Šถๆ…‹ใ ใ‘็ซ‹ใฃใฆใ‚‹bitๅˆ—) ใ‚’็”จใ„ใฆ
\(M^k V\) ใŒใ€ๅˆๆœŸ็Šถๆ…‹ไป˜ใใฎใ€ๆœ€็ต‚็Šถๆ…‹ใชใ‚ใ‘. ใ“ใ‚Œใฏใ€\(k\) ๅ›žใ€่กŒๅˆ—ใจใƒ™ใ‚ฏใƒˆใƒซใฎๆŽ›ใ‘็ฎ—ใ‚’ใ™ใ‚Œใฐใ„ใ„ใ‚“ใ ใ‘ใฉใ€ ใ“ใ‚Œใฃใฆใ€ไธ€ๅ›žใฎๆŽ›ใ‘็ฎ—ใŒ \(O(m^2)\) ใงใงใใ‚‹. ใจใ„ใ†ใ‚ใ‘ใงใ€ๅ…จไฝ“ใจใ—ใฆใฏใ€ \(O(m^2 \ell)\) ใจใชใฃใฆใ‚ชใƒผใƒ€ใƒผใŒ่ฝใกใ‚‹

ใกใ‚ƒใ‚“ใจๆŽˆๆฅญใ‚’่žใ„ใฆใฆใ‚ˆใ‹ใฃใŸ

\(\ell\) ใฏใ›ใ„ใœใ„30็จ‹ๅบฆใฎๅคงใใ•ใฎใคใ‚‚ใ‚Šใงใ‚ใ‚‹. \(|p|\) ใ‚‚ใ€ใใ‚ŒใจๅŒ็จ‹ๅบฆใงใ‚ใ‚‹. ใงใฏใ•ใฆใ€\(m\) (UFAใซใŠใ‘ใ‚‹็Šถๆ…‹ๆ•ฐ) ใฏใ€\(2|p|\) ใฎๆŒ‡ๆ•ฐใ‚ใ‚Šใใ†.

ไบˆๆƒณ

ใƒ‘ใ‚ฟใƒผใƒณ่จ€่ชžใ‚’ๅ—็†ใ™ใ‚‹DFAใฎ็Šถๆ…‹ๆ•ฐใฏใ€ (ๅˆฅใซใใ‚ŒใŒไธŠๆ‰‹ใชๆง‹็ฏ‰ๆ–นๆณ•ใงใชใใฆใ‚‚) \(|p|\) ใฎๅฎšๆ•ฐๅ€็จ‹ๅบฆ.

ใ“ใ‚ŒใฏๅฎŒๅ…จใซใ€ใ„ใใคใ‹ใ‚’ใ€ๆ‰‹ใงๅฎŸ้š›ใซไฝœใฃใฆใฟใฆๅพ—ใ‚‰ใ‚ŒใŸ็ตŒ้จ“ใงใ‚ใ‚‹. ใจใ„ใฃใฆใ‚‚ใ€ๆœฌๅฝ“ใซ่ค‡้›‘ใ™ใŽใ‚‹ใƒ‘ใ‚ฟใƒผใƒณใซใคใ„ใฆใใ‚“ใชใ‚„ใฃใŸใ‚ใ‘ใงใฏใชใ„. ๅฎŸ้š›ใซDFAใ‚’ๆง‹็ฏ‰ใ—ใฆใฟใ›ใ‚‹ใƒ—ใƒญใ‚ฐใƒฉใƒ ใ‚’ใ•ใฃใ•ใจๆ›ธใ„ใฆใ€ ใใฎ็Šถๆ…‹ๆ•ฐใŒใฉใ†ๅข—ใˆใ‚‹ใ‹ใ‚’่ฆ‹ใฆใฟใ‚ˆใ†ใจๆ€ใ†.