Pushdown変換器の制約に対応するPushdown Transduction

概要

論文の詳細を見る
Computer programs can be considered as devices that convert input strings into output strings. One of the most simple model for programs would be the sequential machine, and, as more generalized machine, there would be G. S. M^<4)> (generalized sequential machine), N. D. M^<3)> (nondeterministic sequential machine), the pushdown transducer^<4)> and so on. In this paper, the pushdown transduction associated pushdown transducers (with accepting states) are studied. Various restrictions on pushdown transducers for input-output strings are defined, and characterizing of pushdown transductions associated with each restriction are investigated. Our restrictions on pushdwon transducer are for both input and output that a string should be a single character and that a string should not be a empty-symbol. So 15 restricted classes of pushdown transductions are defined. One consequence is that, for transduction classes with each restriction, characteristics appear in string-length relation of homomorphism images (which construct the transduction) and in whether the homomorphisms are ε-free or not. The other is that many (15) transduction classes defined by restrictions are reduced to less (9) classes each with the same characteristics.
北海道情報大学の論文