I H C BÁCH KHOA
---------------------------------------

NGUY N TH H NG PH N

NG D NG

TH PH THU C BI N

TRONG KI

NG KÝ HI U

VÀ TINH L C TR

NG

MÃ S CHUYÊN NGÀNH: 60.48.01

LU

TH

TP. H CHÍ MINH, tháng 0


BÁCH KHOA
TS.

-HCM
...........................

TS.

N ...............

TS.

..................................

HQG Tp. HCM
ngày 24 tháng 07

2013

1.

.........................

2.

..................

3.

..............

4.

..............................


5.

............................

n ã


I H C QU C GIA TP.HCM

C NG HÒA XÃ H I CH

I H C BÁCH KHOA

T NAM

c l p - T do - H nh phúc

NHI M V LU
...................... MSHV: 11070465 ..........
12/10/1984 .........................................

....

.......................................

: 60.48.01 ...........

Chuyên ngành:
I.


TÀI: ............................................................................................................
....................................................................................................

II. NHI M V VÀ N I DUNG: .................................................................................

III. NGÀY GIAO NHI M V : 21/01/2013 ...............................................................
IV. NGÀY HOÀN THÀNH NHI M V : 21/06/2013 ................................................
V. CÁN B

CÁN B

NG D N: TS.

NG D N

..................................................

CH NHI M B

(H tên và ch ký)

(H tên và ch ký)

(H tên và ch ký)

O


L IC


,

c

. Tơi xin

v

g i

.
chân thành bày t lịng bi t n
K

& KT Máy Tính -

Khoa TP.HCM
k n thu

t n tình truy

n tồn th q Th y Cơ trong
ng

t nh ng ki n th

l i nh cho tôi trong su t quá trình h

quý báu c ng nh t


H c Bách
m

i u

t p.

c

C

,

.
Tơi xin chân thành c
TP. H Chí Minh, tháng 06 n m 2013

Nguy n Th H ng Ph n


TÓM T T LU

Trong l nh v c ki m tra mơ hình hi n nay, bùng n khơng gian tr ng thái là m t
rào c n trong vi c ki m tra các h th ng có khơng gian tr ng thái l n vì khơng th tìm
ki m l i b ng cách vét c n các tr ng thái. Vì lý do
tinh l c tr u

,

xu t k thu t


ng hi n th c trên công c GOLFER (công c nà

c xây d ng trên

n n NuSMV) cho phép ki m tra trên các mơ hình có khơng gian tr ng thái l n. V
khơng gian tr ng thái l

c gi i quy t b ng cách tr u

ng hóa (gom nhóm nhi u

tr ng thái thành m t tr ng thái). Thay vì ki m tra trên mơ hình th t, mơ hình tr
s

c ki

c. N u tìm th y l i trên mơ hình tr u

ng

ng, công c GOLFER

m i m r ng ph m vi tìm ki m trên mơ hình th t. Tuy nhiên cách m r ng ph m vi tìm
ki m nh th nào
tính v n cịn h tr

có th

nh v


c là v

c l i nhanh nh t mà kh n ng l u tr c a máy
c n ph i gi i quy t. Lu n v n s trình bày cách th c

gom nhóm nhi u tr ng thái thành m t tr ng thái (bài toán tr u
vi c m r ng m t tr ng thái tr
qua k thu t tinh l c tr u
quá trình

ng thành nhi u tr ng thái (bài toán tinh l c) thơng

ng. Q trình tr

c nhau. Có th hi u

ng hóa) c ng nh

ng hóa và q trình tinh l c là hai

n gi n là tr u

ng bi n nh ng cái c th thành

cái t ng quát, còn tinh l c là bi n cái t ng quát thành cái c th . Lu n v n v n d ng ý
ng gi i thu t PageRank vào vi c phân tích
thu c bi

gi i quy t bài tốn tr


th ph

ng. Ngồi ra, lu n v n cịn gi i thi u gi i

thu t tìm l i m i, gi i thu t tinh l c tr u
ng (Clarke) và gi i thu t a tr u

quan tr ng c a bi

ng, là s k t h p gi i thu t tinh l c tr u

ng (Qian & Nymeyer ).


ABSTRACT

