계산 트리 논리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 문법
4. 연산자
5. 의미론
- 5.1. 의미상 동치
6. 예제
7. 다른 논리와의 관계
8. 확장
참조

1. 개요

계산 트리 논리(CTL)는 1981년 에드먼드 M. 클라크와 E. 앨런 에머슨에 의해 제안된 형식 검증에 사용되는 논리 체계이다. CTL은 병렬 프로그래밍의 검증에 활용되었으며, 모델 검사 도구에서 명세 언어로 채택되어 널리 사용되었다. CTL은 원자 명제, 논리 연산자, 시간 연산자를 사용하여 시스템의 속성을 표현하며, 경로 연산자(A, E)와 상태 연산자(X, G, F, U, W)를 조합하여 다양한 시간적 속성을 정의한다. CTL은 CTL*와 모달 뮤 계산법의 부분 집합이며, 선형 시간 논리(LTL)와는 표현력에 차이가 있다. CTL은 2차 정량화를 통해 QCTL로 확장되었다.

2. 역사

CTL은 1981년 에드먼드 M. 클라크와 E. 앨런 에머슨에 의해 처음 제안되었으며, 그들은 CTL을 사용하여 ''동기화 스켈레톤'', 즉 병렬 프로그래밍의 추상화를 합성했다.^[1]

CTL이 소개된 이후, CTL과 선형 시간 논리(LTL)의 상대적 장점에 대한 논쟁이 있었다. CTL은 모델 검사를 계산적으로 더 효율적으로 수행할 수 있기 때문에 산업적 사용에서 더 널리 사용되었으며, 가장 성공적인 모델 검사 도구 중 다수가 CTL을 명세 언어로 사용한다.^[1]

3. 문법

CTL의 정규 언어의 잘 구성된 공식은 다음의 문맥 자유 문법에 의해 생성된다.^[1] 여기서 $p$ 는 원자 공식 집합을 나타낸다.^[2] CTL은 원자 명제를 시스템 상태에 대한 진술을 만들기 위한 구성 요소로 사용하며, 이러한 명제는 논리 연산자와 시간 연산자를 사용하여 공식으로 결합된다.^[3]

: $\begin{align}\phi &::= \bot \mid \top \mid p \mid (\neg\phi) \mid (\phi\land\phi) \mid (\phi\lor\phi) \mid(\phi\Rightarrow\phi) \mid (\phi\Leftrightarrow\phi) \\&\mid\quad \mbox{AX }\phi \mid \mbox{EX }\phi \mid \mbox{AF }\phi \mid \mbox{EF }\phi \mid \mbox{AG }\phi \mid \mbox{EG }\phi \mid\mbox{A }[\phi \mbox{ U } \phi] \mid \mbox{E }[\phi \mbox{ U } \phi]\end{align}$

모든 연결자를 사용할 필요는 없다. 예를 들어, $\{\neg, \land, \mbox{AX}, \mbox{AU}, \mbox{EU}\}$ 는 완전한 연결자 집합을 구성하며, 다른 연결자는 이를 사용하여 정의할 수 있다.^[4]

$\mbox{A}$ 는 '모든 경로를 따라' ''(필연적으로)''를 의미한다.
$\mbox{E}$ 는 '적어도(존재) 하나의 경로를 따라' ''(가능하게)''를 의미한다.

예를 들어, 다음은 잘 구성된 CTL 공식이다.

:

\mbox{EF }(\mbox{EG } p \Rightarrow \mbox{AF } r)

다음은 잘 구성되지 않은 CTL 공식이다.

:

\mbox{EF }\big(r \mbox{ U } q\big)

이 문자열의 문제는

\mathrm U

가

\mathrm A

또는

\mathrm E

와 짝을 이루어 사용되어야 한다는 것이다.

4. 연산자

계산 트리 논리(CTL)에서 사용되는 연산자는 기본 명제, 논리 연산자, 시상 연산자로 구성된다. 기본 명제는 참(T) 또는 거짓(F) 값을 가질 수 있다.^[1]

CTL은 1차 술어논리에서 사용되는 어휘를 기본 요소로 사용하며, 여기에 시간 개념을 위한 연산자가 부가되어 논리식을 형성한다. CTL에서 사용되는 연산자들은 다음과 같다.

