# IJPAM: Volume 109, No. 3 (2016)

**KLEENE'S NORMAL FORM THEOREM**

FOR ARITHMETICAL PETRI NETS

FOR ARITHMETICAL PETRI NETS

Zvi Retchkiman Königsberg

Instituto Politecnico Nacional, CIC

Mineria 17-2, Col. Escandon, Mexico D.F 11800, MEXICO

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 . The normal form theorem was introduced by Kleene for the general recursive computation paradigm in terms of system of equations. 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**

International Journal of Pure and Applied Mathematics

**How to cite this paper?****Source:****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.

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