新屋  良磨 (シンヤ リョウマ)

SIN'YA Ryoma

写真a

所属

大学院理工学研究科  数理・電気電子情報学専攻  数理科学コース 

生年

1988年

メールアドレス

メールアドレス

研究分野・キーワード

形式言語・オートマトン理論

出身大学 【 表示 / 非表示

  • 2007年04月
    -
    2011年03月

    琉球大学   工学部   情報工学科   卒業

出身大学院 【 表示 / 非表示

  • 2011年04月
    -
    2016年03月

    東京工業大学  情報理工学研究科  数理・計算科学専攻  博士課程  修了

留学履歴 【 表示 / 非表示

  • 2015年10月
    -
    2016年10月

    テレコム・パリテック   客員博士学生

取得学位 【 表示 / 非表示

  • 東京工業大学 -  博士(理学)

職務経歴(学内) 【 表示 / 非表示

  • 2017年11月
    -
    継続中

    秋田大学   大学院理工学研究科   数理・電気電子情報学専攻   数理科学コース   特任助教  

職務経歴(学外) 【 表示 / 非表示

  • 2016年04月
    -
    2017年10月

      東京大学   大学院情報理工学研究科   研究員

専門分野(科研費分類) 【 表示 / 非表示

  • 情報学基礎理論

  • 数学基礎・応用数学

 

学位論文 【 表示 / 非表示

論文 【 表示 / 非表示

  • On average-case hardness of higher-order model checking

    Nakamura Y.

    Leibniz International Proceedings in Informatics, LIPIcs ( Leibniz International Proceedings in Informatics, LIPIcs )  167   2020年06月  [査読有り]

    ISBN:9783959771559

    国内共著

    DOI

  • Context-Freeness of Word-MIX Languages

    Ryoma Sin'ya

    The proceedings of the 24th International Conference on Developments in Language Theory (DLT2020) ( Springer International Publishing )  12086   304 - 318   2020年05月  [査読有り]

    ISBN:978-3-030-48515-3

    単著

    DOI

  • Almost Every Simply Typed Lambda-Term Has a Long Beta-Reduction Sequence

    Kazuyuki Asada, Naoki Kobayashi, Ryoma Sin'ya, Takeshi Tsukada

    Logical Methods in Computer Science   15 ( 1 )   2019年02月  [査読有り]  [招待有り]

    国内共著

    It is well known that the length of a beta-reduction sequence of a simply typed lambda-term of order k can be huge; it is as large as k-fold exponential in the size of the lambda-term in the worst case. We consider the following relevant question about quantitative properties, instead of the worst case: how many simply typed lambda-terms have very long reduction sequences? We provide a partial answer to this question, by showing that asymptotically almost every simply typed lambda-term of order k has a reduction sequence as long as (k-1)-fold exponential in the term size, under the assumption that the arity of functions and the number of variables that may occur in every subterm are bounded above by a constant. To prove it, we have extended the infinite monkey theorem for strings to a parametrized one for regular tree languages, which may be of independent interest. The work has been motivated by quantitative analysis of the complexity of higher-order model checking.

  • Linear Pseudo-Polynomial Factor Algorithm for Automaton Constrained Tree Knapsack Problem

    Soh Kumabe, Takanori Maehara, Ryoma Sin’ya

    The proceedings of the 13th International Conference and Workshop on Algorithms and Computation (WALCOM 2019)     248 - 260   2018年12月  [査読有り]

    国内共著

    The automaton constrained tree knapsack problem is a variant of the knapsack problem in which the items are associated with the vertices of the tree, and we can select a subset of items that is accepted by a tree automaton. If the capacities or the profits of items are integers, it can be solved in pseudo-polynomial time by the dynamic programming algorithm. However, this algorithm has a quadratic pseudo-polynomial factor in its complexity because of the max-plus convolution. In this study, we propose a new dynamic programming technique, called heavy-light recursive dynamic programming, to obtain algorithms having linear pseudo-polynomial factors in the complexity. Such algorithms can be used for solving the problems with polynomially small capacities/profits efficiently, and used for deriving efficient fully polynomial-time approximation schemes. We also consider the k-subtree version problem that finds k disjoint subtrees and a solution in each subtree that maximizes total profit under a budget constraint. We show that this problem can be solved in almost the same complexity as the original problem.

  • オートマトン理論再考

    新屋良磨

    コンピュータソフトウェア   34 ( 3 ) 3 - 35   2017年09月  [査読有り]  [招待有り]

    ISSN:0289-6540

    単著

    オートマトンは最も単純な計算のモデルである.その単純さゆえに初学者にとっても理解しやすく,情報系の学部においては「計算理論」や「形式言語理論」などの講義はまずオートマトンから教え始めることが標準となっている.一方,その単純さゆえに理論的な深みやさらなる研究の余地がないと誤解されることもしばしばあり,また,講義や解説書においても応用的な需要からかより強力な計算モデルに重きが置かれることも多い.
    本サーベイではオートマトン理論の基礎から始め,三話構成でオートマトン・形式言語理論の様々な定理を解説していく.解説する定理の中には,オートマトン理論における古典的な結果に別の視点を新たに与えるものもあれば,オートマトン・形式言語理論と関わりのなさそうな分野との意外な繋がりを見せるものもある.オートマトン理論に習熟している方にも楽しんでもらえるよう,最近の結果や話題についても内容に盛り込んだ.

    DOI

全件表示 >>

Book(書籍) 【 表示 / 非表示

  • 正規表現技術入門

    新屋良磨,鈴木勇介,高田謙 (担当: 共著 )

    技術評論社  2015年04月 ISBN: 4774172707

学術関係受賞 【 表示 / 非表示

  • 情報処理学会第 57 回プログラミング・シンポジウム 山内奨励賞

    2017年01月   情報処理学会  

    受賞者:  新屋良磨