橋本健二 (ハシモト　ケンジ)

研究者情報

学位

• 博士(情報科学)（2009年03月 大阪大学）

J-Global ID

• 202301019753756290

研究キーワード

• SAT   モデル計数   形式言語理論   

研究分野

• 情報通信 / ソフトウェア
• 情報通信 / 情報学基礎論

経歴

• 2024年04月 - 現在  香川大学創造工学部准教授
• 2017年04月 - 2024年03月  名古屋大学大学院情報学研究科情報システム学専攻助教
• 2013年10月 - 2017年03月  名古屋大学大学院情報科学研究科情報システム学専攻助教
• 2009年04月 - 2013年09月  奈良先端科学技術大学院大学情報科学研究科助教

学歴

•         - 2009年03月   大阪大学   情報科学研究科
•         - 2006年03月   大阪大学   情報科学研究科
•         - 2004年03月   大阪大学   基礎工学部

所属学協会

• 電子情報通信学会   情報処理学会   

研究活動情報

論文

• An ambiguity hierarchy of weighted context-free grammars

  Inoue Y; Hashimoto K; Seki H

  Theoretical Computer Science 974 Theoretical Computer Science 2023年09月 [査読有り]
  
• When Is Context-Freeness Distinguishable from Regularity? an Extension of Parikh’s Theorem

  Yusuke Inoue; Kenji Hashimoto; Hiroyuki Seki

  27th International Conference on Implementation and Application of Automata (CIAA 2023) , LNCS 14151 166 - 178 2023年09月 [査読有り]
  
• Characterizing attributed tree translations in terms of macro tree transducers

  Hashimoto Kenji; Maneth Sebastian

  Theoretical Computer Science 963 Theoretical Computer Science 2023年06月 [査読有り]
  
• Weighted Multiple Context-Free Grammars

  Inoue Yusuke; Hashimoto Kenji; Seki Hiroyuki

  IEICE Transactions on Information and Systems E106.D 3 309 - 318 一般社団法人 電子情報通信学会 2023年03月 [査読有り]
  
• An Ambiguity Hierarchy of Weighted Context-Free Grammars

  Inoue Yusuke; Hashimoto Kenji; Seki Hiroyuki

  26th International Conference on Implementation and Application of Automata (CIAA 2022) 13266 238 - 250 2022年06月 [査読有り]
  
• On the Compositionality of Dynamic Leakage and Its Application to the Quantification Problem

  Bao Trung Chu; Kenji Hashimoto; Hiroyuki Seki

  13th International Conference on Emerging Security Information, Systems and Technologies (SECURWARE 2019) 1 - 8 2019年10月 [査読有り]
  
• Quantifying Dynamic Leakage -- Complexity Analysis and Model Counting-based Calculation

  Trung Bao Chu; Kenji Hashimoto; Hiroyuki Seki

  IEICE Transactions on Information and Systems E102-D 10 1952 - 1965 2019年10月 [査読有り]
  
• Graph Compression by Tree Grammars and Direct Evaluation of Regular Path Query

  Takeshi Takeda; Kenji Hashimoto; Hiroyuki Seki

  IEEE 4th International Conference on Computer and Communication Systems (ICCCS 2019) 257 - 262 2019年02月 [査読有り]
  
• Counting Algorithms for Recognizable and Algebraic Series

  Trung Bao Chu; Kenji Hashimoto; Hiroyuki Seki

  IEICE Transactions on Information and Systems E101-D 6 1479-1490  2018年06月 [査読有り]
  
• Direct Update of XML Documents with Data Values Compressed by Tree Grammars

  Kenji Hashimoto; Ryunosuke Takayama; Hiroyuki Seki

  IEICE Transactions on Information and Systems E101-D 6 1467-1478  2018年06月 [査読有り]
  
• Direct Evaluation of Selecting Tree Automata on XML Documents Compressed with Top Trees

  Kenji Hashimoto; Suguru Nishimura; Hiroyuki Seki

  Proceedings of the 4th International Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2016) 29-36  2016年07月 [査読有り]
  
• Query Rewriting for Nondeterministic Tree Transducers

  Kazuki Miyahara; Kenji Hashimoto; Hiroyuki Seki

  IEICE Transactions on Information and Systems E99-D 6 1410-1419  2016年06月 [査読有り]
  