In current model checking field, the statespace explosion prevents to verify
these large systems due to the reason that exhaustive search is failed. Therefore, this
thesis proposes the abstraction refinement technique implemented on GOLFER (the
tool is built on NuSMV) allows to verify on large state space systems. Abstraction is
applied to reduce the size of statespace. Instead of checking on concrete model,
abstract model is verified firstly. If finding counter example, the searching scope is
widen on the concrete model, this process can be called refinement. Abstraction and
refinement are two opposite processes. Abstraction makes complex things to simple
things while refinement maps simple things to complex things. For abstraction solving,
PageRank algorithm

n the


variable dependency graph. Moreover, this thesis also introduces a new searching
algorithm, abstraction refinement, a combination of counter-example guided
abstraction refinement (Clarke) and multiple abstraction (Qian & Nymeyer).


L

tc
.
Tp.

21 tháng 06

2013

Nguy n Th H ng Ph n


M CL C

L IC

.................................................................................................... i

TÓM T T LU

....................................................................................ii

ABSTRACT .................................................................................................... iii
L


............................................................................................. iv

M C L C ......................................................................................................... v
-

....................................viii

DANH M C HÌNH ........................................................................................... x
DANH M

........................................................................................ xi
I THI

1.1. Lý do ch

TÀI .................................................................. 1

tài ..................................................................................... 1

1.2. M

tài ......................................................................................... 2

1.3. Ph

tài .......................................................................................... 4

1.4. Ý ngh


tài .......................................................................................... 4

1.5. Gi i thi

................................................... 4
.............................................................................. 5
LÝ THUY T ................................................................... 6

2.1.

........................................................ 6
.................................................................. 8


..................................................... 10
GOLFER ................................................................................. 10
......................... 11
-example guided abstraction refinement) .... 13
.......................... 15
.............................. 18
xu t ............................................................................. 18
.......................................... 18
....................................................... 21
................................................. 21
xu t............................................................... 22
phân tích ph thu c bi n PG và VRK ............ 22
................................ 24
......................................... 25
................................................................... 25
................................................................................... 26

...................................................... 30
................... 30
6.1.1. Th nghi m v i Leader- Election .................................................... 31
6.1.2. Th nghi m v i Needham ............................................................... 32
6.1.3. Th nghi m v i Peterson ................................................................. 32
6.1.4. Th nghi m v i Sender-Receiver .................................................... 33
.......................... 34


6.2.1. Th nghi m v i Leader-Election ..................................................... 35
6.2.2. Th nghi m v i Needham ............................................................... 35
6.2.3. Th nghi m v i Peterson ................................................................. 35
6.2.4. Th nghi m v i Sender-Receiver .................................................... 36
6.3. Gi

.......................... 37

6.3.1. Ki m tra trên mô hình tr

ng ch a 50% bi n và mơ hình g c ... 37

6.3.2. Ki m tra trên t p h p các mơ hình tr

ng ch a 20%, 80% bi n và

mơ hình g c ......................................................................................................... 38
6.3.3. Ki m tra trên t p h p các mơ hình tr

ng ch a 20%, 55%, 90%


bi n và mơ hình g c ............................................................................................. 39
6.4.

.......................................... 40
............................... 40
............................................................................... 43

7.1. T

....................................................................... 43
............................................................ 44

DANH M C CÁC TÀI LI U THAM KH O ................................................. 45
PH L

.................................................................. 47

PH L

........................................... 50

PH L C C: DOWNLOAD TÀI NGUYÊN ................................................... 54
PH L C D: MINH H

TH PH THUÔC BI N ............................... 55

LÝ L CH TRÍCH NGANG .............................................................................. 56


-


Thu t ng ti ng Anh

,V

Thu t ng ti ng Vi t

Vi t t t

Abstract DB
Abstract file
Abstract model

Mơ hình tr

ng

Tinh l c tr

ng,

Abstraction
l i

Abstraction refinement

Concrete model

MAR


Mơ hình th t

Convergent variable

VRK

dependency analysis
Counter-example

Ph n ví d ,

ng i ch a l i

Formal methods
Formal specification
Formal verification

c t hình th c
Ki

nh hình th c

Formal language
Heuristic Generator
Model
Model Analysis

Multiple abstraction

(t


CE


)
Propagation variable

PG

dependency analysis
Property
Simple variable

SIM

dependency analysis
Spurious counter example

L i gi trên mơ hình tr u

Theorem proving
Variable dependency
analysis
Verification

Phân tích ph thu c bi n

ng



DANH M C HÌNH

ng hóa tín hi

.......................................... 2

th ph thu c bi n[15].................................................................... 3
th ng tr

........................ 9

n trúc c a GOLFER ..................................................................... 10
Si,0, Si,1

