IJPAM: Volume 109, No. 3 (2016)

KLEENE'S NORMAL FORM THEOREM
FOR ARITHMETICAL PETRI NETS

Zvi Retchkiman Königsberg
Instituto Politecnico Nacional, CIC
Mineria 17-2, Col. Escandon, Mexico D.F 11800, MEXICO

Abstract. This paper gives a proof of the normal form theorem for arithmetical Petri nets $(APN)$. The normal form theorem was introduced by Kleene for the general recursive computation paradigm in terms of system of equations. $APN$ are inhibitor Petri nets that perform three types of arithmetical operations; increment, decrement and test for zero. The proof is based on the idea of computation tree, where each node of such a tree will tell us how a value needed for the arithmetical operations can be inductively obtained. Then, using arithmetization plus course of value recursion a primitive recursive predicate is defined from which by means of a primitive recursive function the desired characterization for the value of the output function is established.

Received: May 11, 2016

Revised: July 22, 2016

Published: October 1, 2016

AMS Subject Classification: 03D78, 03D60, 03D20, 03D10

Key Words and Phrases: normal form theorem, Petri nets, inhibitor arcs, arithmetical Petri nets, arithmetization, recursive functions, computation tree
Download paper from here.

Bibliography

1
S. Kleene, Introduction to Metamathematics, Noth Holland Publishing Co, Amsterdam, Groningen (1952),

2
J.C. Shepardson and H.E. Sturgis, Computability of recursive functions, Journal of the ACM, 10, No. 2 (1963), 217-255, doi: 10.1145/321160.321170.

3
J.L. Peterson, Petri Net Theory and The Modelling of Systems, Prentice Hall (1981).

4
P. Odifreddi, Recursion Theory, The Theory of Functions and Sets of Natural Numbers, Studies in Logic and the Foundations of Mathematics, Elsevier (1999).

5
M. Davis, R. Sigal and E. Weyuker, Computability, Complexity, and Languages, Fundamentals of Theoretical Computer Science, Academic Press (1983).

6
M. Davis, Computability and Unsolvability, McGraw-Hill (1958).

.



DOI: 10.12732/ijpam.v109i3.3 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2016
Volume: 109
Issue: 3
Pages: 511 - 528


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).