• Determinacy and Subsumption of Single-valued Bottom-up Tree Transducers

  Kenji Hashimoto; Ryuta Sawada; Yasunori Ishihara; Hiroyuki Seki; Toru Fujiwara

  IEICE Transactions on Information and Systems E99-D 3 575-587  2016年03月 [査読有り]
  
• The Consistency and Absolute Consistency Problems of XML Schema Mappings between Restricted DTDs

  Hayato Kuwada; Kenji Hashimoto; Yasunori Ishihara; Toru Fujiwara

  World Wide Web Journal 18 5 1443-1461  2015年09月 [査読有り]
  
• Query-based l-diversity

  Chittaphone Phonharath; Ryonosuke Takayama; Kenji Hashimoto; Hiroyuki Seki

  Proceedings of the 7th International Conference on Advances in Databases, Knowledge, and Data Applications (DBKDA 2015) 15-20  2015年05月 [査読有り]
  
• Node Query Preservation for Deterministic Linear Top-Down Tree Transducers

  Kazuki Miyahara; Kenji Hashimoto; Hiroyuki Seki

  IEICE Transactions on Information and Systems E98-D 3 512-523  2015年03月 [査読有り]
  
• Node Query Preservation for Deterministic Linear Top-Down Tree Transducers

  Kazuki Miyahara; Kenji Hashimoto; Hiroyuki Seki

  2nd International Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2013), Electronic Proceedings in Theoretical Computer Science 134 27-37  2013年10月 [査読有り]
  
• XPath Satisfiability with Parent Axes or Qualifiers Is Tractable under Many of Real-World DTDs

  Yasunori Ishihara; Nobutaka Suzuki; Kenji Hashimoto; Shogo Shimizu; Toru Fujiwara

  Proceedings of the 14th International Symposium on Database Programming Languages 1-10  2013年08月 [査読有り]
  
• Decidability of k-secrecy against Inference Attacks Using Functional Dependencies on XML Databases

  Nobuaki Yamazoe; Kenji Hashimoto; Yasunori Ishihara; Toru Fujiwara

  Proceedings of the 2013 International Conference on Parallel and Distributed Processing Techniques and Applications 182-188  2013年07月 [査読有り]
  
• Deciding Schema k-Secrecy for XML Databases

  Chittaphone Phonharath; Kenji Hashimoto; Hiroyuki Seki

  IEICE Transactions on Information and Systems E96-D 6 1268-1277  2013年06月 [査読有り]
  
• The Consistency and Absolute Consistency Problems of XML Schema Mappings between Restricted DTDs

  Hayato Kuwada; Kenji Hashimoto; Yasunori Ishihara; Toru Fujiwara

  Proceedings of the 15th International Asia-Pacific Web Conference 228-239  2013年04月 [査読有り]
  
• Determinacy and Subsumption for Single-valued Bottom-up Tree Transducers

  Kenji Hashimoto; Ryuta Sawada; Yasunori Ishihara; Hiroyuki Seki; Toru Fujiwara

  Proceedings of the 7th International Conference on Language and Automata Theory and Applications 335-346  2013年04月 [査読有り]
  
• Typing XPath Subexpressions With Respect to an XML Schema

  Yasunori Ishihara; Kenji Hashimoto; Atsushi Ohno; Takuji Morimoto; Toru Fujiwara

  Proceedings of the 5th International Conference on Advances in Databases, Knowledge, and Data Applications 128-133  2013年01月 [査読有り]
  
• XPath Satisfiability with Downward and Sibling Axes Is Tractable under Most of Real-world DTDs

  Yasunori Ishihara; Kenji Hashimoto; Shougo Shimizu; Toru Fujiwara

  Proceedings of the 12th International Workshop on Web Information and Data Management 11-18  2012年11月 [査読有り]
  
• Verification of the Security against Inference Attacks on XML Databases

  Chittaphone Phonharath; Kenji Hashimoto; Hiroyuki Seki

  The 1st International Workshop on Trends in Tree Automata and Tree Transducers 11-22  2012年06月 [査読有り]
  
