10 citations · 22 across the 13 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.FL2018
Note on the Infiniteness and Equivalence Problems for Word-MIX Languages
Ryoma Sin'ya
In this note we provide a (decidable) graph-structural characterisation of the infiniteness of , where $L(w_1, ..., w_k) = \{w \in A^* | |w|_{w_1} = \cdots = |w|_…
cs.DS2018
Linear Pseudo-Polynomial Factor Algorithm for Automaton Constrained Tree Knapsack Problem
Soh Kumabe, Takanori Maehara, Ryoma Sin'ya
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…
cs.LO2018★ 5 cited
Almost Every Simply Typed Lambda-Term Has a Long Beta-Reduction Sequence
Kazuyuki Asada, Naoki Kobayashi, Ryoma Sin'ya +1
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-t…