For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Computing Abilities of Multi-Head and Finite-State Transducers
Kenichi MORITA Hiroyuki EBI Kazuhiro SUGATA
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1979/07/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automata and Languages
Full Text: PDF(598.9KB)>>
In this paper, multi-head and finite-state transducers are proposed, and their computing abilities of number-theoretic functions are investigated. A multi-head transducer is an automaton which maps a unary input into a unary output using a finite number of input heads. A finite-state transduccer is one with single input head. First, it is shown that a two-way finite-state transducer is strictly more powerful than a one-way finite-state transducer, but a two-way finite-state transducer can be simulated by a two-scan finite-state transducer. As for the multi-head transducer, the following results are derived. The upper bound of increasing degree of functions computed by two-way multi-head transducers varies with the number of input heads. However, a two-way two-head transducer can compute an arbitrarily slowly increasing monotone total recursive function, so that there exists no lower bound of increasing degree of a function computed by it. Although the class of two-way multi-head transducers forms an infinite hierarchy of computing abilities with respect to the number of input heads, it is shown that a one-way multi-head transducer is equivalent to a two-way finite-state transducer provided that the number of input heads is more than one.