Petri Nets and Regular Processes

✍ Scribed by Petr Jančar; Javier Esparza; Faron Moller

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 364 KB
• Volume: 59
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1999.1643

✦ Synopsis

We consider the following problems: (a) Given a labelled Petri net and a finite automaton, are they equivalent?; (b) Given a labelled Petri net, is it equivalent to some (unspecified) finite automaton? These questions are studied within the framework of trace and bisimulation equivalences, in both their strong and weak versions. (In the weak version a special { action likened to an =-move in automata theory is considered to be nonobservable.) We demonstrate that (a) is decidable for strong and weak trace equivalence and for strong bisimulation equivalence, but undecidable for weak bisimulation equivalence. On the other hand, we show that (b) is decidable for strong bisimulation equivalence, and undecidable for strong and weak trace equivalence, as well as for weak bisimulation equivalence.

1999 Academic Press

1. Introduction

In the specification and verification of distributed systems, it is typically the case that one considers a specific mathematical model for the description of processes, along with some equivalence relating processes which demonstrate the same semantic