定价时间自动机的折扣语义及其在最优调度中的应用

理论计算机科学电子笔记239（2009）179-191www.elsevier.com/locate/entcs定价时间自动机Uli Fauberberg和Kim G. 拉森部丹麦奥尔堡大学计算机科学系电子邮件：{uli，kgl}@ cs.aau.dk摘要我们引入了一个新的折扣语义定价时间自动机。贴现提供了一种方法来模拟无限跟踪的最优成本问题，并在最优调度和其他领域中有应用在贴现语义中，价格呈指数下降，因此，总成本的变化取决于这一部分在未来多久发生。 我们考虑在这种语义下的最优无限运行问题：给定一个定价的时间自动机，找到一条折扣价格最小的无限路径。我们表明，这个问题是可计算的，通过减少到一个类似的问题上有限加权图。这个证明依赖于一个关于定义在无限维区域上的单调函数最小化的新定理，这个定理本身就很有趣。保留字：时间自动机，定价时间自动机，最优调度，有限时间表，有限区域1引言在本十年中，对应用和重定向时间自动机技术进行了大量研究[1，6，9，10，13]。特别是，时间自动机的方法已经成功地处理调度问题（通常情况下），可以重新制定的可达性。为了解决最优调度问题，引入了定价时间自动机1的概念[7，4]。在这个扩展的模型中，底层的时间自动机被装饰有位置和转换上的价格，对时间自动机的行为期间累积成本增加的不同速率进行到目前为止，重点主要放在有限行为的最优性上，一个例外是累积成本和时间之间的极限比的概念，在[8]中已经考虑过，其中表明，对于极限比，最优的有限时间表对于定价时间自动机是可计算的。本文1在[7]中称为线性定价时间自动机，在[4]中称为加权时间自动机1571-0661/© 2009 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2009.05.039180联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179−−→s我们采用不同的方法来实现无限行为的最优性，通过应用贴现原理：行为的某一部分对总成本的贡献取决于这一部分在未来发生的时间。贴现是经济学中一个众所周知的原理，并且已经在时间自动机的上下文中使用，例如[12]。我们证明了对于定价时间自动机，折扣最优无限时间表是可计算的，使用[8]的角点抽象。证明依赖于一个新的定理最小化单调函数的无限维区域，这推广了以前已知的结果有限维区域。在这个无限维的设置中，通常的紧性参数是不可用的，所以证明依赖于收敛序列的显式构造，∞.我们预计结果也在其他设置中具有应用。作者要感谢Patricia Bouyer、Lisbeth Fajstrup、John Leth和Martin Raussen就本文主题进行的大量讨论带折扣的2时间转移系统在本文中起着重要的作用，所以我们回忆一下[2]中的定义：定义2.1[2]定时转移系统是一组状态S的一对（S，T）和一组跃迁T=Ts<$Td，其中Ts<$S×S和Td<$S×≥0×S，它会对下面的流程进行分类，而我们会编写−→t sJinsteadof（s，t，sJ）∈Td：(i) （zerodelays）s−→0对于所有的s∈S，(ii) （additivity）whenevers−→tsJsJJ∈S，且而tJTJ≤t，tenalsos−→sJJt−tJJ对于一些(iii) （determinism）whenenevers−→tsJands−→t那么SJ= SJJ。Ts中的跃迁称为开关（也写作s→sJ，而不是（s，sJ）∈Ts），Td中的跃迁称为延迟。定义的最后一个要求意味着延迟转换的目标是由源唯一确定的，因此我们cannwritedelaytransitionsas−→t我们将在接下来的时间里这样做定义2.2一个定价的时间变迁系统，简称PTTS，是一个元组（S，T，p，r），其中（S，T = Ts<$Td）是一个时间变迁系统，p：Ts→≥0，r：S→≥0是价格函数。转换转换e=s→sJ的价格p（e）模拟了进行这种转换所需的资源量，而状态s的价格率r（s）衡量了保持在该状态的成本我们希望使用某种形式的折扣来度量定价定时转换系统中执行或路径的累积成本。为此，我们从现在开始固定一个贴现因子λ，0<λ 1，我们定义下面的贴现价格，使得未来t个时间单位发生的事情被因子λt贴现。联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）1791810lnλ00n−1n通过定义p（s−→t），可以实现两次精确的函数迭代 st）=我们注意到，对于所有t，在r（st）=r（s）的情况下，上述简化为：p（s−→t st）=r（s）1（λt−1）。要实现精确的数据传输，必须确保数据传输的精确性延迟转换所经过的所有状态的价格之和，但通过时间的流逝进行贴现。该贴现原则亦适用于以下定义。定义2. 图3在hπ=s0−t→0时，a fini e altering g p的计算概率0→tn−1tn−1s1→·· ·−−→sn−1→snisthenumbern-1。tP（π）=λTi−1 p（si−→isti） +λtip（sti→si+1）我我i=0其中Ti吉吉j=−1tj t-1= 0。 无限交替的贴现价格pathπ=s0−t→0st0→s1→ ···是极限P（π）=limn→∞P（π²2n）只要它存在。 这里π²2n表示π限制为2n步，即向上转换为stn−1→s。定义2.4状态s∈S的折扣最优价格为..ΣPmin（s）=infP（π）。π是从s开始的无限路径一条从s开始的无限路径π称为折扣最优路径，如果P（π）=Pmin（s）。一个从s开始的无限路径族（πε）ε>0称为折扣最优，如果|每一个ε。|<ε for each ε.请注意，这并不意味着从一个给定的状态存在一条折扣最优无限路径，而折扣最优路径族的最后一个定义就是这样的。我们现在能够在本文中说明我们所关心的问题问题2.5（折扣最优价格问题）给定一个定价的时间转移系统及其一个状态s，计算Pmin（s），如果它存在，从s计算一个折扣最优无限路径，或者从s计算一个折扣最优无限路径族。我们将证明，对于由定价时间自动机产生的定价时间转移系统第3节，上述问题是可从自动机的初始状态计算的3折扣定价时间自动机回想一下[14]，一个定价的时间自动机，或简称PTA，是一个元组A=（Q，C，I，E，p，r），其中Q是一个有限的位置集，C是一个有限的时钟集，I：Q→=182联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179H，Jx≤，`3x= 3\ndegx←0z，M，Jx≤，`3x= 3degz，Lz，z≤8，p=2z≤8， p= 1J，n≤z≤`，8\nR= 9R= 2 x，z←0attz≥2R= 5 x，z←0attz≥2Fig. 1. 生产系统的定价时间自动机PS。Φ（C）位置不变量，E<$Q× Φ（C）×2C×Q是一组转移，p：E→转移价格，r：Q →位置价格率。这里，时钟约束的集合Φ（C）由语法定义：：：= x Da k |x − y D a k |2（x∈C，k ∈ ，DA∈ {≤，<，≥，>}）例3.1图1的定价定时自动机PS模拟了一个生产系统，该系统可以在三种不同的模式下工作：高（H）、中（M）和低（L）模式，它们分别具有不同的相关价格率：2（H）、5（M）和9（L）。位置中的不变量强制操作模式从H到M和从M到L自动降级（度），除非在3个时间单位内执行注意动作（att）。时钟z上的警卫对连续注意动作进行建模，需要2个时间单位的最小时间间隔。此外，专注的行为需要一定的成本：1（从L升级到M）和2（从M升级到H）。Q利用定价时间变迁系统，给出了定价时间自动机的操作语义回想一下[2]，由时间自动机A=（Q ，C，I，E）（没有价格）生成的时间转移系统（S，T=Ts<$Td）定义为：.C.ΣS= （q，ν）∈Q ×≥0. ν |= I（Q）.JJ.Sj j，Sj，SJ，SjTs=（q，ν）→（q，ν）. q−−→q ∈E：ν|=，ν = v [S ← 0].t.JJTd=（q，v）−→（q，v+t）. n∈[0，t]：v+t|=I（q）定义3.2PTAA =（Q，C，I，E，p，r）的语义是PTTSA）=（S，T，p，r），其中（S，T）是由时间数据A生成的时间和时间数据集，以及时间数据集的函数：Ts→≥0，r= 0：S→≥0aredefineed如.S.J.Σp<$（q，ν）→（qJ，νJ）=p（q−−→qJ）r（q，ν）=r（q）例3.3重新考虑图1中的生产系统。以下交替循环行为提供了一个无限路径（PS）：（H，x=0， z=0）−→3 （H，x= 3， z= 3）−→（M，x= 0， z= 3）−→3（M，x=3， z=6）−→（L，x=3，z=6）−→1（L，x=4， z=7）−→联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179183（M，x=0，z=0）−→2（M，x=2， z=2）−→（H，x=0， z=0）使用λ=e−1，该无限路径的折扣价格p是唯一解184联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）1791w0W下面的公式：p= 2（1−e−3）+5（e−3−e−6）+ 9（e−6−e−7）+e−7+5（e−7−e−9）+2e−9 +e−9p其可以计算为p= 2。16.Q在本文的其余部分，我们必须对我们考虑的定价时间自动机以及贴现因子λ做几个• 我们需要λ是一个有理数。• 我们需要我们的定价时间自动机是有界的，也就是说，存在M∈使得对于A）中的每个可达状态（q，ν），以及对于A的每个时钟x，ν（x）≤M。根据[14]的结果，每个PTA都与有界PTA强价格双相似。• 我们需要我们的定价时间自动机中的所有无限次运行都是时间发散的：当t=0时， st0→s−t→1 st1→·· ·isa n initerun，ten int∞t→∞.0011i=0i前两个假设是很自然的，但第三个可能需要一些注释;我们在这里排除了Zeno运行，这对某些应用程序来说可能是有问题的我们关于时间发散的假设是技术性的，在引理5.2和7.4的证明中是需要的。使用其他证明技术，很可能在不排除Zeno运行的情况下显示我们的结果-但请注意，在无限最优调度的极限比方法中[8]，必须做出类似的强奖励发散我们现在可以陈述本文的主要结果，我们将在其余部分证明：定理3.4折扣最优价格问题对于时间发散有界价格时间自动机和有理λ的初始状态是可计算的。4有限权图为了计算定价时间自动机中的折扣最优无限路径，我们将问题简化为计算有限加权图中的折扣最优无限路径。这个问题又是[5]中讨论的折扣支付博弈在本节中，我们给出了我们所依赖的[5]的结果;关于约简，见第5节。设G=（S，T，w，d）是一个有限权图，w：T→权函数，d：T→折扣函数[0，1]，且G的任何一个都是有限权图在S中的Vertex有可能导致T中的Geuingeuing。Foranifinitepathπ=s0−→s−w→1D1Σ···，设π的折扣价格为数字P（π）=∞.i=0id0i−1j=0对于s∈S，设Pmin（s）是从s开始的路径的最小折扣价格，假设从s出发的无限路径π是折扣最优的，如果P（π）=Pmin（s）。ΣDJ.联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179185≥0Σν∈≥0≥0≥0引理4.1（[5]）值Pmin（s1），.，Pmin（sn），其中S ={s0，.，sn}，可以在O（mn2 log m）强多项式时间内计算，其中m =|不|.折扣最优路径可以通过给每个s∈S分配一条边来获得s−→wD 其中Pmin（s）= w + dPmin（sJ）。注意，上面我们允许贴现函数d：T→T]0， 1]假设值为1，而[5]要求d总是严格小于1.这导致了对我们来说，无限路径的贴现价格可能不会收敛，但是不难看出，在这种情况下，[5]的结果也成立。5区域和角点抽象我们通过将PTA的状态空间减少到有限加权图来展示折扣最优价格的可计算性，其角点抽象在[8]中介绍。 我们使用有界区域的标准概念，参见例如[2];这里，[·和·分别表示整数部分：给定有限个时钟集合C，区域等价定义在C上通过vvJ当且仅当• [ν（x），且= 0 iνJ（x）= 0，对所有x∈C，且• 对所有的x，y∈C，都有≤νJ（x）≤.我们将由M∈定义的块进行分类，并将其分类为。我是一个很好的朋友。nedbyM∈在有限时钟集C上记为RC，M=C. v（x）≤M对所有x∈C/的。给定一个区域R ∈ RC，M和一个时钟约束<$∈ Φ（C），我们说R |=如果ν|对于所有v∈R， 给定一个子集S<$C，我们用R[S<$0]表示S中时钟重置为0的区域，由ν∈R惠ν[S<$0]∈R[S<$0]给出。另一个区域RJ∈RC，M称为R的直接时间后继，记 为RJ= succ（R）， 如果对所 有νJ∈RJ 存在 d∈≥0使得νJ−d∈R ，且 对所有0≤dJ≤d，νJ−dJ∈R<$RJ。 区域R∈RC，M的角点集为cp（R）={ν∈cls（R）|v（x）∈对于所有x∈C}，其中cls（R）表示 R在C中赋值的典型识别下的（拓扑）闭包其中，|C|.定义5.1定价时间自动机A=（Q，C，I，E，p，r）的角点抽象是加权图cp（A）=（S，T，w，d），定义如下，其中箭头上的上标和下标分别表示折现的权重186联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）1795（1−e−1）λ86420e−110 1 2 3H HH0 0 01 1 1M MM01e−1M M因素d：图二. 拐角中的示例路径 点表示.C.ΣS=（q，R，α）∈Q×RC，M× ≥0. R |= I（q），α ∈ cp（R）.WJJJ.Sj，T=（q，R，α）−→（q， R，α）。q−−→q1∈E：R| = 0，ΣRJ=R[S<$0]，αJ=α[S<$0]，w=p（q→qJ）.W.1Σ<$（q，R，α）−→（q，R，α+1）. w=r（q）lnλ（λ−1）.0J。JJ<$（q，R，α）−→（q，R，α）. R1= succ（R），α∈cp（R）<$cp（R）因此，角点抽象是标准区域图的细化[3]，其中还跟踪区域的角点。在cp（A）中的转变上的权重和贴现因子的动机如下：• 跃迁（q，R，α）→（qJ，RJ，αJ）对应于开关跃迁（q，v）→（qJ，νJ），其中ν∈R，νJ∈RJ.• Transition s（q，R，α）→（q，R，α+1）correspondtodelay s（q，ν）−→1（q，v+1）.• 跃迁（q，R，α）→（q，RJ，α）的引入仅用于我们的有界性假设，以及在给定定价的时间自动机中所有无限次运行都是时间发散的假设，现在允许我们得出以下结论：引理5.2角点抽象是一个有限加权图，其性质是它的任何顶点至少有一条向外的边。状态s=（q，ν）和路径π=（q0，ν0）的角点表示→（q1，ν1）→. ·· ·inA. ）状态的一个集合，paths的一个特定集合，incp（A）givivenbycp（s）= （q，R，α）。v∈R，.cp（π）=（q0，R00，α00）→（q0，R01，α01）→···→（q0，R0r0，α0r0）.Σ→（q1，R10，α10）→···. i：νi∈ Ri0例5.3图2显示了第4页给出的无限路径的角点表示的一部分。当λ = e−1时，从（H，x = z = 2）开始到（M，x = 1，z = 4）结束的这一段的贴现价格为5（19（1−e−1）0联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179187−e−1）+ 9（1 −e−1）e−1<$5。25.Q188联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179Σ6指数函数在下一节中，我们将证明，角点抽象对于路径的折扣价格是合理和完整的。完备性证明依赖于定义在无限维区域上的某些函数的最小化;我们将在下面证明，定义在无限维区域上的指数函数的无限线性组合在该区域的一个角上达到其最小值。这一结果的证明依赖于一个新的定理最小化无穷和定义在闭集和有界集上的正值函数∞..Σ我们认为∞=配备 的 ∞-度量 d（x1，x2，. ），（y1，y2，. ）超级i|xi−yi|，并且说，如果关于这个度量是闭的，则∞中的一个集合是闭的。同样，我们让pr i表示到第i个坐标的投影。定理6.1设Z ∈∞是闭有界集，f1，f2，…连续函数序列fi：pri Z →≥0。 设f：Z →≥0 <${∞}为函数，∞由f（x1，x2，. ）=i=1 fi（xi），并假设存在x ∈ Z，其中f（x）的值。 然后，在Z上的f的最小值在Z的一个点上得到。我们注意到，对于某个n∈， 用 n 代 替 ∞ ，定理是平凡的;在这种情况下，Z是紧的，因此这个主张可以通过某种收敛子序列类型的论证来证明。困难在于，在∞中，闭性并不意味着紧性。证据在这个证明中，我们使用函数符号表示序列，因此Z中的点的序列（xi）i∈将被写为函数x：→Z。设a =inf {f（x）|x∈Z}，设x：→Z是满足limi→∞f（x（i））= a的点列.注意，x是序列的序列; x： →（→）。如果Z是紧的，我们可以找到x的一个收敛子序列，这个子序列的极限就是我们要找的点。现在Z不是一般的紧凑，但是所有的投影prjZ到坐标也是紧凑的，因此我们可以使用坐标方式的参数：设y = pr 1x = x（·）（1）. 所有x（i）（1）都是pr1Z的元素，pr1Z是紧集，因此y包含一个收敛于极限z1 ∈ pr1Z的子序列x（1（·））（1）.在此，请参见第1条：→是严格递增的重索引函数。 该子序列因此x的x1具有pr1（x1）收敛于z1∈ pr1Z的性质。一个简单的例子是，对于所有j=1， . . ，k. Lety=prk+1（xk）=x（k（·））（k+ 1），则y是pr k+1Z中的序列，因此紧性包含收敛子序列x（k（·））（k + 1），极限zk+1∈pr k+1Z. 设k+1=k，归纳就结束了。设z =（z1，z2，. . ）∈Z，则我们声称f（z）收敛于值f（z）=a：我们有f（x（i））= lim克Limfj（x（i）（j））= lim克Limfj（x（i）（j））i→∞i→∞k→∞ j=1k→∞i→∞ j=1联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179189≥0Σ最后一个等式，因为级数中的所有项都是非负的，因此收敛是绝对的。 对于内部极限，定义g：→克f（x（i）（j））。k≥0bygk（i）=j=1j则存在limi→∞gk（i），因此我们可以用其子序列gkk代替gk，并且limi→∞gk（i）=limi→∞gk（∞gk（i））.另一方面，对于所有j = 1，.，k，因此通过连续性，克j=1fj（zj）=limi→∞克j=1fj（x（i））（j）= limgk（i）i→∞收集碎片，我们有一个Limg（i）=lim克f（z）=k→∞i→∞kk→∞j=1J Jf（z）。Q类似于有限的情况下，cf。[2]，我们在无限个时钟集合C ={x1，x2，. }是基本时钟约束xiDa k，xi−xjDa k的（可能无限）集合，并且我们说，对于赋值ν：C → ≥0，如果ν ∈ Z，|对于所有的Z，无限区域很容易用∞的子集来标识，并且，再次用∞-度量来装备∞，我们就有了闭区域的概念。我们注意到，一个区域在这个意义上是封闭的，当且仅当它的所有定义时钟约束是封闭的，即只使用非严格不等式。推论6.2设Z∈∞是闭有界区域，f1，f2，..单调连续函数序列fi：priZ→≥0。令f：Z→≥0{∞}∞是由f（x1，x2，. ）=i=1fi（xi），并假设存在x∈Z，其中f（x）收敛。 然后，在Z上的f的最小值在a中得到，Z的角点证据由定理6.1，我们有z∈Z，其中f（z）是f在Z上的最小确界。现在假设z不是Z的角点。有两种情况需要考虑：(i) 存在z和ε > 0的坐标z j，使得对于所有t∈[−ε，ε]，点z+ jt：=（z1，.，zj+t，. ）∈Z.（因此，j是z不是角的坐标，在这种情况下，该坐标中的边平行于xj轴，对应于xj变量的绝对但后来Σ∞f（z+jε）=i=1i/=jciλzi+cjλzj+ε+cf（z）(ii) 存在z和ε的坐标zj，zl，使得对于所有t∈[−ε，ε]，点z+ j，lt：=（z1，.，zj+ t，.，zl+ t，. ）∈Z. (This对应于xj−xl上的对角约束）。但后来Σ∞f（z+j，lε）=i=1ciλzi+cjλzj+ε+clλz<$+ε+cf（z）i j，l在这两种情况下，我们得到一个矛盾，因此z必须是Z的角点。190联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179XΣ7角点抽象是健全和完整的我们现在能够证明，PTA中的任何无限路径都可以近似为角点抽象中的无限路径，其贴现价格不高于原始价格，反之亦然，角点抽象中的任何无限路径都可以近似为PTA中的一族无限路径。定理7.1（角点抽象的合理性）给定一个PTA A和一个pathπ∈cp（A）， P（π）c。一般来说，对于所有ε>0，π∈cp−1（π）forrwhich. P（π）−P（π）。 <ε。如果π是从cp（A）的初始区域开始的，则π从cp（A）的初始状态开始。在证明之前，我们需要一些技术引理，其中第一个引理来自[8]。给我7分。2（[8，Prop. 5]）Letπ=（q， R， α）−k→0 （q，RJ， α+k）→（q，R， α）−k→10 0 000001 1 1···是cp（A）中 的 无 限 路 径 且ε> 0。那么就有一条无限的路π=（q， ν）−t→0（q， v+t）→（q， v）−t→1·· ·在<$A）中，uchtπ∈cp−1（π），并且0 0 0 001Σ1Σ|对于所有i。|<ε for all i. 这里，Ti=ij=0tj和Ki=ij=0kj。第二个引理可以很容易地通过对积分yλtdt：.xy.1.x引理7.3对于0 <λ<1和x，y ∈，.λ-λ≤2|ln λ|λ+ λ|.|.第三个引理是关于某个无穷和的收敛性，并使用了我们的时间发散假设：给我7分。4If（q， R， α）−k→0 （q，RJ， α+k）→（q， R，α）−k→1···是无限的0 0 0Σ∞00 001 1 1路，则和i=0λKi收敛。证据令Ki吉吉j=0kj，设M为cp（A）的状态数。 我们有对于所有i，Ki+M>Ki，因为否则在cp（A）中将存在芝诺循环，因此由引理7.2A中的芝诺循环，意味着A将违反时间发散假设。由于Ki都是整数，这意味着对于所有i ，Ki+M≥Kin<$M−1<$nλKi=M−1nλKiM+j≤. M−1λiλKji=0i=0 j=0i=0j=0这是一个几何级数，因此收敛。Q例7.5如下面的例子所示，假设时间发散不是足以确保上述总和收敛于A本身的任何无限路径：令π=（q， ν）−t→0 （q， v+ t）→（q， v）−t→1（1）在一条无限的道路上，0。0 0 0Σ 01 1ti=1lni− ln（i−1）=联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179191lnλi=1i对于i≥2和t0=t1= 0。π是时间发散的，但是Ti=|ln λ|ij=0tj=−lni卢恩对于i≥1且T0= 0，因此i=0λTi = 1+n1，其中不收敛。Q192联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179.≥0.定理7.1的证明使用引理7.2的符号，我们可以选择任何ε1>0，得到一条路径π，|Ti−Ki|<ε1对于所有i。 根据引理7.3，. 我不是凯岛 1.我不是Ki1凯岛−ε1Σ. λ −λ. < ε1|ln λ|λ+λ2< 2ε1|ln λ|λ1+λ最后一个不等式是因为Ti>Ki−ε1。我们计算了π和πd的精确度的精确度：.... n-1。1 .一、Σ. P（π²2n）−P（π2n）的。=..i=0r（qi）|ln λ|1λTi−λKi.- 是的.好吧+r（qi）|lnλ|λKi−1−λTi−1+pi λTi − λKi。.n-1。1美元。.≤i=0r（qi）|lnλ|+pi . λTi−λKi。n=11。.+i=0r（qi）|lnλ|. λKi−1−λTi−1。1 .一、1. .ΣΣ≤2ε1 1+λ−ε1i=0r（qi） +pi|lnλ|λKi+r（qi）λKi−1所有在BB中的内容都是由Lem提供的。 我是7岁。4itcon. 对于n→∞的值。一个简单的方法来处理ε 1的choice将使您感到不安。P（π）−P（π）。 <ε。Q定理7.6（角点抽象的完备性）给定PTA A和A 中 的p（h π），存在p（hπ） ∈cp（π）的p（h π），使得P（π）≤P（π）.我的律师。 Writeπ=（q， ν）−t→0（q， v+t）→（q， v）−t→1（q， v+t）→·· ·。In0 0 0 0 0 1 1 1 1 1情形P（π）i. s是有限的，我们没有什么可证明的，所以让我们假设P（π）是有限的。设pi=p（qi，νi+ti）→（qi+1，νi+1）=p（qi→qi+1），注意这不取决于t的值。与T=it和t= 0，我们有i ij=−1j−1不好意思 .tP（π）= f（T0，T1，. ）=的i=0λTi−1 p（qi，νi）−→i（qi，νi+t）+λtipiΣ∞=i=0.r（qi）1lnλ.ΣλTi−λTi−1Σ+λTipi其中，我们现在将π的价格视为变量函数f：∞→≥0联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179193我T0，T1，. .0，S0A1，S1S2， S2设q0−→q1−→q2−→···是A中生成π的一条路，设Ri是区域，其中νi∈Ri，并引入赋值νJ：C→≥0，由下式给出νJ（x）=Ti−Tm ax{j≤i|x∈S}，它是，νJ（x）是在时间上的一个时间差，它是在时间上的一个时间差iji重置.194联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179≥0我定义一个（闭有界）区域Z∞由约束条件Z={νJ∈cls（Ri）|i ∈}，则由推论6.2，f在Z上达到最小值，点β∈∞Z。定义赋值σi：C →≥0， 对于i= 0，1，... ，由σi（x）=βi−βm ax{j≤i|x∈Sj}。 Asβ∈Z，对于所有i ∈，我们有veσi∈cp（Ri） .在hπ∈cp（π）处构造一个新的算法是不可能的，因为它的计算量很大（qi，Ri）和其中的任意一个条件都是P（πi） =f（β）;我们参考文献[8]，以进行详细的讨论。 对于Z，β最小，则P（πθ）≤P（π）.Q8结论和今后的工作我们已经证明，角点抽象对于路径的折扣价格是合理和完整的，因此下面的算法可以应用于从给定价格的时间自动机A的起始状态中找到有限条路径（或此类路径的族）的折扣最优：(i) 构建cp（A）。(ii) Findiscount-optimalinitepathπp cp（A）.从最初的(iii) Finda d是count-optim a l i ni n i tep athπ∈cp−1（π），ora familyofsuch.有一些问题尚未解决。 我们的可计算性证明是基于区域和角点，并没有提供一个有效实现的基础。在[11]中，作者证明了有限次运行中的折扣最优允许一定的固定点特征，这与[14]中利用的定价区域的概念一起应该允许有效的，基于区域的算法来计算有限次运行中的折扣最优。此外，我们猜想，类似于有限加权图的设置[15]，当λ接近1时，折扣最优无限运行与具有最小极限比的无限运行重合，这应该为我们的结果与[8]的结果提供一定的统一。最后，人们还应该考虑将所提出的工作扩展到定价定时游戏的设置。引用[1] Abdedda？m，Y.， E. 作为一个r在一个dO。 M aler，Scheduingwithimedautomata，Theor. 我也是。 SCI.354（2006），pp. 272-300[2] Acetoo，L.， A. 如果我不这样做，K。 G. LARSENADJ. Srba，“R e a c t i v e S y s t e m s“，C a mb ri d g e U n i v e s i t y P r e ss，2007年。[3] 巴尔河和D. Dill，Automata for modeling real-time systems，in：Proc.17th Int. Coll. on Automata，Languages and Programming（ICALP322-335[4] 巴尔河，S. La Torre和G. J. Pappas，加权时间自动机中的最优路径，在：Proc.4th Int.Work。混合系统：计算与控制（HSCC'01），计算机科学讲义2034（2001），pp. 49比62[5] Andersson，D.，“Improved Combinatorial Algorithms for Discounted Payoff games,” Master’sthesis, Uppsala[6] Behrmann，G.，E. Brinksma，M. Hendriks和A. 生产调度的可达性分析- 案例研究，在：Proc. 第十九届国际并行和分布式处理系统。（ IPDPS '05 ） （ 20 05 ） 。联合Fauberberg，K.G.Larsen/Electronic Notes in Theoretical Computer Science 239（2009）179195[7] Behrmann，G.，A. Fehnker，T. Hune，K. G. Larsen，P. Pettersson，J. Romijn和F. Vaandrager，定价时间自动机的最小成本可达性，在：Proc.4th Int.Work。混合系统：计算与控制（HSCC'01），计算机科学讲义2034（2001），pp. 147-161[8] Bouyer，P.，E. Brinksma和K. G. Larsen，Staying alive as cheaply as possible，in：Proc. 7th Int. Work.关于混合系统：计算与控制（HSCC'04），计算机科学讲义2993（2004），pp. 203-218[9] Bozga，M.，A. Kerbaa和O. Maler，在并行机上调度非循环分支程序，在：Proc. 第25届IEEE实时系统Symp. （RTSS '04）（2004），pp. 208-217[10] Brinksma ， E. ， A. Mader 和 A. Fehnker ， PLC 控 制 计 划 的 验 证 和 优 化 ， J. Software Tools forTechnology Transfer（STTT）4（2002），pp. 21比33[11]法恩伯格大学和K. G. Larsen，Discounting in time，in：Proc.7th Work。 编程语言的定量方面（QAPL'09），理论计算机科学电子笔记（2009），出现。[12] Henzinger，T.一、R. Majumdar和V.S. Prabhu，量化定时系统之间的相似性，在：Pettersson和W. Yi，editors，Proc.3rd Int. Conf. on Formal Modeling and Analysis of Timed Systems（FORMATS226-241.[13] Hune，T.，K. G. Larsen和P.Pettersson，Guided synthesis of control programs using UPPAAL，in：Proc. IEEE ICDS Int. 工作 分布式系统验证与确认（2000），pp。E15-E22[14] Larsen，K.G.，G. Behrmann，E.Brinksma，A.Fehnker，T.Hune，P.Pettersson和J.Romijn，尽可能便宜：定价时间自动机的有效成本最优可达性。第十三届国际Conf. 计算机辅助验证（CAV'01），计算机科学讲义2102（2001），pp. 493-505[15] 兹维克，U.和M. Paterson，平均支付博弈的复杂性，在：D.- Z. Du和M. Li，editors，Proc. 1st Int. Conf.on Computing and Combinatorics（COCOON1比10