正規言語で修士号を取得しました.修論を公開します.

このエントリーをはてなブックマークに追加
はてなブックマーク - 正規言語で修士号を取得しました.修論を公開します.
Share on Facebook
Post to Google Buzz

 

2013年3月に東京工業大学大学院情報理工学研究科数理・計算科学専攻の修士過程を卒業しました.

現在は同専攻で博士課程学生としてお勉強&研究に打ち込んでいます(あ,所属研究室が佐々研から首藤研に変わりました).

 

修論を

せっかくなので修士論文を公開します.

cover

正規言語上の Abstract Numeration System の 文字列圧縮への応用(PDF)

 修士論文のタイトルは

「正規言語上の Abstract Numeration System の文字列圧縮への応用」

というものです.タイトルは厳めしいですが,内容は非常にシンプルです. この論文では正規言語の数え上げ理論,及びその計算量や圧縮率(+いくつかの応用策)について論じています.

簡単に言うと以前ブログで扱ったRANSの理論の話です(正規表現を使ってデータ圧縮等するツールを作りました)

 

目次

  • 図目次
  • 図や記号に関する注意
  • 1章 はじめに
  • 第1部 準備
    • 2章 正規言語とオートマトン
      • 2.1 形式的定義
      • 2.2 決定性,無曖昧性,非決定性
      • 2.3オートマトンの行列表現
    • 3章 Combinatorial Complexity
      • 3.1 数え上げ関数
      • 3.2 数え上げ関数に関するShurの定理
    • 4章 Abstract Numeration System
      • 4.1 形式的定義
      • 4.2 $n$数法との関係
      • 4.3 平方数に関するEilenbergの定理
  • 第2部2 正規言語上のAbstract Numeration Systemの文字列圧縮への応用
    • 5章 DFAを用いたANSのアルゴリズム
      • 5.1 valS の計算
      • 5.2 repS の計算
      • 5.3 計算量
    • 6章 ANSによる文字列圧縮
      • 6.1 ANS間の基数変換
      • 6.2 圧縮率
    • 7章 応用
      • 7.1 URIの圧縮
      • 7.2 符号
      • 7.3 分割基数変換
    • 8章 議論
      • 8.1 文脈自由言語への拡張の困難さ
      • 8.2 エントロピーベース圧縮法との対比
      • 8.3 圧縮に適した正規言語
    • 9章 まとめ
  • 謝辞
  • 付 録
    • RFC 3986 定義のURI文法
      • 拡張BNFによる定義
      • 拡張正規表現による定義
    • RFC 3986 定義のURI文法
      • 正規言語の同定問題の困難性
      • 順序の問題
  • 索引
  • 参考文献

 

実は

一般の方(正規表現とかオートマトンとか良く知らない人)向けに,解説を付加したり,お話風にしたり,構成を変更したバージョンも作成して公開しようとしていたのですが,色々あって見送りという形になりました.いずれ書きたいものです(書かないフラグ).

  1. コメントはまだありません。

  1. トラックバックはまだありません。

 
Better Tag Cloud