• Decidability of the Security against Inference Attacks using a Functional Dependency on XML Databases

  Kenji Hashimoto; Hiroto Kawai; Yasunori Ishihara; Toru Fujiwara

  IEICE Transactions on Information and Systems E95-D 5 1365-1374  2012年05月 [査読有り]
  
• Validity of Positive XPath Queries with Wildcard in the Presence of DTDs

  Kenji Hashimoto; Yohei Kusunoki; Yasunori Ishihara; Toru Fujiwara

  The 13th International Symposium on Database Programming Languages 1-8  2011年08月 [査読有り]
  
• A Tractable Subclass of DTDs for XPath Satisfiability with Sibling Axes

  Yasunori Ishihara; Takuji Morimoto; Shougo Shimizu; Kenji Hashimoto Toru Fujiwara

  Proceedings of the 12th International Symposium on Database Programming Languages 68-83  2009年08月 [査読有り]
  
• Verification of the Security against Inference Attacks on XML Databases

  Kenji Hashimoto; Kimihide Sakano; Fumikazu Takasuka; Yasunori Ishihara; Toru Fujiwara

  IEICE Transactions on Information and Systems E92-D 5 1022-1032  2009年05月 [査読有り]
  
• Verification of the Security against Inference Attacks on XML Databases

  Kenji Hashimoto; Fumikazu Takasuka; Kimihide Sakano; Yasunori Ishihara; Toru Fujiwara

  Proceedings of the 10th Asia Pacific Web Conference 359-370  2008年04月 [査読有り]
  
• XMLデータベースにおけるスキーマ進化のための更新操作群とそれらのスキーマ表現能力保存に関する性質

  橋本 健二; 石原 靖哲; 藤原 融

  電子情報通信学会論文誌(D) J90-D 4 990-1004  2007年04月 [査読有り]
  
• XMLデータベースへの推論攻撃による機密情報特定可能性の形式化とある前提条件のもとでの特定可能性検証法の提案

  高須賀 史和; 橋本 健二; 石原 靖哲; 藤原 融

  日本データベース学会Letters 5 2 21-24  2006年09月 [査読有り]
  
• Schema Update Operations Preserving the Expressive Power in XML Databases

  Kenji Hashimoto; Yasunori Ishihara; Toru Fujiwara

  Proceedings of the International Special Workshop on Databases for Next Generation Researchers in Memoriam Prof. Yahiko Kambayashi 38-41  2005年04月 [査読有り]
  

書籍

• 理論計算機科学事典

  (担当:分担執筆範囲:5.2 木オートマトン，木トランスデューサ)朝倉書店 2022年01月 807 456-471

講演・口頭発表等

• An Ambiguity Hierarchy of Weighted Context-free Grammars  [通常講演]

  Yusuke Inoue; Kenji Hashimoto; Hiroyuki Seki

  第25回プログラミングおよびプログラミング言語ワークショップ（PPL 2023） 2023年03月 口頭発表（一般）
• 重み付き文脈自由文法の曖昧さ階層について  [通常講演]

  井上 裕介; 橋本 健二; 関 浩之

  2022年度 夏のLAシンポジウム 2022年07月 口頭発表（一般）
• Solving Rep-tile by Computers

  Mutsunori Banbara; Kenji Hashimoto; Takashi, Horiyama; Shin-ichi Minato; Kakeru Nakamura; Masaaki Nishino; Masahiko Sakai; Ryuhei Uehara; Yushi Uno; Norihito Yasuda

  The 14th Gathering 4 Gardner Conference (2022) 2022年04月 口頭発表（一般）
• 重み付き文脈自由文法の曖昧さ階層について

  井上 裕介; 橋本 健二; 関 浩之

  電子情報通信学会コンピュテーション研究会 2022年03月 口頭発表（一般）
• レプ・タイルの定式化を用いた各種ソルバの性能比較  [通常講演]

  番原 睦則; 橋本 健二; 堀山 貴史; 湊 真一; 中村 駆; 西野 正彬; 酒井 正彦; 上原 隆平; 宇野 裕之; 安田 宜仁

  人工知能学会 第119回人工知能基本問題研究会 2022年01月 口頭発表（一般）
• 命題論理式の全ての投射モデルを表現するBDDの構成法  [通常講演]

  磯貝孝明; 橋本健二; 酒井正彦

  第116回人工知能基本問題研究会 2021年03月 口頭発表（一般） オンライン
