SIN'YA Ryoma

写真a

Affiliation

Graduate School of Engineering Science  Department of Mathematical Science and Electrical-Electronic-Computer Engineering  Mathematical Science Course 

Date of Birth

1988

Mail Address

E-mail address

Research Fields, Keywords

Formal Language Theory, Automata Theory

Graduating School 【 display / non-display

  • 2007.04
    -
    2011.03

    University of the Ryukyus     The Department of Information Engineering   Graduated

Graduate School 【 display / non-display

  • 2011.04
    -
    2016.03

    Tokyo Institute of Technology    Department of Mathematical and Computing Sciences  Doctor's Course  Completed

Studying abroad experiences 【 display / non-display

  • 2015.10
    -
    2016.10

    Télécom ParisTech   Visiting Ph.D. student

Degree 【 display / non-display

  • Tokyo Institute of Technology -  Doctor (Science)

Campus Career 【 display / non-display

  • 2021.04
    -
    Now

    Akita University   Graduate School of Engineering Science   Department of Mathematical Science and Electrical-Electronic-Computer Engineering   Mathematical Science Course   Assistant Professor  

  • 2017.11
    -
    2021.03

    Akita University   Graduate School of Engineering Science   Department of Mathematical Science and Electrical-Electronic-Computer Engineering   Mathematical Science Course   Specially-appointed Assistant Professor  

External Career 【 display / non-display

  • 2016.04
    -
    2017.10

    The University of Tokyo   Graduate School of Information Science and Technology   Researcher  

Research Field (grants-in-aid-for-scientific-research classification) 【 display / non-display

  • Theory of informatics

  • Foundations of mathematics/Applied mathematics

 

Published Papers 【 display / non-display

  • 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  [Refereed]

    Single author

    DOI

  • 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  [Refereed]

    Domestic Co-author

    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  [Refereed]

    Single author

    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  [Refereed]  [Invited]

    Domestic Co-author

    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  [Refereed]

    Domestic Co-author

    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.

display all >>

Academic Awards Received 【 display / non-display

  • Yamauchi Award, the 57th Programming Symposium, IPSJ

    2017.01    

    Winner: Ryoma Sin'ya

Grant-in-Aid for Scientific Research 【 display / non-display

  • Grant-in-Aid for Early-Career Scientists

    Project Year: 2019.04  -  2023.03 

Presentations 【 display / non-display

  • Asymptotic Approximation by Regular Languages

    Ryoma Sin'ya

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