New Generation Computing, 24(2006)1-28
Ohmsha, Ltd. and Springer

P Transducers

Gabriel CIOBANU
Institute of Computer Science, Romanian Academy
Bd. Copou 8, 700505 Iasi, Romania
gabriel@info.uaic.ro
Gheorghe PAUN
Institute of Mathematics of the Romanian Academy
PO Box 1-764, 014700 Bucharest, Romania, and
Department of Computer Science and AI
Sevilla University
Avda Reina Mercedes s/n, 41012 Sevilla, Spain
gpaun@us.es
Gheorghe STEFANESCU
School of Computing, National University of Singapore
10 Kent Ridge Crescent, Singapore 119260, Singapore
gheorghe@comp.nus.edu.sg

Received 2 October 2003
Revised manuscript received 26 November 2004

Abstract

We introduce in this paper four classes of P transducers: arbitrary, initial, isolated arbitrary, isolated and initial. The first two classes are universal, they can compute the same word functions as Turing machines, the latter two are incomparable with finite state sequential transducers, generalized or not. We study the effect of the composition, and show that iteration increases the power of these latter classes, also leading to a new characterization of recursively enumerable languages. The "Sevilla carpet" of a computation is defined for P transducers, giving a representation of the control part for these P transducers.

Keywords:Membrane Computing, Chomsky Hierarchy, Turing Machine, Transducer.

[Back]