抄録
Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3500000, indirect: 1050000)
We have developed polynomial time algorithms for checking the equivalence of deterministic restricted one-counter transducers, which are deterministic pushdown transducers having just one stack symbol, that accept by empty stack or by final state. We have proved that a subclass of deterministic pushdown automata called Szilard strict deterministic restricted one-counter automata and a subclass of finite state transducers(FST's for short)called strict prefix deterministic FST's are polynomial time identifiable in the limit from positive data. Furthermore, we have improved the method for analyzing songs of the Bengalese finch using an identification algorithm for the class of k-reversible languages, which is a subclass of regular languages.