논리 연산자: ¬ (부정), ∧ (논리곱), ∨ (논리합), → (조건)
시상 연산자:
경로 연산자:
A (전체): 모든 실행 가능한 경로에 대해 필연적으로 만족해야 함
E (존재): 적어도 하나의 실행 가능한 경로가 존재하여 만족해야 함
상태 연산자:
X (다음): 다음 상태에서 만족해야 함
G (항상): 모든 후속 경로에서 항상 만족해야 함
F (결국): 후속 경로 어딘가에서 결국 만족해야 함
U (~까지): 특정 조건이 만족될 때까지 만족해야 함

CTL에서 시상 연산자는 항상 경로 연산자와 상태 연산자가 쌍으로 그룹화되어 사용되어야 한다. 예를 들어, "U" 연산자 앞에는 반드시 "A" 또는 "E"가 나와야 한다.

논리식 φ, ψ에 대하여, 각 연산자가 붙은 CTL 식의 의미는 다음과 같다.

AXφ: 현재 상태에서 모든 실행 가능한 경로에 대하여, 그 다음 상태에서 φ가 성립한다.
EXφ: 현재 상태에서 연결되는 경로 중 어떤 경로에 대하여, 그 다음 상태에서 φ가 성립한다.
AGφ: 현재 상태에서 모든 실행 가능한 경로에 대하여, 언제나 φ가 성립한다.
EGφ: 현재 상태에서 연결되는 경로 중 어떤 경로에 대하여, 언제나 φ가 성립한다.
AFφ: 현재 상태에서 모든 실행 가능한 경로에 대하여, 언젠가는 φ가 성립한다.
EFφ: 현재 상태에서 연결되는 경로 중 어떤 경로에 대하여, 언젠가는 φ가 성립한다.
A[φ U ψ]: 현재 상태에서 모든 실행 가능한 경로에 대하여, 언젠가는 ψ가 성립하며, 동시에 최초에 ψ가 성립되기까지는 φ가 성립한다.
E[φ U ψ]: 현재 상태에서 연결되는 경로 중 어떤 경로에 대하여, 언젠가는 ψ가 성립하며, 동시에 최초에 ψ가 성립되기까지는 φ가 성립한다.

예를 들어, `EF EG p → AF r`은 CTL의 논리식이지만, `EF (r U q)`는 논리식이 아니다.

4. 1. 논리 연산자

CTL은 일반적인 논리 연산자인 ¬, ∨, ∧, ⇒, ⇔와 함께, 부울 상수인 참과 거짓을 사용한다.^[1] 이러한 연산자는

\neg, \or, \and, \rightarrow

및

\leftrightarrow

와 같이 표기하기도 한다.^[1]

4. 2. 시상 연산자

CTL의 시상 연산자는 다음과 같다.

경로 연산자(Path Operators)
'''A''' Φ - '''A'''ll (전체): 현재 상태에서 시작하는 모든 경로에서 Φ가 참이어야 한다.
'''E''' Φ - '''E'''xists (존재): 현재 상태에서 시작하는 경로 중 Φ가 참인 경로가 적어도 하나 존재한다.
상태 연산자(State Operators)
'''X''' ''φ'' - Ne'''x'''t (다음): ''φ''는 다음 상태에서 참이어야 한다 (이 연산자는 때때로 '''X''' 대신 '''N'''으로 표기된다).
'''G''' ''φ'' - '''G'''lobally (전체적으로): ''φ''는 전체 후속 경로에서 참이어야 한다.
'''F''' ''φ'' - '''F'''inally (결국): ''φ''는 결국 (후속 경로 어딘가에서) 참이어야 한다.
''φ'' '''U''' ''ψ'' - '''U'''ntil (~까지): ''φ''는 ''ψ''가 참이 되는 어떤 위치 ''까지''는 참이어야 한다. 이는 ''ψ''가 미래에 검증될 것임을 의미한다.
''φ'' '''W''' ''ψ'' - '''W'''eak until (약한 ~까지): ''φ''는 ''ψ''가 참이 될 때까지 참이어야 한다. '''U'''와의 차이점은 ''ψ''가 실제로 검증될 것이라는 보장이 없다는 것이다. '''W''' 연산자는 "unless(그렇지 않으면)"라고도 한다.

CTL*에서 템포럴 연산자는 자유롭게 혼합될 수 있지만, CTL에서는 연산자가 항상 쌍으로 그룹화되어야 한다. 즉, 하나의 경로 연산자 다음에 상태 연산자가 온다. CTL*는 CTL보다 엄격하게 더 표현력이 뛰어나다.