• 擬ブール制約の導入による組合せ最適化ソルバCombSQL+の高速化

  岸潤一郎; 酒井正彦; 西田直樹; 橋本健二

  ソフトウェアサイエンス研究会 2021年01月 口頭発表（一般） オンライン 電子情報通信学会
  
• 組合せ最適化問題の記述からSMTソルバの入力式を生成するSQL問合せ

  坂梨元軌; 酒井正彦; 西田直樹; 橋本健二

  ソフトウェアサイエンス研究会 2019年03月 口頭発表（一般） 那覇
• 組合せ最適化問題を記述するための関係代数の集合上への拡張  [通常講演]

  坂梨 元軌; 酒井 正彦; 西田 直樹; 橋本 健二

  第20回プログラミングおよびプログラミング言語ワークショップ PPL2018 2018年03月 ポスター発表
• 配列を含むC言語サブセットから難解言語Malbolgeへのコンパイラ  [通常講演]

  岩金 カナン; 坂梨 元軌; 酒井 正彦; 西田 直樹; 橋本 健二

  第20回プログラミングおよびプログラミング言語ワークショップ PPL2018 2018年03月 ポスター発表
• 有向グラフに対する圧縮法および圧縮グラフに対する頂点選択問合せ評価法の提案  [通常講演]

  武田 健志; 橋本 健二; 関 浩之

  第10回データ工学と情報マネジメントに関するフォーラム（DEIM 2018） 2018年03月 口頭発表（一般）
• 線形マルチボトムアップ木変換器の関数性の決定可能性  [通常講演]

  田端 浩明; 橋本 健二

  第118回情報処理学会プログラミング研究会 2018年03月 口頭発表（一般）
• 非決定性選択木オートマトンの決定化

  川本 将也; 橋本 健二; 関 浩之

  第117回情報処理学会プログラミング研究会 2018年01月
• トップ木に基づく圧縮データに対する直接更新法

  西村 卓; 橋本 健二; 関 浩之

  電子情報通信学会ソフトウェアサイエンス研究会 2017年10月
• 再帰呼び出しを持つC言語サブセットからMalbolgeへのコンパイラ

  坂梨 元軌; 河邉 翔平; 酒井 正彦; 西田 直樹; 橋本 健二

  電子情報通信学会ソフトウェアサイエンス研究会 2017年07月
• 木文法に基づくグラフ圧縮法および圧縮グラフに対する頂点選択問合せ評価法

  武田 健志; 関 浩之; 橋本 健二

  電子情報通信学会ソフトウェアサイエンス研究会 2017年07月
• 成分分割を用いる投射モデル計数ソルバにおける成分単位でのSAT判定を利用した性能改善

  鈴木 涼介; 橋本 健二; 酒井 正彦

  人工知能学会人工知能基本問題研究会 2017年03月
• モデル計数を用いた量的情報流解析のための論理式簡約と静的解析

  中島 聖斗; 橋本 健二; 酒井 正彦; 関 浩之

  電子情報通信学会ソフトウェアサイエンス研究会 2017年03月
• 非線形トップダウン木変換器において問合せ保存が決定可能であるための十分条件

  石原 鷹; 橋本 健二; 関 浩之

  電子情報通信学会ソフトウェアサイエンス研究会 2017年03月
• 木文法に基づき圧縮されたXML文書に対するデータ値を考慮した直接更新法

  高山 隆之介; 橋本 健二; 関 浩之

  第9回データ工学と情報マネジメントに関するフォーラム（DEIM 2017） 2017年03月
• Counting for Recognizable and Algebraic Series

  関 浩之; 橋本 健二; Trung Chu Bao

  情報処理学会 第113回プログラミング研究発表会 2017年03月
• あるクラスのXPath式から先読み付き決定性選択木オートマトンへのスキーマを用いた変換

  川本 将也; 橋本 健二; 関 浩之

  電子情報通信学会ソフトウェアサイエンス研究会 2017年01月
• #SMTツールを用いた量的情報流解析手法の高速化

  中島 聖斗; Trung Chu Bao; 橋本 健二; 酒井 正彦; 関 浩之

  電子情報通信学会ソフトウェアサイエンス研究会 2016年10月
