Lower and upper bounds of shortest paths in reachability graphs
type: Item
instance of: scholarly article
title: Lower and upper bounds of shortest paths in reachability graphs
zbMATH Open document ID: 1101.68730
DOI: 10.1155/S0161171204403378
author: Niranjan Chakravarthy
published in: International Journal of Mathematics and Mathematical Sciences
publication date: 2005-05-25T00:00:00Z
full work available at URL: https://eudml.org/doc/52888
review text: Summary: We prove the following property for safe marked graphs, safe conflict-free Petri nets, and live and safe extended free-choice Petri nets. We prove the following three results. If the Petri net is a marked graph, then the length of the shortest path is at most \((|T|-1)\cdot|T|/{2}\). If the Petri net is conflict free, then the length of the shortest path is at most \((|T|+1)\cdot|T|/{2}\). If the petrinet is live and extended free choice, then the length of the shortest path is at most \(|T|\cdot|T+1|\cdot|T+2|/{6}\), where \(T\) is the set of transitions of the net.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 94C15
Mathematics Subject Classification ID: 68Q85
zbMATH DE Number: 2171761
zbMATH Keywords: Petri nets
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2171761