Navigation

Contact

Project ARS

Project ARS (Algorithms for Reengineering and Synthesis) 2014-2018, funded by DFG (Deutsche Forschungsgemeinschaft, Be 1267/15-1)

People

Objectives

The scope of ARS is in Petri net synthesis and Petri net reengineering.

Petri net synthesis is the problem of finding a Petri net that solves a given labelled transition system. In contrast to this, in Petri net reengineering, a Petri net is given and a 'nice' Petri net is asked for. This 'nice' Petri net should have the same behaviour as the input, but also satisfying some other e.g. structural properties.

In ARS, the relationship between special classes of labelled transition systems and Petri nets should be examined. For example, this was already done with marked graph Petri nets (see e.g. [BD14a], [BD14e] and [BD15a]).

Another topic concerns the distributability of a given labelled transition systems. Here, locations are assigned to the labels and a Petri net solution must be distributed according to these locations.

Finally, ARS also deals with complexity analysis of algorithms in the above context and implementations should be produced as part of the toolset APT.

Publications

  • E. Best and R. R. Devillers, "Pre-synthesis of Petri nets based on prime cycles and distance paths," Sci. Comput. Program., vol. 157, pp. 41-55, 2018.
    @article{DBLP:journals/scp/BestD18,
      author = {Eike Best and Raymond R. Devillers},
      title = {Pre-synthesis of Petri nets based on prime cycles and distance paths},
      journal = {Sci. Comput. Program.},
      volume = {157},
      pages = {41--55},
      year = {2018},
      url = {https://doi.org/10.1016/j.scico.2017.07.005},
      doi = {10.1016/j.scico.2017.07.005},
      timestamp = {Wed, 18 Apr 2018 15:42:42 +0200},
      biburl = {https://dblp.org/rec/bib/journals/scp/BestD18},
      bibsource = {dblp computer science bibliography, https://dblp.org} }
  • E. Best, R. R. Devillers, U. Schlachter, and H. Wimmel, "Simultaneous Petri Net Synthesis," Sci. Ann. Comp. Sci., vol. 28, iss. 2, pp. 199-236, 2018.
    @article{DBLP:journals/cuza/BestDSW18,
      author = {Eike Best and Raymond R. Devillers and Uli Schlachter and Harro Wimmel},
      title = {Simultaneous Petri Net Synthesis},
      journal = {Sci. Ann. Comp. Sci.},
      volume = {28},
      number = {2},
      pages = {199--236},
      year = {2018},
      url = {http://www.info.uaic.ro/bin/Annals/Article?v=XXVIII2\&a=2},
      timestamp = {Tue, 25 Sep 2018 12:12:55 +0200},
      biburl = {https://dblp.org/rec/bib/journals/cuza/BestDSW18},
      bibsource = {dblp computer science bibliography, https://dblp.org} }
  • E. Best, R. R. Devillers, and U. Schlachter, "Bounded choice-free Petri net synthesis: algorithmic issues," Acta Inf., vol. 55, iss. 7, pp. 575-611, 2018.
    @article{DBLP:journals/acta/BestDS18,
      author = {Eike Best and Raymond R. Devillers and Uli Schlachter},
      title = {Bounded choice-free Petri net synthesis: algorithmic issues},
      journal = {Acta Inf.},
      volume = {55},
      number = {7},
      pages = {575--611},
      year = {2018},
      url = {https://doi.org/10.1007/s00236-017-0310-9},
      doi = {10.1007/s00236-017-0310-9},
      timestamp = {Thu, 11 Oct 2018 16:06:29 +0200},
      biburl = {https://dblp.org/rec/bib/journals/acta/BestDS18},
      bibsource = {dblp computer science bibliography, https://dblp.org} }
  • [inproceedings] bibtex | Go to document Go to document
    U. Schlachter and H. Wimmel, "A Geometric Characterisation of Event/State Separation," in Proc. Application and Theory of Petri Nets and Concurrency - 39th International Conference, PETRI NETS 2018, Bratislava, Slovakia, June 24-29, 2018, Proceedings, 2018, pp. 99-116.
    @inproceedings{DBLP:conf/apn/SchlachterW18,
      author = {Uli Schlachter and Harro Wimmel},
      title = {A Geometric Characterisation of Event/State Separation},
      booktitle = {Application and Theory of Petri Nets and Concurrency - 39th International Conference, {PETRI} {NETS} 2018, Bratislava, Slovakia, June 24-29, 2018, Proceedings},
      pages = {99--116},
      year = {2018},
      url = {https://doi.org/10.1007/978-3-319-91268-4\_6},
      doi = {10.1007/978-3-319-91268-4\_6},
      }
  • [inproceedings] bibtex | Go to document Go to document
    R. R. Devillers and U. Schlachter, "Factorisation of Petri Net Solvable Transition Systems," in Proc. Application and Theory of Petri Nets and Concurrency - 39th International Conference, PETRI NETS 2018, Bratislava, Slovakia, June 24-29, 2018, Proceedings, 2018, pp. 82-98.
    @inproceedings{DBLP:conf/apn/DevillersS18,
      author = {Raymond R. Devillers and Uli Schlachter},
      title = {Factorisation of Petri Net Solvable Transition Systems},
      booktitle = {Application and Theory of Petri Nets and Concurrency - 39th International Conference, {PETRI} {NETS} 2018, Bratislava, Slovakia, June 24-29, 2018, Proceedings},
      pages = {82--98},
      year = {2018},
      url = {https://doi.org/10.1007/978-3-319-91268-4\_5},
      doi = {10.1007/978-3-319-91268-4\_5},
      }
  • [inproceedings] bibtex | Go to document Go to document
    U. Schlachter, "Over-Approximative Petri Net Synthesis for Restricted Subclasses of Nets," in Proc. Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings, 2018, pp. 296-307.
    @inproceedings{DBLP:conf/lata/Schlachter18,
      author = {Uli Schlachter},
      title = {Over-Approximative Petri Net Synthesis for Restricted Subclasses of Nets},
      booktitle = {Language and Automata Theory and Applications - 12th International Conference, {LATA} 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings},
      pages = {296--307},
      year = {2018},
      url = {https://doi.org/10.1007/978-3-319-77313-1\_23},
      doi = {10.1007/978-3-319-77313-1\_23},
      }
  • [inproceedings] bibtex | Go to document Go to document
    U. Schlachter and H. Wimmel, "K-Bounded Petri Net Synthesis from Modal Transition Systems," in Proc. 28th International Conference on Concurrency Theory, CONCUR 2017, September 5-8, 2017, Berlin, Germany, 2017, p. 6:1-6:15.
    @inproceedings{DBLP:conf/concur/SchlachterW17,
      author = {Uli Schlachter and Harro Wimmel},
      title = {k-Bounded Petri Net Synthesis from Modal Transition Systems},
      booktitle = {28th International Conference on Concurrency Theory, {CONCUR} 2017, September 5-8, 2017, Berlin, Germany},
      pages = {6:1--6:15},
      year = {2017},
      url = {https://doi.org/10.4230/LIPIcs.CONCUR.2017.6},
      doi = {10.4230/LIPIcs.CONCUR.2017.6},
      }
  • [inproceedings] bibtex | Go to document Go to document
    U. Schlachter and V. Spreckels, "Synthesis of Labelled Transition Systems into Equal-Conflict Petri Nets," in Proc. ATAED 2017, 2017, pp. 131-138.
    @inproceedings{ataedWithValentin,
      author = {Uli Schlachter and Valentin Spreckels},
      title = {Synthesis of Labelled Transition Systems into Equal-Conflict Petri Nets},
      booktitle = {ATAED 2017},
      pages = {131--138},
      year = {2017},
      url = {http://ceur-ws.org/Vol-1847/},
      }
  • E. Badouel and U. Schlachter, "Incremental Process Discovery using Petri Net Synthesis," Fundamenta Informaticae, vol. 154, iss. 1-4, pp. 1-13, 2017.
    @article{DBLP:journals/fuin/BadouelS17,
      author = {Eric Badouel and Uli Schlachter},
      title = {Incremental Process Discovery using Petri Net Synthesis},
      journal = {Fundamenta Informaticae},
      volume = {154},
      number = {1-4},
      pages = {1--13},
      year = {2017},
      url = {https://doi.org/10.3233/FI-2017-1548},
      doi = {10.3233/FI-2017-1548},
      }
  • K. Barylska, E. Best, U. Schlachter, and V. Spreckels, "Properties of Plain, Pure, and Safe Petri Nets," T. Petri Nets and Other Models of Concurrency, vol. 12, pp. 1-18, 2017.
    @article{DBLP:journals/topnoc/BarylskaBSS17,
      author = {Kamila Barylska and Eike Best and Uli Schlachter and Valentin Spreckels},
      title = {Properties of Plain, Pure, and Safe Petri Nets},
      journal = {T. Petri Nets and Other Models of Concurrency},
      volume = {12},
      pages = {1--18},
      year = {2017},
      url = {https://doi.org/10.1007/978-3-662-55862-1_1},
      doi = {10.1007/978-3-662-55862-1_1},
      }
  • [inproceedings] bibtex | Go to document Go to document
    E. Best, R. R. Devillers, and U. Schlachter, "A Graph-Theoretical Characterisation of State Separation," in Proc. SOFSEM 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings, 2017, pp. 163-175.
    @inproceedings{DBLP:conf/sofsem/BestDS17,
      author = {Eike Best and Raymond R. Devillers and Uli Schlachter},
      title = {A Graph-Theoretical Characterisation of State Separation},
      booktitle = {{SOFSEM} 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings},
      pages = {163--175},
      year = {2017},
      url = {http://dx.doi.org/10.1007/978-3-319-51963-0_13},
      doi = {10.1007/978-3-319-51963-0_13},
      timestamp = {Wed, 11 Jan 2017 11:03:34 +0100},
      editor = {Bernhard Steffen and Christel Baier and Mark van den Brand and Johann Eder and Mike Hinchey and Tiziana Margaria},
      series = {Lecture Notes in Computer Science},
      volume = {10139},
      publisher = {Springer},
      biburl = {http://dblp.dagstuhl.de/rec/bib/conf/sofsem/BestDS17},
      bibsource = {dblp computer science bibliography, http://dblp.org} }
  • [inproceedings] bibtex | Go to document Go to document
    E. Best and H. Wimmel, "Plain, Bounded, Reversible, Persistent, and k-marked Petri Nets Have Marked Graph Reachability Graphs," in Proc. Reachability Problems - 10th International Workshop, RP 2016, Aalborg, Denmark, September 19-21, 2016, Proceedings, 2016, pp. 51-62.
    @inproceedings{DBLP:conf/rp/BestW16,
      author = {Eike Best and Harro Wimmel},
      title = {Plain, Bounded, Reversible, Persistent, and k-marked Petri Nets Have Marked Graph Reachability Graphs},
      booktitle = {Reachability Problems - 10th International Workshop, {RP} 2016, Aalborg, Denmark, September 19-21, 2016, Proceedings},
      pages = {51--62},
      year = {2016},
      url = {https://doi.org/10.1007/978-3-319-45994-3\_4},
      doi = {10.1007/978-3-319-45994-3\_4},
      timestamp = {Fri, 26 May 2017 00:49:43 +0200},
      biburl = {https://dblp.org/rec/bib/conf/rp/BestW16},
      bibsource = {dblp computer science bibliography, https://dblp.org} }
  • [inproceedings] bibtex | Go to document Go to document
    E. Best and R. R. Devillers, "The Power of Prime Cycles," in Proc. Application and Theory of Petri Nets and Concurrency - 37th International Conference, PETRI NETS 2016, Toru\'n, Poland, June 19-24, 2016. Proceedings, 2016, pp. 59-78.
    @inproceedings{DBLP:conf/apn/BestD16,
      author = {Eike Best and Raymond R. Devillers},
      title = {The Power of Prime Cycles},
      booktitle = {Application and Theory of Petri Nets and Concurrency - 37th International Conference, {PETRI} {NETS} 2016, Toru{\'{n}},
      Poland, June 19-24, 2016. Proceedings},
      pages = {59--78},
      year = {2016},
      url = {https://doi.org/10.1007/978-3-319-39086-4\_5},
      doi = {10.1007/978-3-319-39086-4\_5},
      timestamp = {Fri, 26 May 2017 00:48:46 +0200},
      biburl = {https://dblp.org/rec/bib/conf/apn/BestD16},
      bibsource = {dblp computer science bibliography, https://dblp.org} }
  • [inproceedings] bibtex | Go to document Go to document
    U. Schlachter, "Bounded Petri Net Synthesis from Modal Transition Systems is Undecidable," in Proc. 27th International Conference on Concurrency Theory, CONCUR 2016, August 23-26, 2016, Québec City, Canada, 2016, p. 15:1-15:14.
    @inproceedings{DBLP:conf/concur/Schlachter16,
      author = {Uli Schlachter},
      title = {Bounded Petri Net Synthesis from Modal Transition Systems is Undecidable},
      booktitle = {27th International Conference on Concurrency Theory, {CONCUR} 2016, August 23-26, 2016, Qu{\'{e}}bec City, Canada},
      pages = {15:1--15:14},
      year = {2016},
      url = {http://dx.doi.org/10.4230/LIPIcs.CONCUR.2016.15},
      doi = {10.4230/LIPIcs.CONCUR.2016.15},
      timestamp = {Tue, 30 Aug 2016 15:28:48 +0200},
      editor = {Jos{\'{e}}e Desharnais and Radha Jagadeesan},
      series = {LIPIcs},
      volume = {59},
      publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
      isbn = {978-3-95977-017-0},
      timestamp = {Tue, 30 Aug 2016 15:28:27 +0200},
      biburl = {http://dblp.uni-trier.de/rec/bib/conf/concur/Schlachter16},
      bibsource = {dblp computer science bibliography, http://dblp.org} }
  • [inproceedings] bibtex | Go to document Go to document
    E. Best, E. Erofeev, U. Schlachter, and H. Wimmel, "Characterising Petri Net Solvable Binary Words," in Proc. Application and Theory of Petri Nets and Concurrency - 37th International Conference, PETRI NETS 2016, Toruń, Poland, June 19-24, 2016. Proceedings, 2016, pp. 39-58.
    @inproceedings{DBLP:conf/apn/BestESW16,
      author = {Eike Best and Evgeny Erofeev and Uli Schlachter and Harro Wimmel},
      title = {Characterising Petri Net Solvable Binary Words},
      booktitle = {Application and Theory of Petri Nets and Concurrency - 37th International Conference, {PETRI} {NETS} 2016, Toruń, Poland, June 19-24, 2016. Proceedings},
      pages = {39--58},
      year = {2016},
      url = {http://dx.doi.org/10.1007/978-3-319-39086-4_4},
      doi = {10.1007/978-3-319-39086-4_4},
      timestamp = {Thu, 09 Jun 2016 15:20:16 +0200},
      biburl = {http://dblp.dagstuhl.de/rec/bib/conf/apn/BestESW16},
      bibsource = {dblp computer science bibliography, http://dblp.org} }
  • [inproceedings] bibtex | Go to document Go to document
    U. Schlachter, "Petri Net Synthesis for Restricted Classes of Nets," in Proc. Application and Theory of Petri Nets and Concurrency - 37th International Conference, PETRI NETS 2016, Toruń, Poland, June 19-24, 2016. Proceedings, 2016, pp. 79-97.
    @inproceedings{DBLP:conf/apn/Schlachter16,
      author = {Uli Schlachter},
      title = {Petri Net Synthesis for Restricted Classes of Nets},
      booktitle = {Application and Theory of Petri Nets and Concurrency - 37th International Conference, {PETRI} {NETS} 2016, Toruń, Poland, June 19-24, 2016. Proceedings},
      pages = {79--97},
      year = {2016},
      url = {http://dx.doi.org/10.1007/978-3-319-39086-4_6},
      doi = {10.1007/978-3-319-39086-4_6},
      timestamp = {Thu, 09 Jun 2016 15:20:16 +0200},
      biburl = {http://dblp.dagstuhl.de/rec/bib/conf/apn/Schlachter16},
      bibsource = {dblp computer science bibliography, http://dblp.org} }
  • [inproceedings] bibtex
    K. Barylska, E. Best, E. Erofeev, &. Mikulski, and M. Piątkowski, "Conditions for Petri Net Solvable Binary Words," in Proc. ToPNoC (Transactions on Petri Nets and other Models of Concurrency), 2016.
    @inproceedings{BBEMP16,
      author = {Kamila Barylska and Eike Best and Evgeny Erofeev and Łukasz Mikulski and Marcin Piątkowski},
      title = {Conditions for Petri Net Solvable Binary Words},
      booktitle = {ToPNoC (Transactions on Petri Nets and other Models of Concurrency)},
      note = {To appear},
      editor = {Jetty Kleijn and Jörg Desel},
      publisher = {Springer-Verlag},
      year = {2016},
      }
  • E. Best and J. Esparza, "Existence of Home States in Petri Nets is Decidable," Information Processing Letters, 2016.
    @article{BE16,
      author = {Eike Best and Javier Esparza},
      title = {Existence of Home States in Petri Nets is Decidable},
      journal = {Information Processing Letters},
      year = {2016},
      url = {http://www.sciencedirect.com/science/article/pii/S0020019016000132},
      doi = {10.1016/j.ipl.2016.01.011},
      }
  • [techreport] bibtex
    E. Best, E. Erofeev, U. Schlachter, and H. Wimmel, "Characterising Petri Net Solvable Binary Words," Universität Oldenburg, Berichte aus dem Department für Informatik 01/16, 2016.
    @techreport{RoteReihePNBinaryWords2016,
      author = {Eike Best and Evgeny Erofeev and Uli Schlachter and Harro Wimmel},
      title = {Characterising Petri Net Solvable Binary Words},
      number = {01/16},
      type = {Berichte aus dem Department f{\"u}r Informatik},
      issn = {1867-9218},
      year = {2016},
      institution = {Universit{\"a}t Oldenburg},
      pages = {1--20},
      }
  • [inproceedings] bibtex | Go to document Go to document
    E. Best and U. Schlachter, "Analysis of Petri Nets and Transition Systems," in Proc. 8th Interaction and Concurrency Experience, ICE 2015, Grenoble, France, 4-5th June 2015., 2015, pp. 53-67.
    @inproceedings{DBLP:journals/corr/BestS15,
      author = {Eike Best and Uli Schlachter},
      title = {Analysis of Petri Nets and Transition Systems},
      booktitle = {8th Interaction and Concurrency Experience, {ICE} 2015, Grenoble, France, 4-5th June 2015.},
      editor = {Sophia Knight and Ivan Lanese and Alberto Lluch{-}Lafuente and Hugo Torres Vieira},
      series = {{EPTCS}},
      volume = {189},
      pages = {53--67},
      year = {2015},
      url = {http://dx.doi.org/10.4204/EPTCS.189.6},
      doi = {10.4204/EPTCS.189.6},
      }
Webmqmaster23 (marqubcoje5.grawvyfeunder@uol.dey6) (Changed: 2020-06-25)