
For FullText 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 MultiHead and FiniteState Transducers
Kenichi MORITA Hiroyuki EBI Kazuhiro SUGATA
Publication
IEICE TRANSACTIONS (19761990)
Vol.E62
No.7
pp.474480 Publication Date: 1979/07/25 Online ISSN:
DOI: Print ISSN: 00000000 Type of Manuscript: PAPER Category: Automata and Languages Keyword:
Full Text: PDF(598.9KB)>>
Summary:
In this paper, multihead and finitestate transducers are proposed, and their computing abilities of numbertheoretic functions are investigated. A multihead transducer is an automaton which maps a unary input into a unary output using a finite number of input heads. A finitestate transduccer is one with single input head. First, it is shown that a twoway finitestate transducer is strictly more powerful than a oneway finitestate transducer, but a twoway finitestate transducer can be simulated by a twoscan finitestate transducer. As for the multihead transducer, the following results are derived. The upper bound of increasing degree of functions computed by twoway multihead transducers varies with the number of input heads. However, a twoway twohead 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 twoway multihead transducers forms an infinite hierarchy of computing abilities with respect to the number of input heads, it is shown that a oneway multihead transducer is equivalent to a twoway finitestate transducer provided that the number of input heads is more than one.

