Paper Info
Title
On the parameterized complexity of the synthesis of Boolean nets with restricted place environments
Abstract
Though constructing a sequential system model may be technically uncomplicated and rather 'straightforward', its result is often cumbersome and difficult to analyze since all possible interleavings of system's actions have to be present. This naturally raises the interest to the possibility of automatic synthesis of models that are able to grasp behavioral parallelism of the system. Boolean Petri nets are a classical formalism that enjoys generic concepts of concurrency, synchronization and conflict, and allows to obtain a concise yet expressive system representation. Let tau be a Boolean type of nets. The problem of tau-synthesis consists in deciding whether a given transition system A is isomorphic to the reachability graph of a Boolean Petri net N of type tau (a tau-net, for short). In case of a positive decision, N should be constructed. Another instance of the synthesis problem takes the dependencies of places into account: A place p of a tau-net depends on a transition t if p can influence t, that is, a marking of p can inhibit the firing of t, or if p can be influenced by t, that is, the firing of t can change a marking of p. The problem tau-synthesis of Boolean nets with restricted dependencies (tau-SOBNWRD) consists in deciding for a given transition system A and natural number d whether there exists a Boolean Petri net N of type tau such that, firstly, the reachability graph of N and A are isomorphic and, secondly, every place p of N depends on at most d transitions. For many Boolean types that allow independence, the (unrestricted) t-synthesis problem is NP-complete, and for all of them tau-SOBNWRD inherits the NP-completeness. In this paper, we enhance our understanding of tau-SOBNWRD from a parameterized point of view: We show for 27 of the 128 thinkable Boolean types that allow independence that tau-SOBNWRD parameterized by d is W[1]-hard, and for 75 of them that the problem is W[2]-hard. (C) 2021 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.tcs.2021.08.014
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
Petri net, Transition system, Synthesis, Parameterized complexity
Journal
890
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Ronny Tredup101.01
Evgeny Erofeev2122.57