Reachability problem

Reachability problem --- проблема достижимости (разметки). The reachability problem for Petri nets consists in finding an algorithm for deciding about a Petri net [math]\displaystyle{ N }[/math] and a marking [math]\displaystyle{ n }[/math] of [math]\displaystyle{ N }[/math] whether or not [math]\displaystyle{ m }[/math] is reachable for [math]\displaystyle{ N }[/math].

The reachability problem was for a long time the most-celebrated open problem in the theory of Petri nets. Before a proof for its decidability was found, many equivalent versions for the statement were known. The equivalent versions dealt with various aspects of Petri nets, language theory and vector-additive systems. For example, the reachable problem for Petri nets is decidable iff the empty marking problem for Petri nets is decidable.