Affiliations: Sistemas Informáticos y
Computación, Facultad de Ciencias Matemáticas,
Universidad Complutense de Madrid, Spain.
fernandorosa,defrutos@sip.ucm.es
Note: [] Address for correspondence: Facultad de Ciencias
Matemáticas. Plaza de las Ciencias, 3-28040 Madrid, Spain
Abstract: We study the relationship between name creation and replication in a
setting of infinitestate communicating automata. By name creation we mean the
capacity of dynamically producing pure names, with no relation between them
other than equality or inequality. By replication we understand the ability of
systems of creating new parallel identical threads, that can synchronize with
each other. We have developed our study in the framework of Petri nets, by
considering several extensions of P/T nets. In particular, we prove that in
this setting name creation and replication are equivalent, but only when a
garbage collection mechanism is added for idle threads. However, when
simultaneously considering both extensions the obtained model is, a bit
surprisingly, Turing complete and therefore, more expressive than when
considered separately.
Keywords: Petri nets, pure names, infinite state systems, decidability, multithreading, security, choreography
