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

SIN'YA Ryoma

写真a

所属

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

生年

1988年

メールアドレス

メールアドレス

研究キーワード 【 表示 / 非表示

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

  • Automata Theory

出身大学 【 表示 / 非表示

  • 2007年04月
    -
    2011年03月

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

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

  • 2011年04月
    -
    2016年03月

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

留学履歴 【 表示 / 非表示

  • 2015年10月
    -
    2016年10月

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

取得学位 【 表示 / 非表示

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

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

  • 2021年04月
    -
    継続中

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

  • 2017年11月
    -
    2021年03月

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

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

  • 2016年04月
    -
    2017年10月

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

学会(学術団体)・委員会 【 表示 / 非表示

  • 2020年12月
    -
    継続中
     

    日本国

     

    Computational Logic and Applications

  • 2016年04月
    -
    継続中
     

    日本国

     

    情報処理学会

  • 2016年04月
    -
    継続中
     

    日本国

     

    日本ソフトウェア科学会

研究分野 【 表示 / 非表示

  • 情報通信 / 情報学基礎論

  • 自然科学一般 / 数学基礎

 

学位論文 【 表示 / 非表示

研究等業績 【 表示 / 非表示

    ◆原著論文【 表示 / 非表示

  • Asymptotic Approximation by Regular Languages

    Ryoma Sin'ya

    The proceedings of the 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'21) ( Springer, Cham )  12607   74 - 88   2021年01月  [査読有り]

    研究論文(学術雑誌)   単著

    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.

  • オートマトン理論再考

    新屋良磨

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

    研究論文(学術雑誌)   単著

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

    DOI

  • 言語の測度に基づく非正規性の証明技法

    新屋良磨

    コンピュータソフトウェア   34 ( 1 ) 163 - 179   2017年02月  [査読有り]  [招待有り]

    研究論文(学術雑誌)   単著

    与えられた言語が非正規であることの証明技法として,ポンピング補題や右同値類の有限性 (Myhill-Nerodeの定理) などの手法が有用であることが広く知られている.本論文ではこれらの手法とは全く異なる新しい非正規性の証明技法を提案する.いくつかの例題を通じて提案手法の新規性・有用性を議論し,さらに提案手法の課題についても具体的に述べる.提案技法は言語の測度に基づくものであり,「与えられた言語Lがほとんど空(測度が0)である」という直観的な性質を非正規性の証明に用いる.

    DOI

  • ◆国際会議プロシーディングス【 表示 / 非表示

  • Words-to-Letters Valuations for Language Kleene Algebras with Variable Complements

    Yoshiki Nakamura, Ryoma Sin'ya

    Proceedings of the 16th International Conference on Automata and Formal Languages ( Electronic Proceedings in Theoretical Computer Science )    2023年09月  [査読有り]

    研究論文(国際会議プロシーディングス)   国内共著

  • Measuring Power of Generalised Definite Languages

    Ryoma Sin'ya

    In Proceedings of the 27th International Conference on Implementation and Application of Automata ( Springer )    2023年08月  [査読有り]

    研究論文(国際会議プロシーディングス)   単著

    DOI

  • Measuring Power of Locally Testable Languages

    Ryoma Sin'ya

    Proceedings of the 26th International Conference on Developments in Language Theory ( Springer )    2022年05月  [査読有り]

    研究論文(国際会議プロシーディングス)   単著

  • Carathéodory Extensions of Subclasses of Regular Languages

    Ryoma Sin'ya

    The proceedings of the 25th International Conference on Developments in Language Theory (DLT2021) ( Springer International Publishing )    2021年08月  [査読有り]

    研究論文(国際会議プロシーディングス)   単著

  • 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月  [査読有り]

    研究論文(国際会議プロシーディングス)   国内共著

    DOI

  • 全件表示 >>

    ◆研究会,シンポジウム資料等【 表示 / 非表示

  • 正則言語で極限的に近似可能な言語について

    新屋良磨

    第23回プログラミングおよびプログラミング言語ワークショップ (PPL2021)     2021年03月

    研究論文(研究会,シンポジウム資料等)   単著

  • ◆その他【 表示 / 非表示

  • Regular languages that can be approximated by testing subword occurrences

    Sin'ya R.

    Computer Software ( Computer Software )  40 ( 2 ) 49 - 60   2023年05月

    国内共著

    <p>言語<I>L</I>が正規可測であるとは,<I>L</I>に「収束」する正規言語の対の無限列が存在することを言う.本論文では,正規言語の代わりに正規言語の部分クラスである区分検査可能(Piecewise Testable (PT): 部分語の出現情報の Bool 演算で記述可能)言語および文字検査可能(Alphabet Testable (AT): 文字の出現情報の Bool 演算で記述可能)言語に焦点を当てその可測性を考察する.特に,正規言語に対するAT可測性はco-<B>NP</B>完全である一方,PT可測性は線形時間で決定できることを示す.</p>

    DOI CiNii Research

  • 形式言語理論:非可換と可換のあいだ

    新屋 良磨

    応用数理 ( 一般社団法人 日本応用数理学会 )  31 ( 4 ) 15 - 22   2021年12月

    <p>Formal language theory is the field of study of non-commutative objects so-called “languages” (sets of words). While many problems on languages are difficult to solve due to the non-commutativity, the situation could be drastically changed if we consider a commutative invariant of a language. This paper explains some commutative invariants of languages with concrete examples.</p>

    DOI CiNii Research

  • 形式言語における鳩ノ巣原理の探求 (代数系、論理、言語とその周辺領域)

    新屋 良磨

    数理解析研究所講究録 ( 京都大学数理解析研究所 )  ( 2096 ) 69 - 71   2018年12月

    リポジトリ

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

  • 正規表現技術入門

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

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

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

  • PPL2021発表賞

    2021年03月11日   第21回プログラミングおよびプログラミング言語ワークショップ   正則言語で極限的に近似可能な言語について

    受賞者:  新屋良磨

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

    2017年01月   情報処理学会  

    受賞者:  新屋良磨

