TUM Logo

Petri Nets

Petri Nets  

Proseminare 2 SWS / 4,0 ECTS (Kursbeschreibung)
Veranstalter: Alexander Malkis
Zeit und Ort:

Mo, 08:00 – 09:45 Uhr, 01.06.011 (Proseminar)
Beginn: 2016-10-17

The lecture is given in english
The slides are available in english

Registration

The registration deadlines are all over. If for some reason a prospective participant failed to register in time, he/she is welcome to drop an e-mail to the instructor. He/she will have to work quickly to catch up.

Contents

A Petri net (aka Vector Addition System) is a simple computation model, mostly used for modeling multithreading and concurrency in general. Simplifying, a Petri net is roughly equivalent to a nondeterministic program of the form

WHILE true DO
   Chunk 1;
[] Chunk 2;
   ...
[] Chunk n;
END WHILE

where each chunk is a sequence of decrement and increment commands on variables ranging over natural numbers, and where an attempt to decrement below zero blocks.
Petri nets are simpler than Turing machines or RAMs. Reachability of a marking (which is a proper term for "state" or "configuration" in the context of Petri nets) from another one is decidable for Petri nets, while reachability of a state from another one is undecidable in more powerful systems. We ask: if a marking is reachable from another one, how large can the graph distance between them get at worst? This proseminar is devoted to this question.

Previous Knowledge/Skills Expected

  • Ability to quickly obtain necessary background knowledge independently.
  • Linear algebra.
  • Helpful: discrete mathematics, complexity theory, primitively recursive functions.

Objective

Obtain the best possible answer for the question: if a marking is reachable from another one, how large can the graph distance between them get at worst (as a function of different quantities such as the number of places, number of transitions, the Manhattan distance between the markings, etc.)?

Teaching and Learning Method

The work shall be accomplished in groups of typically two participants per topic. (One and three are exceptions but possible.) Each group shall submit one report, one set of slides, and give one or two presentations. The report and the presentation(s) are strictly compulsory: their absence means a failure. All the written work shall be done in (variants of) LaTeX, possibly using (variants of) bibtex. Using more modern XeLaTeX, LuaLaTex, and/or Biber+Biblatex is welcome. We fix a common notation for all the reports and presentations. The student code of conduct must be observed.
In addition, each participant shall review one report in a double-blind way.
In presentations, each participants of each group shall be allocated a total of at least 20 minutes. The upper bound depends on the topic and on the distribution of work within a group.
Attending all talks and active discussion is compulsory.
Every action or its absence is influencing the grade, including complying with the schedule.
The seminar language is English.

Schedule

  • ≤ 31 July: each group one obtains a topic; each group obtains its presentation date.
  • 15 August: cancellation deadline, i.e., if a student decides not to participate, he or she is kindly asked to cancel by then. If not canceled, informally report on progress.
  • ≤ 31 August: Second informal report on progress.
  • ≤ 6 weeks before the first presentation of a group: submit the report and the slides in (source and (PDF or Postscript)) without the authors' names on the documents,
  • at an arbitrary time point each participant obtains one report for a double-blind review, which he or she has to accomplish within 2 weeks.
  • ≤ 27 days (= 4 weeks - 1 day) before the first presentation of a group: obtain feedback on one's own report. Since the feedback is done by the other participants, the timely presence of the feedback or its quality are not guaranteed.
  • ≤ 2 weeks before the first presentation of a group: submit the final versions of the group's report and slides with the author's names. The contribution of each participant to the report shall be clearly stated.
  • directly after the presentation: obtain feedback from the instructor on the talk and on the slides.
  • ≤ 1 week after the last presentation of a group: obtain feedback from the instructor on the report.
  • ≥ 1 week after the last presentation of a group: grade goes formally to TUMonline.

Talk timetable:

The complexity of the finite containment problem for Perti nets (canceled) 17.10.2016
(canceled) 24.10.2016
The complexity of the word problems for commutative semigroups and polynomial ideals (topic taken) 31.10.2016
(continuation, time slot taken) 07.11.2016
Petri nets and large finite sets 14.11.2016
(continuation) 21.11.2016
Presburger vector addition systems (topic taken) 28.11.2016
(continuation, time slot taken) 05.12.2016

Scientific Material

Choice of papers:

  1. E. W. Mayr, A. R. Meyer: The complexity of the finite containment problem for Petri nets. Journal of the ACM, 1981.
  2. E. W. Mayr, A. R. Meyer: The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics, 1982.
  3. K. McAloon: Petri nets and large finite sets. Theoretical Computer Science, 1984.
  4. J. Leroux: Presburger Vector Addition Systems. Logic in Computer Science, 2013.

On [PDF|Xe|Lua]LaTeX