|
Affiliation |
Graduate School of Engineering Science Department of Mathematical Science and Electrical-Electronic-Computer Engineering Mathematical Science Course |
|
Date of Birth |
1988 |
|
Mail Address |
|
SIN'YA Ryoma
|
|
|
Research Interests 【 display / non-display 】
-
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 Areas 【 display / non-display 】
-
Informatics / Theory of informatics
-
Natural Science / Basic mathematics
Thesis for a degree 【 display / non-display 】
Research Achievements 【 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]
Research paper (journal) Single author
-
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]
Research paper (journal) 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.
-
Automata Theory Revised
Ryoma Sin'ya
Computer Software 34 ( 3 ) 3 - 35 2017.09 [Refereed] [Invited]
Research paper (journal) Single author
-
A New Technique for Proving Non-Regularity based on the Measure of a Language
Ryoma Sin'ya
Computer Software 34 ( 1 ) 163 - 179 2017.02 [Refereed] [Invited]
Research paper (journal) Single author
-
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 [Refereed]
Research paper (international conference proceedings) Single author
-
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]
Research paper (international conference proceedings) Domestic Co-author
-
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]
Research paper (international conference proceedings) Single author
-
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]
Research paper (international conference proceedings) 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.
-
Almost Every Simply Typed Lambda-Term Has a Long Beta-Reduction Sequence
Ryoma Sin’ya, Kazuyuki Asada, Naoki Kobayashi, Takeshi Tsukada
Foundations of Software Science and Computation Structures: 20th International Conference, FOSSACS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings 10203 53 - 68 2017.04 [Refereed]
Research paper (international conference proceedings) Domestic Co-author
It is well known that the length of a β-reduction sequence of a simply typed λ-term of order k can be huge; it is as large as k-fold exponential in the size of the λ-term in the worst case. We consider the following relevant question about quantitative properties, instead of the worst case: how many simply typed λ-terms have very long reduction sequences? We provide a partial answer to this question, by showing that asymptotically almost every simply typed λ-term of order k has a reduction sequence as long as (k − 2)-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. The work has been motivated by quantitative analysis of the complexity of higher-order model checking.
＊本業績は入力者が(秋田大学着任前に)東京大学に所属していたときの東大チームでの共同研究成果である。 -
Formal Language Theory: Between Commutativity and Non-Commutativity
Sin'ya Ryoma
Bulletin of the Japan Society for Industrial and Applied Mathematics ( The Japan Society for Industrial and Applied Mathematics ) 31 ( 4 ) 15 - 22 2021.12
◆Original paper【 display / non-display 】
◆International conference proceedings【 display / non-display 】
◆Other【 display / non-display 】
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 】
-
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
-
Asymptotic Approximation by Regular Languages
Ryoma Sin'ya
Logic, Language, Algebraic system and Related Areas in Computer Science (オンライン開催(zoom)) 2020.02 - 2020.02
Academic Activity 【 display / non-display 】
-
2020.12-Now
Steering Committee
-
2018.04-Now
-
2018.04-Now