著者
新屋 良磨
出版者
日本ソフトウェア科学会
雑誌
コンピュータ ソフトウェア (ISSN:02896540)
巻号頁・発行日
vol.34, no.3, pp.3_3-3_35, 2017-07-25 (Released:2017-09-25)

オートマトンは最も単純な計算のモデルである.その単純さゆえに初学者にとっても理解しやすく,情報系の学部においては「計算理論」や「形式言語理論」などの講義はまずオートマトンから教え始めることが標準となっている.一方,その単純さゆえに理論的な深みやさらなる研究の余地がないと誤解されることもしばしばあり,また,講義や解説書においても応用的な需要からかより強力な計算モデルに重きが置かれることも多い.本サーベイではオートマトン理論の基礎から始め,三話構成でオートマトン・形式言語理論の様々な定理を解説していく.解説する定理の中には,オートマトン理論における古典的な結果に別の視点を新たに与えるものもあれば,オートマトン・形式言語理論と関わりのなさそうな分野との意外な繋がりを見せるものもある.オートマトン理論に習熟している方にも楽しんでもらえるよう,最近の結果や話題についても内容に盛り込んだ.
著者
新屋 良磨 Shinya Ryoma
巻号頁・発行日
2016-03 (Released:2016-02-19)
著者
新屋 良磨
出版者
日本ソフトウェア科学会
雑誌
コンピュータ ソフトウェア (ISSN:02896540)
巻号頁・発行日
vol.34, no.1, pp.1_119-1_124, 2017-01-25 (Released:2017-02-16)

与えられた言語が非正規であることの証明技法として,ポンピング補題や右同値類の有限性 (Myhill-Nerodeの定理) などの手法が有用であることが広く知られている.本論文ではこれらの手法とは全く異なる新しい非正規性の証明技法を提案する.いくつかの例題を通じて提案手法の新規性・有用性を議論し,さらに提案手法の課題についても具体的に述べる.提案技法は言語の測度に基づくものであり,「与えられた言語Lがほとんど空(測度が0)である」という直観的な性質を非正規性の証明に用いる.
著者
新屋 良磨 光成 滋生 佐々 政孝
出版者
日本ソフトウェア科学会
雑誌
コンピュータ ソフトウェア (ISSN:02896540)
巻号頁・発行日
vol.30, no.2, pp.2_191-2_206, 2013-04-25 (Released:2013-08-25)

正規表現によるパターンマッチングは広く用いられており,これまで様々なマッチング手法が研究されてきた.正規表現をDFAに変換してマッチングを行う手法もその1つである.本論文では2つの高速化手法を提案する.1つ目の手法は,マッチングの並列化である.マッチング対象となる文字列を複数に分割してデータ並列にマッチング可能な,同時状態有限オートマトン(Simultaneous Finite Automata, SFA)をオートマトン理論の自然な拡張によって定義した.2つ目は,DFA・SFAから,ネイティブコードを実行時に最適化して生成する手法である.コード生成によって,既存実装に比べてマッチング時のスループットの向上が見込め,また特定の正規表現における最適化も可能となる.最終的に,これらの手法を実装し,マルチコアマシン上での評価を基にその有用性を確認した.
著者
新屋 良磨
出版者
日本ソフトウェア科学会
雑誌
コンピュータ ソフトウェア (ISSN:02896540)
巻号頁・発行日
vol.30, no.3, pp.3_163-3_179, 2013-07-25 (Released:2013-08-31)

Abstract Numeration System (ANS)は自然数と言語を一対一に対応づける記数法(Numeration System)である.本論文では,正規言語Lについて,Lに属する文字列wのL上のANSでの数 – wのL内での順番の計算によって圧縮を定義する.さらに,ANSによる圧縮では: (1) (無限集合である)正規言語Lから平均圧縮率を計算可能.(2) 圧縮対象の文字列長に対し準線形時間で圧縮可能.(3) 圧縮対象文字列wを分割して並列に圧縮可能等の良い性質を持つことを示す.本論文において,特に断らない限り任意長整数の乗算が定数時間で計算可能な一様コストモデルを仮定するが,乗算にコストがかかる場合での議論や解決策の提案も行う.