4 papers
Asymptotic Approximation by Regular Languages
Ryoma Sin'ya
This paper investigates a new property of formal languages called REG-measurability where REG is the class of regular languages. Intuitively, a language \(L\) is REG-measurable if…
Simple proof of Parikh's theorem a la Takahashi
Ryoma Sin'ya
In this report we describe a simple proof of Parikh's theorem a la Takahashi, based on a decomposition of derivation trees. The idea of decomposition is appeared in her master's th…
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|_…
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…