......................................... 13
Si,x.......................................................................... 15
ng (Multiple Abstraction) ........................... 16
............................................................. 22
.............................................................. 25
................................................. 26
-

.............. 31
............. 33
-

-

34
............................. 35

........................................ 36

-

............................ 36
..... 38
..... 38
m tra trên 3 file

..... 39

.................................... 40
....................................................... 41
th ph thu c bi n cho bài toán Leader-3 .................................... 55


DANH M C

p tr ng thái ........................................... 14
.......................................................................... 23
.................................................... 27
.................................................. 32
................................................................ 35
-A* gi l i 50% bi n .................................. 50
-A* gi l i 50% bi n ..................................... 50
- MAR gi l i 50% bi n ............................. 51
- MAR gi l i 50% bi n .............................. 51
- SAGA gi l i 50% bi n ............................ 51
- MAR gi l i 20% và 80% bi n ................. 52
-gi l i 20%, và 80% bi n ........................... 52

-MAR gi l i 20%, 55% và 90% bi n ......... 52
-SAGA gi l i 20%, 55% và 90% bi n........ 53
i gian th c thi trên NuSMVg c v

.................... 53


ng d

th ph thu c bi n trong ki

ng ký hi u và tinh l c tr

GI I THI
Ph n này s gi i thi u t ng quan v
ph m vi c a

tài: lý do ch n

cb

tài, m c tiêu c a

c các k t qu

c.

c khi

ng c a m t s n ph m ph n c ng, ph n m m c n


a ra th

i ta luôn tìm cách ki m tra các s n

ph m ph n c ng, ph n m m m t cách nhanh nh t và ít t n kém nh
c cá

tài,

tài

Xu t phát t yêu c u ch t
ph i

TÀI

tài, ý ngh a th c ti n và gi i thi u s

1.1. Lý do ch n

ng

c tính c a s n ph m có úng v i nhu c

có th ki m

i s d ng hay khơng thì

mơ hình hóa s n ph m ph n c ng, ph n m m và th c hi n

ki m tra trên mơ hình
m t ph

. Q trình này chính là ki m tra mơ hình

g pháp hình th c nh m

c ph n c ng và ph n m m

m b o tính

n c a h th ng bao g m

c áp d ng r ng rãi ngay c trong quá trình thi t k c a

s n ph m.
Tuy nhiên, ki m tra mơ hình hi n t i v n còn h n ch khi áp d ng ki m tra cho
m t h th ng l n. V i cách làm thô
l

ng là vét c n không gian tr ng thá

tìm

m tra mơ hình g p h n ch v m t th i gian và
n ng c a máy tính có gi i h n

tr u

ng hóa


c s d ng

làm gi m kích th

ng h p này, k thu t

c c a không gian tr ng thái. Tr u

ng hóa trong ki m tra mơ hình là cách t o ra các mơ hình tr u
hình th

u.

1.1 cho th y h th ng

green, yellow và khi th c hi n tr
còn 2 tr ng thái:

ng d a trên mơ

n giao thơng có 3 tr ng thái: red,

ng hóa trên mơ hình này thì h th ng tr u

ng


ng d


th ph thu c bi n trong ki

1.1 Tr u
V iý

ng tr

ng hóa tín hi u

ng hóa, kích th

rào c n trong ki m tra mơ hình. V
ng t t t mơ hình g
nà

ng ký hi u và tinh l c tr

ng

n giao thông[3]

c không gian tr ng thái l n khơng cịn là

cịn l i là làm th nà

có m t mơ hình tr u

u; và khi phát hi n l i trên mơ hình tr u

ki m ch ng l i


trên mơ hình g

ng, làm th

u m t cách ít t n kém th i gian và

chi phí nh t.
Vì nh ng lý do

tài này s hi n th c ch c n ng tinh l c tr u

cơng c GOLFER (cơng c nà
tr

ng có th hi u

c xây d ng trên n n NuSMV). Ch c n ng tinh l c

n gi n là s k t h p gi a tr u

tinh l c là m t quá trình

c c a tr

thì tinh l c là quá trình ánh x
tr ng thái th c trên mơ hình g

M c tiêu c a
d ng m t mơ hình tr


ng nh vào hàm tr

ng h

ng thành các

c h-1.

tài s tr l i câu h i:

tinh l c tr u

ng hi u qu thì xây

ng nh th nào? N u ki m tra trên mơ hình tr

ng phát

trên mơ hình g c nh th nào?

