Repositorio de producción científica de la Universidad de Sevilla

Generation of Diophantine Sets by Computing P Systems with External Output

 

Advanced Search
 
Opened Access Generation of Diophantine Sets by Computing P Systems with External Output
Cites

Show item statistics
Icon
Export to
Author: Romero Jiménez, Álvaro
Pérez Jiménez, Mario de Jesús
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2002
Published in: Unconventional Models of Computation. Lecture Notes in Computer Science, v.2509
ISBN/ISSN: 978-3-540-44311-7
0302-9743
Document type: Chapter of Book
Abstract: In this paper a variant of P systems with external output designed to compute functions on natural numbers is presented. These P systems are stable under composition and iteration of functions. We prove that every diophantine set can be generated by such P systems; then, the universality of this model can be deduced from the theorem by Matiyasevich, Robinson, Davis and Putnam in which they establish that every recursively enumerable set is a diophantine set.
Size: 238.9Kb
Format: PDF

URI: http://hdl.handle.net/11441/44948

DOI: 10.1007/3-540-45833-6_15

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)