Place/Transition Nets with Debit Arcs
Abstract
We add an extension called debit arcs to traditional place/transition 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 token/antitoken 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 place/transition 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, Place/transition nets, Automata theory, Formal languages, Parallel computation model, Colored nets, High-level nets.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1990
- Accession Number
- ADA222724
Entities
People
- P. D. Stotts
- Parke Godfrey
Organizations
- University of Maryland