  P-time event graphs are discrete event systems able to model cyclic
production systems where tasks need to be performed within given time windows.
Consistency is the property of admitting an infinite execution of such tasks
that does not violate any temporal constraints. In this paper, we solve the
long-standing problem of characterizing the decidability of consistency by
showing that, assuming unary encoding of the initial marking, this property can
be verified in strongly polynomial time. The proof is based on a reduction to
the problem of detecting paths with infinite weight in infinite weighted
digraphs called N-periodic graphs.
