A. Khoumsi/Electronic Notes in Theoretical Computer Science 130
(
2005
)
79
对于图
1
的示例,设
δ
u
,
v
是动作
u
和
v
之间的延迟:
•
蒂奥
萨
最初在位置
10
。 在φ(m)出现时,位置
l1
变量
x
被赋值为
m
。
•
从
l1
开始,在
α
出现时,
T
iosa
达到
l2
。
•
从l2
开始
,在β出现时,
T
iosa
达到
l3
或
l4
。只有当δ
α
,
β
3和x
≥
p时才能达到
l3
,只有当δ
α
,
β
>2和x
≤
p时才能达到
l4
。
我们看到当2<δ
α
,
β
3和x=p时存在非决定性。当达到
L4
•
从
13
层
开始,
蒂奥
萨
什么都不执行
•
从l4
开始
,在ρ出现时,
T
iosa
达到
l1
。我们有δ
α
,
ρ
>3。
T
iosa
A
的语义也可以由
A
接受的定时迹集来定义。以下是一些必要的定
义:
定时动作是一对(
e
,
τ
),其中
e
是动作,
τ
是
e
发生的时刻。当
e
是一个
输入时((
1
)
“
行
”
是
“
行
”
,
“
行
”
是
“
行
”
。
定时输出
、
定时内部
)
动
作
。
定时序列是定时动作的(有限或无限)序列<<<<“(e1,τ1)···(e
i,τi)···“,其中0τ1···τi···。
定时跟踪是通过删除定时序列的所有定时内部操作从定时序列中获得的。
对给定的时间序列
λ
t
=
(
e1
,
τ
1
)(
e2
,
τ
2
)···,对
e1
,
e2
,
··· ∈
τ
,可接
受
.
设
n
是
λ
t
的长度(
n
可以是无限的),
λ
ti
=
(
e1
,
τ
1
)···(
ei
,
τ
i
)
是长度为
i
的
λ
t
的前缀,其中
0
≤
i
≤
n
(
i
是有限的)。
λ
t
被
A i
接受
<$λ
t
是空序列
λ
t
0
或
A
有一个长度为
n
的连续转移序列
Tr
1
Tr
2
···,从
l
0
开始,使得
Tri= 1
,
2
,
·
··
,
n
:
Tr
i
的动作是
e
i
,在执行
λ
t
i
−
1
之
后,
Tr
i
在时间
τ
i
被使能。直观地说,
λ
t
对应于
A
的一次执行。
接受定时迹:设
μ
t
=
(
e
1
,
τ
1
)(
e
2
,
τ
2
)···为定时迹。
μ
t
被
A
接受
i μ
t
是通过
删除
A
接受的定时序列的所有定时内部动作而获得的。直觉,
μ
t
对应于
对
A
的执行的观察。
定义
2.1
T
iosa
A(TOL
T
iosa
)
的时间可观察语言
是
A
的行为。
我们将考虑的
T
iosa
类满足以下假设:
假设
2.1T iosa A
接受的无限时间序列是
非
zeno
的,即,无限数量的动作
不能在有限的时间间隔内执行