10 citations · 22 across the 13 of their papers we have counts for
9 papers · 1 filter
Measure-Theoretic Aspects of Star-Free and Group Languages
Ryoma Sin'ya, Takao Yuyama
A language is said to be -measurable, where is a class of languages, if there is an infinite sequence of languages in that ``converges'' to .…
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|_…
An Automata Theoretic Approach to the Zero-One Law for Regular Languages: Algorithmic and Logical Aspects
Ryoma Sin'ya
A zero-one language L is a regular language whose asymptotic probability converges to either zero or one. In this case, we say that L obeys the zero-one law. We prove that a regula…
Zero-One Law for Regular Languages and Semigroups with Zero
Ryoma Sin'ya
A regular language has the zero-one law if its asymptotic density converges to either zero or one. We prove that the class of all zero-one languages is closed under Boolean operati…
Graph Spectral Properties of Deterministic Finite Automata
Ryoma Sin'ya
We prove that a minimal automaton has a minimal adjacency matrix rank and a minimal adjacency matrix nullity using equitable partition (from graph spectra theory) and Nerode partit…
Simultaneous Finite Automata: An Efficient Data-Parallel Model for Regular Expression Matching
Ryoma Sin'ya, Kiminori Matsuzaki, Masataka Sassa
Automata play important roles in wide area of computing and the growth of multicores calls for their efficient parallel implementation. Though it is known in theory that we can per…
Text Compression using Abstract Numeration System on a Regular Language
Ryoma Sin'ya
An abstract numeration system (ANS) is a numeration system that provides a one-to-one correspondence between the natural numbers and a regular language. In this paper, we define an…