Please use this identifier to cite or link to this item: https://doi.org/10.1007/BF03037291
Title: P transducers
Authors: Ciobanu, G.
Pǎun, G.
Ştefǎnescu, G. 
Keywords: Chomsky hierarchy
Membrane computing
Transducer
Turing machine
Issue Date: 2006
Source: Ciobanu, G.,Pǎun, G.,Ştefǎnescu, G. (2006). P transducers. New Generation Computing 24 (1) : 1-28. ScholarBank@NUS Repository. https://doi.org/10.1007/BF03037291
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.
Source Title: New Generation Computing
URI: http://scholarbank.nus.edu.sg/handle/10635/39321
ISSN: 02883635
DOI: 10.1007/BF03037291
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

8
checked on Dec 5, 2017

Page view(s)

81
checked on Dec 8, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.