\mbox{A}

는 '모든 경로를 따라' ''(필연적으로)''를 의미하며,

\mbox{E}

는 '적어도(존재) 하나의 경로를 따라' ''(가능하게)''를 의미한다.

예를 들어,

:

\mbox{EF }(\mbox{EG } p \Rightarrow \mbox{AF } r)

위 식은 잘 구성된 CTL 공식이다.

하지만,

:

\mbox{EF }\big(r \mbox{ U } q\big)

위 식은 잘 구성되지 않은 CTL 공식인데, 그 이유는

\mathrm U

가

\mathrm A

또는

\mathrm E

와 짝을 이루어 사용되어야 한다는 규칙을 지키지 않았기 때문이다.

4. 3. 최소 연산자 집합

CTL에는 최소 연산자 집합이 존재하며, 모든 CTL 공식은 이 최소 집합만을 사용하여 표현할 수 있다. 이는 모델 검증에 유용하다. 최소 연산자 집합의 예시로는 {true, ∨, ¬, '''EG''', '''EU''', '''EX'''}가 있다.

시간 연산자는 다음과 같이 최소 연산자 집합으로 변환될 수 있다.

'''EF'''''φ'' == '''E'''[true'''U'''(''φ'')] ('''F'''''φ'' == [true'''U'''(''φ'')]이기 때문)
'''AX'''''φ'' == ¬'''EX'''(¬''φ'')
'''AG'''''φ'' == ¬'''EF'''(¬''φ'') == ¬ '''E'''[true'''U'''(¬''φ'')]
'''AF'''''φ'' == '''A'''[true'''U'''''φ''] == ¬'''EG'''(¬''φ'')
'''A'''[''φ'''''U'''''ψ''] == ¬( '''E'''[(¬''ψ'')'''U'''¬(''φ''∨''ψ'')] ∨ '''EG'''(¬''ψ'') )

5. 의미론

CTL 공식은 전이 시스템을 통해 해석된다. 전이 시스템은 $\mathcal{M}=(S,{\rightarrow},L)$ 형태로 구성되는데, 여기서 $S$ 는 상태 집합, ${\rightarrow} \subseteq S \times S$ 는 전이 관계 (모든 상태가 적어도 하나의 후속 상태를 갖는 직렬 관계), $L$ 은 명제 문자를 상태에 할당하는 라벨링 함수이다.

$\mathcal{M}=(S,\rightarrow,L)$ 을 전이 모델이라 하고, $s \in S$ 및 $\phi \in F$ ( $F$ 는 $\mathcal{M}$ 의 형식 언어에서 잘 정의된 공식의 집합)일 때, 의미론적 함의 관계 $(\mathcal{M}, s \models \phi)$ 는 $\phi$ 에 대해 재귀적으로 정의된다. (자세한 정의는 영문 문서 참조)

CTL은 주어진 상태 $s$ 를 뿌리로 하는 무한히 깊은 계산 트리의 본질에 대한 주장을 담고 있다.

5. 1. 의미상 동치

두 CTL 공식 φ와 ψ는 어떤 모델에서든 한쪽을 만족하는 모든 상태가 다른 쪽도 만족하면 의미상 동등하며, φ ≡ ψ로 표기한다.

\mathrm A

(전체 경로)와

\mathrm E

(존재 경로)는 서로 이중 관계이다. 즉, ¬ AΦ ≡ E ¬ Φ 이다.

\mathrm G

(항상)와

\mathrm F

(언젠가) 역시 서로 이중 관계이다.

드 모르간 법칙을 CTL에 적용하면 다음과 같은 항등식을 얻을 수 있다.

¬ AFφ ≡ EG ¬ φ
¬ EFφ ≡ AG ¬ φ
¬ AXφ ≡ EX ¬ φ

CTL 연결사의 검증을 시간상 다음 상태로 펼칠 수 있게 해주는 '''확장 법칙'''은 다음과 같다.

AGφ ≡ φ ∧ AX AG φ
EGφ ≡ φ ∧ EX EG φ
AFφ ≡ φ ∨ AX AF φ
EFφ ≡ φ ∨ EX EF φ
A[φ U ψ] ≡ ψ ∨ (φ ∧ AX A [φ U ψ])
E[φ U ψ] ≡ ψ ∨ (φ ∧ EX E [φ U ψ])

