Разрешимость проблемы достижимости для сетей Петри (обзор проблемы)

Дается обзор современного состояния проблемы достижимости в сетях Петри, широко применяемых при разработках систем управления дискретными процессами. Основываясь на идеях Э. Майера [1], приводим полное доказательство разрешимости проблемы достижимости. Рассматриваются также некоторые темы, примыкающие к анализируемой проблеме: разрешимость арифметики Пресбургера, полулинейные множества, графы векторного сложения, графы достижимости и др.