没有合适的资源?快使用搜索试试~ 我知道了~
加权时间转移系统中的折扣问题及其应用
∈理论计算机科学电子笔记253(2009)25-31www.elsevier.com/locate/entcs时间折扣Uli Fauberberg和Kim G. 拉森部丹麦奥尔堡大学计算机科学系电子邮件:{uli,kgl}@ cs.aau.dk摘要本文研究了加权定时转移系统中的折扣问题。贴现提供了一种建模无限次运行的最优成本问题的方法,并在最优调度和其他领域有应用。我们表明,当假设一个特定的自然可加性属性的折扣权重运行,基本上只有一种可能的方式来引入折扣语义。我们的证明依赖于这样一个事实,即某个函数方程本质上只有一个解,对此我们提供了一个初等证明。关键词:时间转移系统,时间自动机,加权时间自动机,定价时间自动机,折扣1引言贴现是经济学中一个众所周知的原理,一段时间以来也被用于最优控制[10]和博弈论[12]。 贴现未来意味着对即将发生的事件给予更多的权重,而对以后才发生的事件给予较少的权重。 因此,权重为w的事件对整体行为由g(t)w给出,其中g是递减函数,t是 事件发生的时间。对于某些λ]0, 1[(在经济学中的应用中由实际或预测利率给出),使用指数贴现g(t)=λt是标准的,但是先验的其他贴现函数是可能的。 在理论计算机科学中,贴现最近被引入到概率和一般定量系统中[7,8,9]。这些文献的观点都是上述观点,即未来时刻t的事件被λt贴现,并证明了所引入的贴现系统理论具有良好的性质。对于实时系统,折扣已在[13,14]和[11,17]中用于解决最优调度问题。在后面的这些论文中,加权定时自动机被用来对具有权重和定时信息的系统进行建模,采用贴现来测量无限路径的累积权重1571-0661 © 2009 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2009.10.00326联合Fauberberg,K.G.Larsen/Electronic Notes in Theoretical Computer Science 253(2009)⊆ × × →→→∈−→∈ ∈∈∈对于实时系统的建模和分析,如时间自动机[1],时间Petri网[15],时间CCS [16]和其他,时间变迁系统的概念作为基本的语义模型。对于具有权重和定时信息的模型的分析[2,3],这个角色由加权定时转移系统扮演当使用加权定时转换系统的折扣时,有几种选择。一个人可以通过步骤贴现,例如在[14,17],或通过经过的时间,例如在[11]。在前一种情况下,根据到达事件所需的步骤数对事件进行贴现;在后一种情况下,根据事件发生所需的时间进行贴现。本文的目的是证明,如果一个人需要一个特定的自然的可加性属性的折扣累计权重的运行,那么本质上只有一种方法来引入折扣加权定时转移系统的形式主义。第一作者希望向奥尔堡大学数学科学系的Arne Jensen和Martin Raussen表示感谢,感谢他们就第3节的主题进行了有趣的讨论。此外,作者感谢匿名裁判的一些有用的评论2加权定时转移系统定义2.1一个加权定时变迁系统(S,Ts,Td,w,r)由一组状态S,一组开关变迁Ts ∈S×S,一组延迟变迁Td组成。S≥0S,转换权重w:T s,并说明重量比率r:S. 延迟转换服从以下公理:• (s,0,s)∈Td对所有s∈S,• 对任意(s1,x,s2)∈Td和(s2,y,s3)∈Td,且(s1,x+y,s3)∈Td,• 对任意(s1,x,s2)∈Td且y≤x,存在s3∈S使得(s1,y,s3)∈Td且(s3,x-y,s2)∈Td,且• 只要(s,x,s1)∈Td且(s,x,s2)∈Td,则s1= s2.转换通常写为s→sJ和s−→xsJ,而不是(s,sJ)∈Tsrespec-(s,x, SJ)Td;一般(切换或延迟)转换将被表示为Q。切换转换的权重w(e)e=s sJ可以用于对进行该转换所需的资源量或通过进行该转换获得的资源量(如果为负)进行建模,并且状态s的权重率r(s)用于测量停留在该状态所需的(或再次通过停留获得的)每时间单位的资源量。我们说一个加权定时转移系统是延迟使能的,如果有s S和x>0使得(s,x,sJ)Tdfor some(necessarily unique)sJS. 这是一种自然属性;不启用延迟的加权定时转换系统是离散的。加权时间转移系统作为加权时间自动机的语义自然出现,参见[4,11]。我们在这里不关心它的精确表述;我们只注意到, 方式遵循以下有用的属性:联合Fauberberg,K.G.Larsen/Electronic Notes in Theoretical Computer Science 253(2009)27∈QQQQ→01n01Mn001n1M如果(S,Ts,Td,w,r)作为加权时间自动机A的语义出现,则S中的状态是由A的位置和其时钟的赋值组成的对。权重率仅取决于位置,延迟仅改变状态的估值分量,因此如果(s,x,sJ)Td,则r(s)=r(sJ)。当一个加权的定时转移系统服从这最后一个性质时,我们就说它具有延迟不变的加权率。加权定时转移系统T中的路径是(有限或无限)序列s0−→Qs1−→QS2−→Q···T中的swit ch和del ay转变。ThesetofallfiniteT中的路记为PT,如果π 1 = s1 − →Q s1−→Q·· ·−→s1,π2=s2−→Q S2−→Q·· ·−→S2 ∈PT,其中s1=s2,thenπ1<$π2=s1−→Qs1−→Q·· ·−→s1−→s2−→Q·· ·−→s2表示它们的连接。当采用加权定时转移系统进行最优调度时,使用权函数和速率函数来引入累积权函数 W:PT。在处理可达性最优调度问题时,例如,在[2,3]中,这种情况,但是对于无限最优调度,必须引入无限路径的累积权重作为其有限前缀的累积权重的限制,参见。[4、11、14]。有不同的方法来确保大多数路径存在上述限制,特别是[4]的商方法和[11,14]的(不同的)贴现方法等。这里的技术定义并不重要,因为我们感兴趣的是累积权函数的一个特殊性质,而不是它的精确公式:定义2.2如果存在函数g:≥0→,则称累积权重函数W:PT→在时间上被贴现,使得W(e<$π)=W(e)+g(x)W(π)对于所有的del ay转移e=s−→xsJ∈Td和e相容路π.因此,在时间上贴现的累积权重函数具有在引言中提到的性质: 根据(通常是递减的)折扣函数g被折扣了一个值g(x)。我们将在下面说明,对于实际中出现的加权定时转移系统,这个定义对如何定义累积权函数施加了严格的限制。请注意,该定义还意味着在时间上打折的累积权重函数具有有用的递归性质,可以用于计算。我们说,累积权重函数W:PT→这是折现的在时间上,在具有延迟不变加权率的加权定时转移系统T是自然的,如果W(s-→xsJ)对于所有的delay跃迁s-→xsJ仅依赖于s和x,并且如果W及其相关联的折扣函数g都是非平凡的,即不等于零。Q28联合Fauberberg,K.G.Larsen/Electronic Notes in Theoretical Computer Science 253(2009)0/§≡W(s−→s)=α(s)λ dt和g(x)=λ0定理2.3设T是具有时滞不变权率的时滞使能加权定时转移系统,W:PT→自然累积权函数其在时间上被贴现,具有相关联的贴现函数g:≥0→。 则存在λ∈>0和α:S→使得xJxt x对于所有lls∈S和所有ll延迟变换s−→xsJ。上面的定理意味着,如果人们对定义2.2的递归性质感兴趣,那么基本上只有一种可能的延迟累积权重定义。这也是[11]中的定义。 定理的证明依赖于下面给出的某个函数方程的解。3证明定理2.3将是下面关于某个函数方程的定理的一个简单推论该方程是著名的柯西方程的推广 f(x+y)=f(x)+f(y),在Cauchy [ 6 ]中给出了它的一个完全解此外,给出的证明只使用了柯西在1821年已经使用的方法;作者有兴趣看看这个方程是否可以更容易地使用一些更现代的方法来求解。定理3.1连续函数f,g:≥0→满 足 函数方程f(x+y)=f(x)+g(x)f(y)(1)当且仅当以下属性之一成立:• f(x)≠0,• f(x)≠k=0且g(x)≠0,或• f(x)=α<$xλ t dt和g(x)=λ x,其中α,λ∈,α=0且λ> 0.证据1. 函数f(x)0是方程(1)对于所有函数g的解。如果f(x)k=0,则k=k+g(x)k,因此对于所有x,g(x)=0。另一方面,如果对于某个x 0,g(x0)=0,则对于所有y,f(x0+y)=f(x0),因此f是常数。这给出了定理前两项的平凡解第2节。特殊情况g(x)<$1在[ 6 ]中得到了处理;对于这种情况,函数f(x)=αx,对于α ∈,是唯一的解。从现在开始我们可以假设f(x)/= 0对于某个x,g(x)1对于某个x,g(x)0对于所有x。第3节。 设x0使得f(x0)= 0。则f(x0+y)=g(x0)f(y)且f(y+x0)=f(y)对所有y,因此g(x0)=1。联合Fauberberg,K.G.Larsen/Electronic Notes in Theoretical Computer Science 253(2009)29§§.Σ∈KK§/∈i=0i=0另一方面,假设x0使得g(x0)=1。 则f(x0+y)=f(x0)+f(y),且f(y+x0)=f(y)+g(y)f(x0),由此我们假设f(x0)= 0.4. 通过在等式(1)中代入y = 0,我们得到f(x)=f(x)+g(x)f(0),对于所有x,因此f(0)=0。通过3,g(0)=1。在我们的假设下,这又意味着对所有x,g(x)>0,因为如果对某个x,g(x)<0,那么通过连续性,对某个y,g(y)= 0,这在§2中已经排除了。5. 设x>0,则通过对方程f((k+1)x)=f(kx)+g(kx)f(x)的归纳,我们得到f(kx)=f(x)k−1i=0g(ix)(二)对于所有k+。 另一方面,对 方 程 的类似归纳f((k+1)x)=f(x)+g(x)f(kx)导致对于所有k ∈+。f(kx)=f(x)k−1i=0(g(x))i(三)第6节。设x0>0,并假设f(x0)=0。然后通过等式(3),f(kx0)=0,对于所有k ∈+。现在设n,k∈+且x1=nx0,则0 =f(kx1)=f(x1)k−1i=0(g(x1))i(四)等式(3)。假设f(x1)/= 0,则g(x1)=1,由§3。因此,我们可以将等式(4)乘以1−g(x1),得到1−((g(x1))k=0。当g(x1)>0且g(x1)/= 1时,这是不可能的。我们已经看到,f(x0)=0意味着对所有n,k∈+,f(nx0)=0,因此f(αx0)=0,对于所有α ∈>0,连续性。 但是对于所有x > 0,f(x)=0,我们在第2节中已经排除了这一点。因此,对于所有x=0,我们必须有f(x)由§3,也是g(x)1,对于所有x=0。7. 对于x=0和k+,我们可以组合等式(2)和等式(3)并除以f(x)得到k−1k− 1g(ix)=通过归纳,这意味着对所有k∈+,§§.Σ.Σ30联合Fauberberg,K.G.Larsen/Electronic Notes in Theoretical Computer Science 253(2009)g(kx)=(g(x))k(5)第8节。 设λ = g(1). 在等式(5)中设置x=1,我们看到对于所有k∈联合Fauberberg,K.G.Larsen/Electronic Notes in Theoretical Computer Science 253(2009)31βK对所有的x∈[0,x],都有nxtα λ dt. s0=λk,k∈+. 通过连续性,g(x)=λK1 −λ+的版本。 若x=n,对n,k∈ +,则(g(x))k=g(kx)=λn,. nknxK第9节。设β=f(1).在等式(3)中设置x=1,f(k)=βk−1i=0λi=1−λk1 −λ对于所有k ∈+。 如果x=n,其中n,k∈+在同一方程中,则并且因此1 −λn1 −λ =f(kx)=f(x)k−1i=01(g(x))in=f(x)1 −λn1 −λxF. n=β−λk对所有n,k∈+. 通过连续性,f(x)= β1−λx1−λ 对所有x∈>0和设置α= βlnλ给出了所需的结果。λ−1定理2.3现在很容易得出:根据定理2.3。 设s∈Ssu ch使得s-x→0sJ∈TdQ对于某个x0∈>0,则对所有x≤x0有SJJ∈Ssu ch使得s−→xsjj∈Td。定义fs:[0,x0]→byfs(x)=W(s−→xsJ). 则fs(x+y)=fs(x)+g(x)fs(y)对所有x,y∈≥0其中x+y≤x0,定理3.1的证明的简单修改表明,这意味着我们有λ∈>0和αs∈,使得g(x)=λx和fs(x)=0剩下的唯一情况是考虑rarestatess∈S,其中chs−→xsJ仅对x=0,但是对于这些,定理的陈述是空的。Q4结论和进一步工作我们已经证明,如果人们希望在时间转移系统中的累积权重函数满足某种自然可加性性质,如定义2.2中所给出的,那么对于如何定义它只剩下很少的选择。特别地,[4]的商方法和[14,17]中的基于步骤的贴现都不会产生在时间上贴现的累积权重函数在时间上折现不仅是对累积权函数的一个自然要求,而且它还隐含着累积权的一个递归特征。因此,可以使用不动点计算来找到(有限或无限)路径的累积权重,并且还可以找到最优路径在某种意义上。 这反过来又有望对基于区域的算法在加权时间自动机中计算累积权重的可用性产生影响。.Σ.Σ因此g对于所有的x ∈≥0。β32联合Fauberberg,K.G.Larsen/Electronic Notes in Theoretical Computer Science 253(2009)引用[1] 巴 尔 河 和 D.Dill , A theory of timed automata , Theoretical Computer Science126 ( 1994 ) ,pp.183[2] 巴 尔 河 , S. L. Torre 和 G. J. Pappas , Optimal paths in weighted timed automata , TheoreticalComputer Science318(2004),pp.297-322[3] 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[4] Bouyer,P.,E. Brinksma和K.G. 拉森,尽可能便宜地活着,在:Proc. 第七届国际工作关于混合系统:计算与控制(HSCC'04),计算机科学讲义2993(2004),pp. 203-218[5] Cassez,F.和C. Jard,编辑,[6] 因 为 , A.- L. , “Cours d'analyze de l'Ecole ro y ale polyte chnique.Prem i`erepartie : Analysealg'ebrique,”Editions Jacques Gabay , Paris , 1989 , ( Reprin t of the 182 1 edition ) .[7] de Alfaro ,L.,M. Faella,T.A. 亨青格河Majumdar和M.Stoelinga,Model checking discountedtemporal properties,Theoretical Computer Science345(2005),pp.139-170。[8] de Alfaro,L.,M. Faella和M. Stoelinga,定量转换系统的 线性和分支度量, 在:J。 D'ıaz,J. KarhumakiA.Lepistú 和 D. Sannella , 编 辑 , P roc. 第 31 届 国 际 [ 医 ] 科 Automata , Languages andProgramming(ICALP 2004),Lecture Notes in Computer Science3142(2004),pp. 97[9] de Alfaro,L.,T. A. Henzinger和R. Majumdar,Discounting the Future in Systems Theory,in:J.C.M. Baeten , J.K. Lenstra , J. Parrow 和 G. J. Woeginger, editors , Proc. 30th Int. Coll. Automata ,Languages and Programming(ICALP 2003),Lecture Notes in Computer Science2719(2003),pp. 1022-1037.[10] Derman,C.,“Finite State Markovian Decision Processes,” Academic Press,[11] 法恩伯格大学和K. G. Larsen,Discount-optimal in finite runs in priced timed automata,ElectronicNotes in Theoretical Computer Science239(2009),pp.179-191.[12] Filar,J.和K.Vrieze,[13] 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[14] Jurdzinski,M.和A. Trivedi,凹价时间自动机,在:Cassez和Jard [5],pp. 48-62.[15] Merlin,P.M. 和D.J. Faber,通信协 议的可恢复 性:理论 研究的含义 ,IEEE Trans.Comm. COM-24(1976),pp.1036-1043。[16] Moller,F.和C. M. N. Tofts,通信系统的时间演算,在:J.C. M. Baeten和J.W. Klop,editors,Proc.1st Int. Conf. on Concurrency Theory(CONCUR401-415[17] Thrane , C. , 联 合 Fauberberg 和 K. G. Larsen , Quantitative analysis of weighted transitionsystems,Journal of Logic and Algebraic Programming(2009)。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 深入理解23种设计模式
- 制作与调试:声控开关电路详解
- 腾讯2008年软件开发笔试题解析
- WebService开发指南:从入门到精通
- 栈数据结构实现的密码设置算法
- 提升逻辑与英语能力:揭秘IBM笔试核心词汇及题型
- SOPC技术探索:理论与实践
- 计算图中节点介数中心性的函数
- 电子元器件详解:电阻、电容、电感与传感器
- MIT经典:统计自然语言处理基础
- CMD命令大全详解与实用指南
- 数据结构复习重点:逻辑结构与存储结构
- ACM算法必读书籍推荐:权威指南与实战解析
- Ubuntu命令行与终端:从Shell到rxvt-unicode
- 深入理解VC_MFC编程:窗口、类、消息处理与绘图
- AT89S52单片机实现的温湿度智能检测与控制系统
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功