6. 예제

P가 "나는 초콜릿을 좋아한다", Q가 "날씨가 따뜻하다"를 의미한다고 할 때, CTL 공식의 예시는 다음과 같다.

'''AG'''.P: "나는 앞으로 무슨 일이 있어도 초콜릿을 좋아할 것이다."
'''EF'''.P: "언젠가는, 적어도 하루는 초콜릿을 좋아하게 될 가능성이 있다."
'''AF'''.'''EG'''.P: "내가 앞으로 영원히 초콜릿을 갑자기 좋아하게 될 가능성이 항상 있다." (참고: 내 생명이 유한하기 때문에 단순히 내 남은 생이 아니라 '''G'''는 무한하다.)
'''EG'''.'''AF'''.P: "앞으로 어떤 일이 벌어지느냐에 따라 (E), 영원히 (G) 앞으로 초콜릿을 좋아하는 날이 최소한 하루는 보장될 수 있다(AF). 그러나 만약 뭔가 잘못되면 모든 것은 무효가 되고 내가 초콜릿을 좋아하게 될지 여부는 보장되지 않는다."

다음 두 예시는 CTL*과 CTL의 차이점을 보여주는데, 이는 until 연산자가 경로 연산자('''A''' 또는 '''E''')로 한정되지 않아도 되기 때문이다.

'''AG'''(P'''U'''Q): "지금부터 날씨가 따뜻해질 때까지 매일 초콜릿을 좋아할 것이다. 날씨가 따뜻해지면, 더 이상 초콜릿을 좋아할지 여부는 알 수 없다. 아, 그리고 언젠가는, 단 하루라도 따뜻해지는 것이 보장된다."
'''EF'''(('''EX'''.P)'''U'''('''AG'''.Q)): "다음과 같은 가능성이 있다. 언젠가는 날씨가 영원히 따뜻해질 것이고(AG.Q), 그 시간 전에 항상 다음 날 나를 초콜릿을 좋아하게 만들 수 있는 ''어떤'' 방법(EX.P)이 있을 것이다."

7. 다른 논리와의 관계

CTL은 CTL*와 모달 μ 계산법의 부분 집합이다. CTL은 알루어, 헨징거, 쿠퍼만의 교대 시간 논리(ATL)의 일부이기도 하다. CTL과 선형 시간 논리(LTL)는 모두 CTL*의 부분 집합이지만, 서로 동등하지 않다.^[1] CTL과 LTL 모두의 진부분 집합인 공통 부분 집합을 가지고 있다.

'''FG'''P^영어는 LTL에는 존재하지만 CTL에는 존재하지 않는다.
'''AG'''(P⇒(('''EX'''Q^영어)∧('''EX'''¬Q^영어)))와 '''AG.EF'''P^영어는 CTL에는 존재하지만 LTL에는 존재하지 않는다.
'''GF'''P^영어는 LTL에는 있지만 CTL에는 없다.
'''AG'''(P→('''EF'''Q^영어))는 CTL에는 있지만 LTL에는 없다.

8. 확장

CTL은 2차 정량화 $\exists p$ 및 $\forall p$ 를 사용하여 "정량적 계산 트리 논리"(QCTL)로 확장되었다.^[2] QCTL에는 두 가지 의미론이 있다.

트리 의미론: 계산 트리의 노드에 레이블을 지정한다. QCTL* = QCTL = 트리상의 MSO. 모델 검증 및 만족도는 타워 완전이다.
구조 의미론: 상태에 레이블을 지정한다. QCTL* = QCTL = 그래프상의 MSO. 모델 검증은 PSPACE-완전이지만 만족도는 결정 불가능하다.

구조 의미론을 갖는 QCTL의 모델 검증 문제에서, QBF 해결사의 이점을 활용하기 위해 TQBF(참 정량 부울 공식)로의 축소가 제안되었다.^[3]

참조

_[1] 서적 Springer, Berlin 2001
_[2] 간행물 On the Expressiveness of QCTL http://drops.dagstuh[...] Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik 2016
_[3] 간행물 From Quantified CTL to QBF http://drops.dagstuh[...] Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik 2019
_[4] 서적 소프트웨어과학기초, TopSE 기초강좌1 近代科学社

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com