Regions of Petri nets with a/sync connections

被引：8

作者：

Kleijn, Jetty ^{[1
]}

Koutny, Maciej ^{[2
]}

Pietkiewicz-Koutny, Marta ^{[2
]}

机构：

[1] Leiden Univ, LIACS, NL-2300 RA Leiden, Netherlands

[2] Newcastle Univ, Sch Comp Sci, Newcastle Upon Tyne NE1 7RU, Tyne & Wear, England

来源：

THEORETICAL COMPUTER SCIENCE | 2012年 / 454卷

基金：

英国工程与自然科学研究理事会;

关键词：

Concurrency; Transition system; Petri net; Theory of regions; Synthesis problem; Place transition net; Step sequence semantics; Synchronous and asynchronous communication; a/sync connection; TRANSITION-SYSTEMS; INHIBITOR ARCS;

D O I：

10.1016/j.tcs.2012.04.016

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Automated synthesis from behavioural specifications, such as transition systems, is an attractive way of constructing correct concurrent systems. In this paper, we investigate the synthesis of Petri nets which use special connections between transitions and places. Along these a/sync connections tokens can be transferred instantaneously between transitions executed in a single step. We show that for Place/Transition nets with a/sync connections the synthesis problem can be treated within the general approach based on regions of step transition systems. We also show that the problem is decidable for finite transition systems, and outline a suitable construction algorithm. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：189 / 198

页数：10

共 28 条

[1] Reo: a channel-based coordination model for component composition [J].

Arbab, F .

MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 2004, 14 (03) :329-366

[2] The synthesis problem for elementary net systems is NP-complete [J].

Badouel, E ;

Bernardinello, L ;

Darondeau, P .

THEORETICAL COMPUTER SCIENCE, 1997, 186 (1-2) :107-134

[3]

Badouel E., 1998, Lectures on Petri Nets I: Basic Models. Advances in Petri Nets, P529

[4]

Bergenthum R, 2008, LECT NOTES COMPUT SC, V5062, P388, DOI 10.1007/978-3-540-68746-7_25

[5] Zero-safe nets: Comparing the collective and individual token approaches [J].

Bruni, R ;

Montanari, U .

INFORMATION AND COMPUTATION, 2000, 156 (1-2) :46-89

[6]

Busi N, 1997, LECT NOTES COMPUT SC, V1243, P151

[7] Genet: a Tool for the Synthesis and Mining of Petri Nets [J].

Carmona, J. ;

Cortadella, J. ;

Kishinevsky, M. .

NINTH INTERNATIONAL CONFERENCE ON APPLICATION OF CONCURRENCY TO SYSTEM DESIGN, PROCEEDINGS, 2009, :181-+

[8]

Chernikova N.V., 1965, USSR Comput. Math. Math. Phys, V5, P228, DOI [10.1016/0041-5553(65)90045-5, DOI 10.1016/0041-5553(65)90045-5]

[9]

CHRISTENSEN S, 1994, LNCS, V815, P159

[10]

Cortadella Jordi., 2002, Logic Synthesis of Asynchronous Controllers and Interfaces

← 1 2 3 →