Place/Transition Nets with Debit Arcs
MARYLAND UNIV COLLEGE PARK INST FOR ADVANCED COMPUTER STUDIES
Pagination or Media Count:
We add an extension called debit arcs to traditional placetransition nets. A debit arc allows its destination transition to fire whenever desired, but records a debt or antitoken in its source place if a token there is not consumed. A normal token can annihilate with an antitoken, which can be though of as paying off the debt. Two natural rules for tokenantitoken annihilation instantaneous, and delayed are examined and are shown to create two distinct classes of automation in terms of language recognition power. Under instantaneous annihilation, nets with debit arcs are equivalent as a class to Turing machines, and so extend the modeling power of standard placetransition nets, and thus are only a notational convenience. Nets with debit arcs are shown to be a special case of colored nets. Keywords Petri nets, Placetransition nets, Automata theory, Formal languages, Parallel computation model, Colored nets, High-level nets.
- Computer Programming and Software