抄録
Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3600000, indirect: 1080000)
We have developed a polynomial-time algorithm for checking the equivalence of deterministic restricted one-counter transducers (DROCT's for short), which are deterministic pushdown transducers having just one stack symbol, that accept by final state with possible epsilon-moves. By extending this technique, we have also developed a polynomial-time algorithm for checking the inclusion of these DROCT's. Then, we have presented a polynomial-time algorithm for learning real-time DROCT's which accept by final state via membership and equivalence queries. Furthermore, we have shown that the regularity of the behavior of some programs for playing games of Daihinmin, which is one of card games, on computers can be extracted by using the EUREKA system which incorporated an identification algorithm of the class of k-reversible languages, which is a subclass of regular languages, for analyzing songs of the Bengalese finch.