Name
Abstract | ||
|---|---|---|
A word is called Petri net solvable if it is isomorphic to the reachability graph of an unlabelled Petri net. In this paper, the class of finite, two-letter, Petri net solvable words is studied. A linear time, necessary condition allows for an educated guess at which words are solvable and which are not. A full decision procedure with a time complexity of O(n(2)) can be built based on letter counting. The procedure is fully constructive and can either yield a Petri net solving a given word or determine why this fails. Algorithms solving the same problem based on systems of integer inequalities reflecting the potential Petri net structure are only known to be in O(n(3)). Finally, the decision procedure can be adapted from finite to cyclic words. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-39086-4_4 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Binary words,Labelled transition systems,Petri nets,Synthesis | Integer,Discrete mathematics,Petri net,Constructive,Computer science,Reachability,Stochastic Petri net,Isomorphism,Time complexity,Binary number | Conference |
Volume | ISSN | Citations |
9698 | 0302-9743 | 5 |
PageRank | References | Authors |
0.57 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eike Best | 1 | 93 | 6.86 |
| Evgeny Erofeev | 2 | 12 | 2.57 |
| Uli Schlachter | 3 | 26 | 5.95 |
| Harro Wimmel | 4 | 114 | 11.56 |