트랜지션 시스템(Transition System)이란? Reachability Graph란?

 트랜지션 시스템(Transition System)은 프로세스 모델의 한 종류로, 이름에서도 알 수 있 듯이 Transition과 함께 State를 나타내는 것을 목적으로 하는 모델이다. 이 때, state는 페트리 넷의 marking이 될 수도 있고, 현재 enabled된 트랜지션의 목록일 수도, enabled된 트랜지션의 개수일 수도 있다. 즉, state는 사용자가 원하는대로 정의할 수 있는 것이다. 하지만 하나의 state에서 다른 state로 넘어가는 것은 반드시 트랜지션을 통해서만 이루어진다. 

 트랜지션 시스템은 DFG나 페트리 넷이 이벤트 로그에서 시작했던 것과는 다르게 페트리 넷에서 시작한다. (물론, 이벤트 로그에서 시작하여 페트리 넷을 거쳐 트랜지션 시스템이 될 수 있다.) 다음과 같은 예시 페트리 넷이 있다고 하자.

R예시 페트리 넷 PN

Reachability Graph

 여기에서 우리가 트랜지션 시스템의 state를 marking이라고 정했다고 하자. marking이 무엇인지 모르겠다면 다음 포스팅을 참고하도록 한다.

2019/06/20 - [Theory/Process Model] - 페트리 넷(Petri Net)이란?

페트리 넷(Petri Net)이란?

 우선, 현재의 Marking은 [x, r1, r2]이다. 여기서 만약 rg1 트랜지션이 fire된다면 x, r1의 토큰이 소모되고 g1에 하나의 토큰이 생성되어 [g1, r2] 마킹이 될 것이다. 그렇다면 우리는 이를 다음과 같이 표현할 수 있다. 즉, [r1, r2, x] state에서 rg1 트랜지션을 통해 [g1, r2] state가 되는 것이다. 

state는 어떤 형태로 표현하든 상관이 없다.

 [g1, r2] state에서 go1 트랜지션이 fire되면 어떻게 될까? g1의 토큰이 소모되고 o1에 토큰이 만들어져 [r2, o1] 마킹이 될 것이다. 이 트랜지션을 붙이면 다음 그림과 같이 될 것이다.

 

 이런 식으로 모든 reachable marking에 대해서 트랜지션 시스템을 만들어나갈 수 있을 것이고, 그것은 아래 그림과 같다. 이처럼 어떤 페트리 넷에 대해 하나의 initial marking에서 모든 reachable marking을 표현한 transition system을 Reachability Graph라고 한다. 

PN의 Reachability Graph

 Reachability Graph는 마킹을 하나하나 계산하고 세어 봐야 하는 다른 프로세스 모델과는 다르게, Reachable Marking을 한 눈에 볼 수 있다는 강력한 장점을 가진다. 

 이외 Transition System

  이외에도 사용자가 원하는 대로 state를 정의하여 transition system을 만들 수 있다. 같은 페트리 넷 PN에 대해서 state를 enable된 transition의 개수로 정의해 보자. 그렇다면 어떤 transition system이 만들어질까?

 

열심히 그린 state가 enabled transition 개수인 transition system

 다음과 같은 transition system이 만들어질 것이다!

 

 트랜지션 시스템은 그 자체에서 바로 프로세스의 흐름을 파악하기는 비교적 힘들지만, 다른 프로세스 모델들이 나타낼 수 없는 정보를 한 눈에 보여줄 수 있다는 강력한 장점을 가진다. 이러한 장점 때문에 트랜지션 시스템은 많은 process discovery 알고리즘에서 사용되기도 한다. state를 어떻게 정의하느냐에 따라 자신의 입맛대로 프로세스를 표현할 수 있다는 점에서 트랜지션 시스템은 매력적인 프로세스 모델이다!

 

References

1. Wil van der Aalst. Process Mining: Data Science in Action (Second Edition) : Springer, 2016.