• 木文法に基づく圧縮XML文書に対するデータ値を考慮した直接更新手法

  高山 隆之介; 橋本 健二; 関 浩之

  電子情報通信学会ソフトウェアサイエンス研究会 2016年10月
• Determinacy and Query Preservation of Tree Transducers  [招待講演]

  Kenji Hashimoto

  The 4th International Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2016) 口頭発表（招待・特別）
• トップ木に基づく木圧縮法の実装と問い合わせ処理法の提案

  西村 卓; 橋本 健二; 関 浩之

  電子情報通信学会ソフトウェアサイエンス研究会 2016年07月

MISC

• GPMC version mc2020

  Kenji Hashimoto Model Counting Competition 2020 2020年07月

受賞

• 2023年09月 グラフ数え上げ国際競技会 アイデア部門（The Inspiring Idea Track）第1位
   NaPS+GPMC international_society 

  受賞者: 小栗滉介;橋本健二;酒井正彦
• 2023年07月 Model Counting Competition 2023 Projected Weighted Model Counting Track Ranking A the 1st place
   GPMC international_society 

  受賞者: Kenji Hashimoto
• 2022年08月 Model Counting Competition 2022 Projected Weighted Model Counting Track Ranking B 1st place
   international_society 

  受賞者: Kenji Hashimoto;Shota Yap
• 2022年08月 Model Counting Competition 2022 Projected Model Counting Track Ranking A 1st place
   GPMC international_society 

  受賞者: Kenji Hashimoto;Shota Yap
• 2018年07月 電子情報通信学会ソフトウェアサイエンス研究会 平成29年度電子情報通信学会ソフトウェアサイエンス研究会 研究奨励賞
   トップ木に基づく圧縮データに対する直接更新法 JPN japan_society 

  受賞者: 西村卓;橋本健二;関浩之
• 2013年05月 電子情報通信学会ソフトウェアサイエンス研究会 平成24年度電子情報通信学会ソフトウェアサイエンス研究会 研究奨励賞
   決定性線形下降木変換器における頂点問合せ保存 JPN japan_society 

  受賞者: 宮原 一喜;橋本 健二;関 浩之
• 2008年12月 数理モデル化と問題解決研究会 第72回数理モデル化と問題解決研究会プレゼンテーション賞
   XML Schema Evolution Preserving Information Based on the User-specified Relationship japan_society 

  受賞者: Kenji Hashimoto

共同研究・競争的資金等の研究課題

• 投射モデル計数のためのグラフ表現を用いた問題分類と計数戦略

  科学研究費助成事業

  研究期間 : 2023年04月 -2026年03月 

  代表者 : 橋本 健二

   

  確率や量的な安全尺度の計算への応用を背景にして、論理式の解（モデル）の個数を高速に数える技術の必要性が高まっている。命題論理式のための既存の投射モデル計数ソルバやその計数戦略には一長一短があるが、それらを入力問題ごとに適切に切り替えるための有効な問題分類方法は知られていない。本研究では、論理式のグラフ表現に着目し、その特徴量を用いた投射モデル計数のための問題分類と計数戦略決定を試みる。機械学習を用いたモデル学習を通して、投射モデル計数問題の分類に役立つグラフ表現の特徴量を見いだすことで、高速に解くことができる適切なソルバや計数戦略を問題ごとに決定するシステムを構築する。
