Conformance checking aims to quantify process compliance by comparing an event log and a reference model. While event logs have traditionally been represented as sequential traces, real-life processes often require partially ordered traces to accurately reflect causal dependencies, concurrency, durations, overlapping, or uncertainty in the observed behavior. Consequently, there is a growing need for algorithms that can directly handle partially ordered input. In conformance checking for partially ordered input, two different paradigms exist. The goal is either to evaluate whether at least one sequential execution order of a partially ordered trace conforms to the model (uncertain semantics). This is useful, e.g., in case of quality issues of the event log, where the main goal is to evaluate whether the observed behavior can be explained by the model. Alternatively, the goal is to evaluate whether all possible execution orders of a partially ordered trace conform to the model, including concurrent executions of unordered events (certain semantics). This is important in use cases where some execution orders may be harmful and guarantees are required, or where concurrency of events is relevant. So far, research has primarily focused on uncertain semantics. To close this gap, in this paper, we introduce a token-based replay conformance checking approach for certain semantics, which evaluates the full behavior defined by a partially ordered trace or event log, and calculates a fitness value in polynomial time. We additionally propose a fast variant that calculates lower and upper fitness bounds in linear time.