1.1, hàm tr u

ng trong ví d này là: gom nhóm các tr ng

thái xe c có th l u thơng (tr ng thái yellow và green) thành

1.2

ng hóa bi n nhi u


c l i các tr ng thái tr ng thái tr
u b ng hàm

ây

tài

hi n l i thì th c hi n tinh l c l i
Tr l i ví d

ng hóa và tinh l c.

ng hóa. N u tr u

tr ng thái trên mơ hình g c thành m t tr ng thái tr

1.2. M c tiê

ng cho


ng d

th ph thu c bi n trong ki

ng ký hi u và tinh l c tr

ng


Thang. H. Bui & Phuong. B.K. Dang

Level 0

x0

Level 1

x1

x3

Level 2

x2

x4

1.2

x5

th ph thu c bi n[15]

xu t m

thu c bi n m i: tính tốn

quan tr ng c a bi


th ph thu c bi n. Áp d

pháp phân tích ph thu c bi n vào tr

ng hóa mơ hình d a trên m c

quan tr ng c a bi n
xu t gi i pháp tinh l c tr

ng trong ki m tra mơ hình:là s k t

h p gi a gi i thu t CEGAR (counter example guided abstraction
refinement) và ph

ng pháp ki m tra mơ hình a tr u

ng (multiple

abstraction)
Nói cách khác m c tiêu c a

tài là gi i quy t bài toán bùng n không gian

tr ng thái trong ki m tra mơ hình b ng ph
tiê

xu t ph

ng pháp m i tính tốn


bi n. Xây d ng mơ hình tr
tr u

ng pháp tr u tinh l c tr u t
quan tr ng c a bi

ng d a trên m c

th ph thu c

quan tr ng c a các bi n. Hàm

ng h p này th c hi n gom nhóm các bi n có

ch gi l i các bi n có

c

quan tr ng l n. Gi i thu t tinh l c tr u

quan tr ng nh ,
ng th c hi n ki m


ng d

th ph thu c bi n trong ki

tra trên mơ hình tr u


ng ký hi u và tinh l c tr

ng

ng, n u phát hi n l i, th c hi n tinh ch nh l i mơ hình tr u

ng g n h th ng th c h n và l p l i quá trình ki m tra.

1.3. Ph m

tài
xu t m t ph

tinh l c tr

ng pháp phân tích ph thu c bi n m i và ph

ng pháp

ng cho công c GOLFER. Th nghi m k t qu v i các bài toán m u
lection, Sender Receiver and Peterson
.

1.4. Ý ngh a

tài

N u theo ph

ng pháp truy n th ng là vét c n không gian tr ng thái

Công c
i

xu t
l

, cho phép ch y trên các mơ hình có s tr ng thái
t qu nhanh chóng. V
i)

M c dù m c tiêu c a ki m tra ch
t

ng trong ki m tra mơ hình có th

c

ng trình là
c dùng

tìm l i nh ng tinh l c tr u

ch ng minh h th

1.5. Gi i thi u s
cho k t qu
v i các bài toán
.



ng d

th ph thu c bi n trong ki

ng ký hi u và tinh l c tr

ng

k thu t
MAR (abstraction refinement)

1.6.
Ph n còn l i c a lu

c t ch

: trình bày các v
thuy t v tr u

v

ng, mơ hình tr u

lý thuy t v ki m tra mơ hình và lý