• データハイブリッドなリアクティブプログラムの解析技術と自動合成・説明抽出への応用

  日本学術振興会：科学研究費助成事業

  研究期間 : 2022年04月 -2025年03月 

  代表者 : 関 浩之; 小川 瑞史; 結縁 祥治; 橋本 健二

   

  レジスタ計算モデルに関する研究：データ値を扱う計算モデルであるレジスタオートマトン(RA), レジスタ文脈自由文法(RCFG), レジスタ木オートマトン(RTA)の能力を考察するため，それらの表現する言語クラスに対するポンプ補題を証明した．本補題を用い，RA, RCFG, RTAでは表現できない言語の具体例を示した． RAに対応する論理として，凍結演算子付きμ-計算（μ↓-計算）が知られている．しかしμ↓-計算は表現能力が大きすぎて自動検証への応用は難しい．本研究では，論理積に関する制約（高々一方のオペランドにしか凍結演算子，X以外の時相演算子を含まない）を満たす部分クラスμd↑-計算を定義し，RAとμd↑-計算の表現能力が同一であることを証明した． ノミナル集合はデータ値の無限集合を群論的に拡張した概念である．本研究では，決定性上昇型ノミナル木オートマトン(DBNTA)を定義し，DBNTAに対する対話型学習アルゴリズムを提案した．ノミナル集合上の適切な半順序を定義し，２つの軌道有限集合間にこの半順序に関する無限鎖が存在しないことを示すことで，提案アルゴリズムの停止性を証明した． 重み付きモデルに関する研究：多重文脈自由文法（mcfg）は文脈自由文法(cfg)の自然な拡張である．本研究では，mcfgに重みを導入したwmcfgを定義した．wmcfgは語の組を重みに対応づける関数を表現する．続いて，wmcfgに対する２つの基本問題が多項式時間判定可能であること，wmcfgによって表現される関数のクラスが，基本的な4つの演算に対して閉じていること等を証明した． 重み付きcfg(wcfg)は，cfgに重みを導入した計算モデルである．本研究では，トロピカル半環上の無あいまいwcfg, 有限あいまいwcfg, 多項式あいまいwcfg, および，一般のwcfgの間に，表現能力に関する真の階層関係が存在すること等を証明した．
• データハイブリッドなリアクティブプログラムの解析技術と自動合成・説明抽出への応用

  日本学術振興会：科学研究費助成事業

  研究期間 : 2022年04月 -2025年03月 

  代表者 : 関 浩之; 小川 瑞史; 結縁 祥治; 橋本 健二

   

  組込み制御ソフトウェアに代表されるリアクティブプログラムの信頼性を担保するための数理的手法を実用システムに適用可能にするためには，データ値，時間，確率等の量的概念を考慮した計算モデルの設定が鍵となる．本研究ではこのような問題意識のもとに，以下の課題に取り組む． データ値を扱うモデルであるレジスタ計算モデルについて，表現能力の同定，基本問題の計算量解析，特にリアクティブ合成問題とそれに関連するゲーム構造の数理的解析を行う． 重みとは，コスト等，計算に従って発生する付随量を表す．重み付き計算モデルの表現能力を明らかにし，重み付き計算モデルの対話的学習アルゴリズムを開発して，説明可能AIへ応用する．