科研費(文科省・学振)獲得実績 【 表示 / 非表示

  • 実効記述集合論,計算可能解析学およびオートマトン理論

    独立行政法人日本学術振興会 二国間交流事業 共同研究

    研究期間:  2020年04月  -  2022年03月  代表者:  木原貴行

  • 高階な言語の概普遍性判定問題の決定可能性の解析

    若手研究

    研究期間:  2019年04月  -  2023年03月  代表者:  新屋良磨


    高階言語はプログラムの正しさを検証する「モデル検査」と呼ばれる技術を中心に近年注目を集めている言語クラスであるが,未解明な基本的性質が多く残されている重要な研究対象である.
    本研究では高階言語に対する概普遍性判定問題と呼ばれる決定問題の決定可能性に着目し研究を進め,高階言語の母関数的・組合せ的性質の解明のへ新たな道を拓くことを目指す.

受託研究受入実績 【 表示 / 非表示

  • 測度論的な概念を用いた形式言語理論への新たなアプローチ

    提供機関: 国立研究開発法人 科学技術振興機構  一般受託研究

    研究期間:

    2021年10月
    -
    2024年03月

    代表者: 新屋良磨

学会等発表 【 表示 / 非表示

  • Context-Freeness of Word-MIX Languages

    Ryoma Sin'ya

    Developments in Language Theory 2021  2021年08月  -  2021年08月   

  • Caratheodory Extensions of Subclasses of Regular Languages

    Ryoma Sin'ya

    Developments in Language Theory 2021  2021年08月  -  2021年08月   

  • 正則言語の局所多様体とそのカラテオドリ拡張

    新屋良磨

    第38回 記号論理と情報科学 研究集会  2021年08月  -  2021年08月   

  • 正則言語で極限的に近似可能な言語について

    新屋良磨

    正則言語で極限的に近似可能な言語について   (オンライン開催(zoom))  2021年03月  -  2021年03月    日本ソフトウェア科学会 プログラミング論研究会

  • Asymptotic Approximation by Regular Languages

    Ryoma Sin'ya

    Logic, Language, Algebraic system and Related Areas in Computer Science  (オンライン開催(zoom))  2020年02月  -  2020年02月   

 

担当授業科目(学内) 【 表示 / 非表示

  • 2019年12月
    -
    継続中

    基礎AI学C

  • 2019年12月
    -
    継続中

    基礎AI学A

  • 2019年12月
    -
    継続中

    基礎AI学B

  • 2018年04月
    -
    継続中

    数理科学実験

 

学会・委員会等活動 【 表示 / 非表示

  • Computational Logic and Applications

    2020年12月
    -
    継続中

    運営委員

  • 情報処理学会

    2018年04月
    -
    継続中

    幹事

  • 日本ソフトウェア科学会

    2018年04月
    -
    継続中

    組織委員

学外の社会活動(高大・地域連携等) 【 表示 / 非表示

  • セキュリティ・キャンプ全国大会講師

    一般社団法人セキュリティ・キャンプ協議会事務局  セキュリティ・キャンプ全国大会 

    2020年04月
    -
    2020年12月