SCIENTIA SINICA Informationis, Volume 47, Issue 6: 696(2017) https://doi.org/10.1360/N112016-00056

An approach to distinguishing the levels of free-labeled $L$-type Petri net languages in the Chomsky hierarchy

• ReceivedNov 9, 2016
• AcceptedDec 21, 2016
• PublishedMar 6, 2017
Share
Rating

Abstract

Petri nets (PNs) and automatic machines are two approaches to modeling discrete event dynamic systems. The relationship between these approaches is important for controlling discrete event dynamic systems. This paper investigates the relationship between these approaches from the formal language point of view, i.e., we introduce an approach to distinguishing the levels of free-labeled $L$-type PN languages in the Chomsky hierarchy. To characterize PNs from the formal language point of view, the concepts of increaser, valid increaser, and linearer are introduced. For a PN with no valid increaser, its PN language is regular. For a PN with a valid increaser with at least two linearers, its PN language is context-sensitive. For a PN in which each valid increaser has only one linearer, assuming only one increaser in the PN, the PN language is context-free. If the PN has more than one increaser, the corresponding PN language is context-sensitive when valid increasers and their linearers can be fired currently or crossed. The language is context-free when the increasers and their linearers are fired alternatively, or an increaser and its linearer are fired sequentially relative to other increasers and their linearers, or when firing occurs after an increaser and before its linearer.

Funded by

• Figure 7

A Petri netwhose valid incrementers and their linearerscan be fired concurrently, in which $M_0=(1,0,0,0,0)$

• Figure 8

A Petri net, three ofwhose valid incrementers and linearers canbe fired concurrently. (a) and (b) are different cases of the Petri net, in which $M_0=(1,0,0,0,0)$

• Figure 9

A Petri net, twoof whose valid incrementers and linearerscan be fired concurrently. (a)$\sim$(c) are different cases of the Petri net, in which $M_0=(1,0,0,0,0,0)$

• Figure 10

Illustrating that two valid incrementers and their linearers can be fired sequentially, intersectively, nestedly and alternatively. (a)$\sim$(e) are different cases of the Petri net, in which $M_0=(1,0,0,0,0,0)$

• Figure 11

An instance ofreachability tree. (a) $M_0=(1,0,0,0)$; (b) reachability tree

• Figure 12

An instance showing information lost in the reachability tree. (a) $M_0$ = (1; 0; 0; 0); (b) reachability tree

• Figure 13

(a) A-type and (b) B-type reachability tree for the Petri net in Figure 12(a)

• Figure 14

(a) A-type and (b) B-type reachability tree for the Petri net in Figure 5

• Figure 15

An Instance shown in reference [8]. (a) $M_0=(1,0,0,0,0,0,0)$; (b) $M_0=(1,0,0,0,0,0,0,0,0,0)$

• Figure 16

A Petri net without transitive vectors and its NMRT tree. (a) $M_0=(1,0,0,0)$; (b) B-type reachability tree; (c) NMRT tree

Citations

• 0

Altmetric

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有