joint work with Jakub Różycki

Speaker(s)

Piotr Hofman

Affiliation

Uniwersytet Warszawski

Date

Jan. 29, 2020, 2:15 p.m.

Room

room 5050

Title in Polish

Generalized linear equations with unordered data

Seminar

Seminar Automata Theory

---

Consider a Petri net in which every token carries a k-element set of data, and whenever we fire a transition
then data from consumed and produced tokens are compared for equality and disequality. Such an extension
of Petri Nets allows more precise modeling than normal Petri Nets. Of course, comparing to Patri nets the analysis
of data nets is harder and natural problems become undecidable, but not all of them. In this work, we prove that so-called
integer reachability, useful as a witness of nonreachability in standard sens, is in NEexpTime.
The case when k=1 was considered in the paper published at LICS 2017.
During the talk, I will focus on the cases when k=1 and k=2, to illustrate developed techniques.

---