Affiliation 
Graduate School of Engineering Science Department of Mathematical Science and ElectricalElectronicComputer Engineering Mathematical Science Course 
Date of Birth 
1988 
Mail Address 

Research Fields, Keywords 
Formal Language Theory, Automata Theory 
SIN'YA Ryoma


Graduating School 【 display / nondisplay 】

2007.042011.03
University of the Ryukyus The Department of Information Engineering Graduated
Graduate School 【 display / nondisplay 】

2011.042016.03
Tokyo Institute of Technology Department of Mathematical and Computing Sciences Doctor's Course Completed
Studying abroad experiences 【 display / nondisplay 】

2015.102016.10
Télécom ParisTech Visiting Ph.D. student
Degree 【 display / nondisplay 】

Tokyo Institute of Technology  Doctor (Science)
Campus Career 【 display / nondisplay 】

2021.04Now
Akita University Graduate School of Engineering Science Department of Mathematical Science and ElectricalElectronicComputer Engineering Mathematical Science Course Assistant Professor

2017.112021.03
Akita University Graduate School of Engineering Science Department of Mathematical Science and ElectricalElectronicComputer Engineering Mathematical Science Course Speciallyappointed Assistant Professor
External Career 【 display / nondisplay 】

2016.042017.10
The University of Tokyo Graduate School of Information Science and Technology Researcher
Research Field (grantsinaidforscientificresearch classification) 【 display / nondisplay 】

Theory of informatics

Foundations of mathematics/Applied mathematics
Published Papers 【 display / nondisplay 】

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

On averagecase hardness of higherorder model checking
Nakamura Y.
Leibniz International Proceedings in Informatics, LIPIcs ( Leibniz International Proceedings in Informatics, LIPIcs ) 167 2020.06 [Refereed]
Domestic Coauthor

ContextFreeness of WordMIX 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

Almost Every Simply Typed LambdaTerm Has a Long BetaReduction Sequence
Kazuyuki Asada, Naoki Kobayashi, Ryoma Sin'ya, Takeshi Tsukada
Logical Methods in Computer Science 15 ( 1 ) 2019.02 [Refereed] [Invited]
Domestic Coauthor
It is well known that the length of a betareduction sequence of a simply typed lambdaterm of order k can be huge; it is as large as kfold exponential in the size of the lambdaterm in the worst case. We consider the following relevant question about quantitative properties, instead of the worst case: how many simply typed lambdaterms have very long reduction sequences? We provide a partial answer to this question, by showing that asymptotically almost every simply typed lambdaterm of order k has a reduction sequence as long as (k1)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 higherorder model checking.

Linear PseudoPolynomial 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 Coauthor
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 pseudopolynomial time by the dynamic programming algorithm. However, this algorithm has a quadratic pseudopolynomial factor in its complexity because of the maxplus convolution. In this study, we propose a new dynamic programming technique, called heavylight recursive dynamic programming, to obtain algorithms having linear pseudopolynomial 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 polynomialtime approximation schemes. We also consider the ksubtree 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.
Academic Awards Received 【 display / nondisplay 】

Yamauchi Award, the 57th Programming Symposium, IPSJ
2017.01
Winner： Ryoma Sin'ya
GrantinAid for Scientific Research 【 display / nondisplay 】

GrantinAid for EarlyCareer Scientists
Project Year： 2019.04  2023.03
Presentations 【 display / nondisplay 】

Asymptotic Approximation by Regular Languages
Ryoma Sin'ya
Logic, Language, Algebraic system and Related Areas in Computer Science (オンライン開催(zoom)) 2020.02  2020.02