ng trong ki m tra mơ hình.
(cơng c ki m tra mơ hình

ký hi u GOLFER, ph
mơ hình a tr u


ng

ng pháp phân tích ph thu c bi n lan truy n, k thu t ki m tra
ng và gi i thu t CEGAR (counter-example guided abstraction

refinement).
ình bày p

xu t và

xu t

cho gi i thu t phân tích bi n h i t d a trên gi i thu t PageRank và gi i
thu t tinh l c tr u

ng (k t h p gi a CEGAR và a tr

ng).

5: trình bày ph n h
thi u nh

, ph n này gi i

i trong ki n trúc công c ki m tra mơ hình

ng ký hi u và gi i

thi u cú pháp câu l nh th c thi.

6: trình bày k
th c hi n so sánh ph

, các k t qu th c thi trong ph n này

ng pháp phân tích bi n lan truy n và ph

ng pháp phân tích

bi n h i t trên gi i thu t tìm l i A*, so sánh gi i thu t tinh l c tr u
thu t a tr u
mô hình

ng dùn

ng v i gi i

pháp phân tích bi n h i t , so sánh công c ki m tra

ng ký hi u GOLFER khi dùng gi i thu t tinh l c tr u
u.
7: tóm t t các k t qu

c c ng nh

ng v i công c


ng d


th ph thu c bi n trong ki

C

S

ng ký hi u và tinh l c tr

LÝ THUY T

M c tiêu chính c a cơng ngh ph n m m là cho phép
h th ng v

ng

k

ng

y m c dù ph c t p. Trong quá trình ki m tra s n ph m thì

k thu t ki m tra mơ hình và ch

n là hai k thu t có th áp d ng.

Ki m tra mơ hình là m

m trong nhánh ki

(formal verification)[4]. M c tiêu c a nhánh ki

n c a h th

nh hình th c

nh hình th c là ki

nh tính

c thi t k và xây d

i có

th ki m tra m t h th ng v i s tr ng thái không gi i h n b ng k thu t tr

ng

hóa (abstraction).
Ch

t ch ng minh mà h

th ng và thu c tính c n ki
minh

c bi u thành cơng th c logic tốn h c. Ch ng

n là m t quá trình i tìm k t qu cho các thu c tính c n ki m tra t các
(axioms) và các nguyên t

c. Trái v i ki m tra mơ hình, ch ng minh


n khơng g p tr ng i v vi c bùng n không gian tr ng thái.
Ph n lu n v n này ch t p trung vào nhánh ki m tra mô hình

2.1.

ng ký hi u.

(Model checking)

Trong ki m tra hình th c, ki m tra mơ hình [2] là m t cách tìm ra các vi ph m
c a các thu c tính trong khơng gian tr ng thái. Khi m t vi ph
ph n ví d (counter-

giúp cho các k

l i. Hi

c tìm th y, m t
th

nh v

c

c ng d ng r ng rãi trong nhi u
c: các h th ng nhúng, k thu t ph n m m, các thi t k ph n c ng. Nói m t

cách ng n g


mc
Th c hi n t

m tra mơ hình là:
ng


ng d

th ph thu c bi n trong ki

ng ký hi u và tinh l c tr

T o ra ph n ví d (counter-example) n u phát hi n l

ng

u này r t có

ích cho vi c tìm và s a l i.
Có th ki m tra riêng ph n: ch ki m tra các ph

c t riêng ph n và

có th ki m tra t ng tính ch t riêng r , vì có th ki m tra nh ng tính ch t
quan tr

c.

M t khác,


cịn có m t s h n ch :

Vi c ki m tra này ch th c hi n trên các mơ hình ch không ph i trên các
h th ng th c. D

t qu

c ch

i ph i có m t mơ hình mơ t

c g n chính xác h th ng

g c.
Ki m tra mơ hình ch ki m tra trên nh ng u c
nó khơng b

c cung c

n tr n v n c a c h th ng.

Quá trình ki m tra g p tr ng i

ph c t p c a h th ng ki m

tra l n. V i các h th ng ngày càng l n và ph c t p, s tr ng thái càng lúc càng l n, có
th d

n k t qu là khơng th nào quét h t t t c các tr ng thái c a h th ng. Khi


ki m tra mơ hình không th tr l
sai. B ng k thu t tr

c câu h

ng hóa, v n

c tính c n ki

bùng n tr ng thái

c gi i quy t.

Trong qui trình ki m tra mơ hình, m t h th ng c n ki
di

c bi u

t h th ng chuy n d ch (transition system).
th ng chuy n d ch (Transition system)] M t h th ng

chuy n d ch là m t b ký hi u M = M = (S, T, S0), t
S0 S là m t t p các tr ng thái kh
M t tr ng thái có th
tr ng thái kh

u, T

S


t t p các tr ng thái,

S là m t t p c a các s d ch chuy n.

c (reachable state) là tr ng thái có th

u sau khi qua nhi u s chuy n d ch.

nt


ng d

th ph thu c bi n trong ki

ng ký hi u và tinh l c tr

ng

2.2.
Tr

ng hóa là m

m thu g n không gian tr ng thái b ng

cách dùng m t tr ng thái tr
x y ra hi


ng bi u di n cho m t t p các tr ng thái g c

ng là m t tr ng thái tr

ng có th

i di n cho c các tr ng thái

không t n t i trong h th ng g c (tr ng thái không bao gi

t

n c a h th ng ban

u).
ng hóa theo mi n (Domain Abstraction)] Gi s
r ng S có th

