Computing Abilities of Multi-Head and Finite-State Transducers

Kenichi MORITA  Hiroyuki EBI  Kazuhiro SUGATA  

IEICE TRANSACTIONS (1976-1990)   Vol.E62   No.7   pp.474-480
Publication Date: 1979/07/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automata and Languages

Full Text: PDF(598.9KB)>>
Buy this Article

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.