전 State based region theory 포스팅에서 우리는 transition system이 Elemenatry Transition System이라는 가정을 했다.
2019/07/30 - [Theory/Process Discovery] - State Based Region Theory란?
State Based Region Theory란?
이 포스팅을 미루고 미뤘던 이유는 지금 연구실에서 내가 하고 있는 것이기 때문이다. 집에서까지 이 친구를 마주치고 싶지 않았다. 워라밸 소중해 우리는 이벤트 로그를 transition system으로 바꿀 수 있다. 이..
process-mining.tistory.com
이번 포스팅에서는 이 Elementary Transition System이 무엇인지에 대해 알아보도록 하겠다.
Elementary Transition System의 조건
우선 정의를 살펴보자.
이 조건들에 대해 하나하나 살펴보도록 하겠다. (순서는 A1 == 1, A2 == 2 순으로 진행하겠다.)
1. Self-loop를 가지지 않는다.
Transition system이 self-loop, 즉, 하나의 state에서 나가서 그 state로 다시 되돌아오는 event가 없어야한다.
2. 서로 다른 두 state를 연결하는 event는 한 개이다.
두 개의 state에 대해 이들을 연결하는 event는 오직 하나이다.
3. 모든 이벤트가 일어난다.
이벤트 셋에 있는 모든 이벤트들은 트랜지션 시스템 안에서 일어나야 한다.
4. 모든 state는 initial state로부터 reachable하다.
TS 내의 모든 state들은 initial state로부터 reachable해야 한다.
5. State-separation Property
State-separation property란, 모든 state의 pair에 대해서 두 개의 state들이 서로 공유하지 않는 다른 region을 최소한 한 개는 가진다는 것이다. 예를 들어, 다음과 같은 transition system이 있다고 하자.
이 Transition system에 대해 모든 state의 pair를 구하면 다음과 같다.
그리고 Transition system의 region을 모두 구하면 다음과 같다. (region이 무엇인지 궁금하다면 위의 state based region theory 관련 포스팅을 참고하도록 한다.)
이제 각 state pair에 대해 각 state가 속해 있는 region을 살펴 보고, 공유하지 않는 region이 있는지 확인한다. 예를 들어, {i, s1}은 i는 r1과 r3, r5에 속하고 s1은 r1, r4, r5에 속하기 떄문에 공유하지 않는 r3와 r4를 가지므로 조건을 만족한다. 하나의 예를 더 들어 보면, {i, s2}는 i는 r1과 r3, r5에 속하고 s2는 r2, r4, r5에 속하기 때문에 공유하지 않는 r1, r3, r2, r4를 가지므로 조건을 만족한다. 이렇게 모든 state pair에 대해 조건을 만족하는지 확인한다.
6. Forward closure property
Forward closure property란, 각 이벤트에 대해서 그 이벤트의 모든 pre-region에 공통적으로 속해 있는 state가 그 이벤트를 enable한다는 것이다. 우리의 예시에 대해 이를 살펴보자.
우선, 이벤트 a의 pre-region은 r1이다. 그리고 r1에 속해 있는 state는 i, s1인데 이들은 모두 a를 enable한다. 그러므로 a에 대해서 이 성질을 만족한다. 다음 예시로 c를 살펴 보자. c의 pre-region은 r2, r4이고 이의 교집합은 s2이다. s2는 c를 enable하므로 c에 대해 이 성질을 만족한다.
위 조건들을 모두 만족하는 transition system이 elementary transition system이다.
Elementary transition system to petri net
이 Elementarty transition system에 대해서 state-based region theory를 이용하면 safe(1-bounded, 한 place 안에 최대 1개의 토큰이 있는 것), pure(transition에 대해 input place와 output place가 disjoint인 것), simple (같은 input과 output place를 가지는 서로 다른 트랜지션이 없는 것) 페트리 넷을 도출할 수 있다. 그 과정은 다음과 같다.
1. Transition system의 각 이벤트가 페트리 넷의 트랜지션이 된다.
2. Transition system의 각 non-trivial region이 페트리 넷의 place가 된다.
3. initial state를 포함하는 region에 해당하는 place에 토큰을 더한다.
위와 같이 모든 non-trivial region들에 대해서 state based region theory를 이용하여 페트리 넷을 도출시킬 수 있는데, 이를 maximal saturated net이라고 한다. 또한 mininmal region들에 대해서만 state based region theory를 적용시켜petri net을 도출시킬 수도 있다. 이 페트리 넷을 minimal saturated net이라고 한다.
이번 포스팅에서는 elementary transition system이 무엇인지와 더불어 이를 이용해 만들 수 있는 petri net에 대해 알아보았다. 시험이 끝나니까 그 하고 싶던 글쓰기가 왜 이렇게 재미가 없는지.. 침대에서 굴러다니는 것이 제일 재밌다
References
1. M.Nielsen,G.Rozenberg,P.S.Thiagarajan,Elementarytransitionsystems,TheoreticalComputerScience96(1992)3–33.
2. Course: Advanced Process Mining. RWTH. Dr. Sebastiaan J. van Zelst
최근댓글