  Mixed-paradigm process models integrate strengths of procedural and
declarative representations like Petri nets and Declare. They are specifically
interesting for process mining because they allow capturing complex behaviour
in a compact way. A key research challenge for the proliferation of
mixed-paradigm models for process mining is the lack of corresponding
conformance checking techniques. In this paper, we address this problem by
devising the first approach that works with intertwined state spaces of
mixed-paradigm models. More specifically, our approach uses an alignment-based
replay to explore the state space and compute trace fitness in a procedural
way. In every state, the declarative constraints are separately updated, such
that violations disable the corresponding activities. Our technique provides
for an efficient replay towards an optimal alignment by respecting all
orthogonal Declare constraints. We have implemented our technique in ProM and
demonstrate its performance in an evaluation with real-world event logs.