c mơ t b ng m t t p các bi n tr ng thái X = (x0, x1, ..., xn),

Di. Gi s r ng có m t t p c a các ánh x toàn ánh H = (h1, h2, ..., hn),
x t

m t mi

nh Di vào m t mi

xi b b qua trong mơ hình tr

i


v

i|

i hi ánh

|Di|. (N

i

ng). Áp d ng H cho S, ký hi u H(S), s sinh ra

m t t p c a các phiên b n tr

ng S.
ng hóa (Abstraction)] M t s

(homomorphic-

i

tr

ng hóa

ng hình) c a m t h th ng chuy n d ch M = (S, T, S0) v i t p tr u

ng hóa theo mi n H là h th ng chuy n d
1),


H(s2))

khi (s1, s2)

0
0

= H(S0).

nh lý: N u m t h th ng tr

th ng th c

(Clarke[3])
c di
thì h th

,

i.

M t khác, khơng có gì b o
trên h th ng tr u

t là khi khơng có l i trong mơ hình

m là h th ng g c c ng có l i n u ta tìm

cl i


ng.

Ch ng minh: Gi s r ng có m t tr ng thái khơng th th
state) trong h th ng th c vi ph m các thu
theo mi n (domain abstraction), tr ng thái vi ph m này

n (unreachable

n, b ng vi c tr

ng hóa

c tr n v i các tr ng thái có


ng d

th ph thu c bi n trong ki

ng ký hi u và tinh l c tr

th

i

n (reachable state) thành m t tr ng thái tr

th


i

n (reachable state).
Ví d ,

ng

ng, nó tr thành tr ng thái có

2.1

. Ta th y trong h th ng th c
thái l i (11

n tr ng

u trong hình (b) thì tr ng thái (110) và tr ng thái (111)

c bi u di

n (11x).

000

100

101

110


001

010

011

111

a)

10x

00x

11x

01x
b)

2.1 H

có m t hàm tr u

h th ng tr

ng t t là bài toán c n gi i quy t.

ng

[15]



ng d

th ph thu c bi n trong ki

ng ký hi u và tinh l c tr

các cơng trình

ng

c

nh

,
-

rke et al. và
tion).

3.1.
GOLFER là m t công c ki

ng ký hi

trên n n t ng NuSMV. Ki n trúc c

3.1.


GOLFER tool

Model
Analysis

Model
Abstractor

Heuristic
Generator

Abstract DB

Abstract file

NuSMV

Model
(NuSMV)
+
Property
(INVAR)

c trình bày trong

c phát tri n d a

Multiple
Abstraction


Control flow

Guided
Random
Search

Guided
Search
(A*)

Statistic information
(& Counter-example)

Data flow

3.1 Ki n trúc c a GOLFER

Directed Model Checking

GOLFER Library


ng d

th ph thu c bi n trong ki

ng ký hi u và tinh l c tr

ng


Trong ki n trúc này, mơ hình (Model) và thu c tính c n ki m tra (Property)
phân tích và tính tốn tr u
i ki m tra (Directed Model Ch
ng (abstract file) chính là t p tr

ki m tra. File tr u

c t o ra m t cách th

phân tích ph thu c bi

c phân tích mơ hình (Model

Analysis), t p tr

c t o ra s

i t o mơ hình tr

t o ra mơ hình tr
d li u tr

B ki

d li u tr

tìm ki

d


ng các gi i thu t

ng trình h tr các gi i thu t

ng (multiple abstraction), tìm ki m ng u nhiên dùng heuristic

ng (guided random search) và A*(Guided search )
d

ng (Abstract DB).
d

u. Hi n t i b ki m tra ch
a tr u

ng

c chuy n sang b

t

tìm l i nh

c

dùng mơ hình tr

ng


ng tìm l i trên mơ hình g c

3.2.

(PG)

Thang. H. Bui & Phuong. B.K. Dang
thu c bi n tính tốn t m quan tr ng c a các bi n v i h th ng

c minh h a b

th ph thu c bi n. P
(Propagation variable dependency analysis), vi t t t là PG
th ph thu c bi n, cơng th

tính tốn t m quan tr ng c

iv im i
th là

E(x).
S ph thu c gi a các bi
1.2. M

c bi u di n b

quan tr ng c a các bi
M

quan tr ng c a các bi n


các bi n

m

Các bi n

cùng m c s

th ph thu c bi n nh

c tính theo cơng th c E(x).
m c th

quan tr ng.

(level) s l

i