• ソフトウェアモデルへの量的尺度の導入とプログラム解析への応用

  日本学術振興会：科学研究費助成事業

  研究期間 : 2019年04月 -2023年03月 

  代表者 : 関 浩之; 小川 瑞史; 結縁 祥治; 橋本 健二

   

  ソフトウェアの信頼性を担保するための数理的解析・検証技術を実用システムに適用可能にするためには，対象とする系をデータ値，時間，確率，情報量等の量的概念を考慮した数理的モデルに拡張する必要がある．本研究ではこのような問題意識のもとに，量的情報流の動的解析，データ値をもつ計算モデルとその構造化文書処理への応用，および，重みをもつ計算モデルとそのソフトウェアコスト解析への応用の３つの課題に取り組む．それぞれの課題において，オートマトンや形式文法に基づく適切な計算モデルを設定し，基本問題の計算量の解析，効率のよいアルゴリズムの開発，および，ツールの試作と実験に基づく提案手法の有効性の評価を行う． データ値をもつ計算モデルとそのソフトウェア開発への応用に関して以下の成果を得た． (1) 再帰プログラムのための簡潔な計算モデルとしてプッシュダウンシステム(Pushdown System, PDSと略)が知られている．本研究ではPDSをレジスタ付きに拡張したレジスタPDS（RPDSと略）を導入し，その高信頼ソフトウェア開発への応用に取り組んだ．レジスタオートマトンによって認識される言語を正則言語とよぶ．本研究ではまず，RPDSが前方正則保存性をもつことを証明した．この成果も踏まえ，RPDSのLTLモデル検査問題が判定可能であることを証明し，その計算複雑さについて明らかにした． (2) (1)のモデル検査問題ではプログラムのモデルはデータ値を扱えるが仕様（検証項目）を記述するLTL（時相論理）式ではデータ値を直接記述できない．そこで，レジスタオートマトンに変換可能な凍結演算子付き線形時相論理の部分クラスを見出した． (3) レジスタをもつ計算モデルとして，レジスタオートマトン，レジスタ文脈自由文法，ボトムアップ型レジスタ木オートマトンの表現する言語クラスのそれぞれに対して，いわゆるポンプの補題を証明した． 重み付き計算モデルとその応用：重み付きレジスタオートマトン(WRA)に対する重み最小実行問題の計算複雑さの解析とアルゴリズムの開発を行った成果をまとめた論文が，海外論文誌Theoretical Computer Science に採録された． また，文脈自由文法の拡張である多重文脈自由文法に重みを導入した重み付き多重文脈自由文法(WMCFG)を提案し，WMCFGに関する基本問題の判定可能性やWMCFGの生成する重み付き言語クラスの閉包性についても考察した．この研究発表に対して，電子情報通信学会ソフトウェアサイエンス研究会研究奨励賞を受賞した． 研究課題について，学術誌掲載論文３編，国内口頭発表４件の成果を挙げており，順調に進展していると自己評価できる． データ値をもつ計算モデルとそのソフトウェア開発への応用：今後は，再帰プログラムのための簡潔な計算モデルプッシュダウンシステム(Pushdown System, PDSと略)にレジスタを加えたRegister PDS(RPDSと略）について引き続き研究を行う．具体的に，RPDSのソフトウェア合成への応用として，プログラムの入出力関係を表す仕様が与えられたとき，それを満たすプログラムが存在するかを判定する実現可能性問題を考察する．具体的に，入力記号と出力記号が交互に並ぶような記号列からなる言語を認識するRPDSによって仕様を表現し，入力記号列を読んで出力記号列を生成するレジスタ付きプッシュダウン変換器（RPDTと略）によってモデル化する．既存研究として，有限オートマトン，レジスタオートマトン，PDSおよびそれらに対応する変換器を用いて定義された実現可能性問題の判定可能性が論じられているので，それらを参考にして理論的研究を進める． また，今年度の成果として得られた，レジスタオートマトン(RA)に変換可能な凍結演算子付き線形時相論理の部分クラスを拡張し，RAと能力等価な凍結演算子付きmu-計算の部分クラスを見出すことを試みる． 重み付き計算モデルとその応用：今後は，重み付き文脈自由文法（WCFG）の表現能力，例えば，曖昧さの程度（無曖昧，有限曖昧，多項式的曖昧など）が表現能力に及ぼす影響等について考察を行う．関連する既存研究として，重み付きオートマトンおよび重み付き木オートマトンについて，上述のような曖昧さの程度に基づく表現能力の階層性が示されている．階層性の証明には各クラスに対するポンプ補題が用いられる．WMCFGの部分クラスに対してもこの種のポンプ補題を証明することにより，曖昧さの程度に基づく部分クラスの階層性が証明できると予想している．
• 量的情報流解析のための投射モデル計数ソルバの開発

  科学研究費補助金

  研究期間 : 2017年04月 -2020年03月
• ソフトウェアセキュリティ・プライバシーのための静的解析・動的検査法

  日本学術振興会：科学研究費助成事業

  研究期間 : 2015年04月 -2019年03月 

  代表者 : 関 浩之; 小川 瑞史; 結縁 祥治; 橋本 健二

   

  非決定性木変換器における問合せ保存性について考察した．木文法およびトップ木に基づく圧縮法，圧縮データを解凍することなく直接問合せおよび更新する手法を提案・実装した．文脈自由文法にデータ値を扱う能力を限定的に加えたレジスタ文脈自由文法(RCFG)について，所属問題と空問題の計算量がEXPTIME完全であることなどを示した．また，ガード式において任意の２項関係を指定できるようにRCFGを一般化した．重み付きレジスタオートマトン(WRA)に関する基本問題の計算量を考察し，最小重み経路問題に帰着して求めるアルゴリズムを提案した．さらに，マルウェアの意味理解やSMTソルバに関する基礎的研究を行った．
• ソフトウェアセキュリティのための量を扱う計算モデルの提案

  日本学術振興会：科学研究費助成事業

  研究期間 : 2014年04月 -2018年03月 

  代表者 : 関 浩之; 橋本 健二

   

  ソフトウェアのセキュリティやプライバシーの尺度として，量的情報流，差分プライバシー等が提案され種々議論されている．本研究課題では主に量的情報流を中心にいくつかの定量的尺度について，それを計算するアルゴリズムや，そのような尺度に基づくソフトウェアの安全性検証手法の開発に取り組んだ．具体的に，復号アルゴリズムの時間攻撃による漏洩量の計算法，XMLデータベースにおけるk-安全性の検査法，#SMTソルバーを用いた量的情報流の計算手法，および文字列データの量的情報流解析の基礎となる認識可能級数および代数的級数に対する計数アルゴリズムの開発と，シミュレーションまたは実装ツールに基づく評価実験を行った．
• 木およびグラフ変換における問合せ保存の自動検証

  科学研究費補助金

  研究期間 : 2014年04月 -2017年03月
• 形式言語理論に基づく静的解析法とその安全性検査への応用

  日本学術振興会：科学研究費助成事業

  研究期間 : 2011年04月 -2016年03月 

  代表者 : 関 浩之; 小川 瑞史; 楫 勇一; 橋本 健二

   

  木言語理論を用い，XML文書等の構造化データに対する情報保存性およびセキュリティに関して以下の成果を挙げた．変換vが問合せqを保存するとは、任意のデータtに対して， tへの問合せqの結果を，変換の結果v(t)からも得ることができることをいう．木変換器や頂点問合せ等のモデルに基づき問合せ保存性問題の判定可能性や判定に要する計算量を明らかにした．許可問合せの結果や公開情報を利用して禁止問合せの結果(機密情報)を得ようとする行為を推論攻撃と呼ぶ．本研究ではk-安全性，l-多様性という推論攻撃に対する２つの安全性に着目・導入し，それらの判定可能性の理論的考察および判定手法の実験的評価を行った．
• 概念モデルと問合せ集合を用いたXMLスキーマの導出と更新

  日本学術振興会：科学研究費補助金

  研究期間 : 2010年04月 -2013年03月 

  代表者 : 橋本 健二

   

  XMLスキーマ更新やそれに伴う XML 文書変換を,情報保存の観点において適切に行うための手法を確立することを目指した。本研究では,問合せ保存と呼ばれる情報保存の一形式化に着目し,木変換器や木オートマトンなどを XML 文書に対する変換と問合せの形式モデルとして用いて問合せ保存性の問題定義を行った。そして,XML 文書変換と問合せが与えられたときに,変換前文書に対する問合せ結果を,変換後文書からでも取り出すことが可能な,変換後文書に対する問合せが存在するかを検査する手法と,実際に問合せ保存が満たされる場合に変換後文書に対する問合せを構成する方法を提案した。

委員歴

• 2018年06月 - 現在   電子情報通信学会ソフトウェアサイエンス研究専門委員会   専門委員
• 2019年06月 - 2023年05月   情報処理学会論文誌ジャーナル/JIP編集委員会   編集委員
• 2022年04月 - 2023年03月   第25回プログラミングおよびプログラミング言語ワークショップ(PPL 2023)   組織委員
• 2022年06月 - 2022年12月   第20回情報学ワークショップ(WiNF2022)   プログラム委員
• 2021年08月 - 2022年03月   第24回プログラミングおよびプログラミング言語ワークショップ(PPL 2022)   プログラム委員
• 2021年10月 - 2021年11月   第19回情報学ワークショップ(WiNF2021)   プログラム委員
• 2020年08月 - 2021年03月   第23回プログラミングおよびプログラミング言語ワークショップ(PPL 2021)   プログラム委員
• 2017年04月 - 2021年03月   情報処理学会プログラミング研究会   編集委員・運営委員

担当経験のある科目

情報数学香川大学
コンピュータ科学実験１名古屋大学
アルゴリズム理論明石工業高等専門学校
プログラミング演習奈良先端科学技術大学院大学
安全安心工学A奈良先端科学技術大学院大学
アルゴリズム概論奈良先端科学技術大学院大学

その他のリンク

researchmap

https://researchmap.jp/k-hasimt