没有合适的资源?快使用搜索试试~ 我知道了~
同步化自动机:平面游戏与复杂性的研究
M×Q可在www.sciencedirect.com在线获取理论计算机科学电子笔记339(2018)85-97www.elsevier.com/locate/entcs关于同步、对策与平面自动机的Juan Andres Montoya胡安·安德烈斯·蒙托亚1,2 克里斯蒂安·诺拉斯科3Dep artamentodeMatem'aticasUniversidad Nacional deColombiaBo got'a,Colombia摘要研究了平面自动机上的同步对策。我们证明,识别平面游戏,可以赢得的同步器是一个co-NP困难的问题。我们证明了一些额外的结果表明,平面游戏是很难的非平面游戏。这些结果表明,平面自动机是复杂的自动机同步的代表。关键字:同步化自动机,同步化博弈,C·N·Y猜想。1介绍本工作涉及确定性有限状态自动机(简称DFA)的同步。我们研究了在平面自动机上进行的同步游戏(见[2]回想一下,DFA是三元组M=(QM,δM,δM),使得:• QM是一个有限集合,是自动机M的内部状态的集合。• M是一个有限的字母表,M的输入字母表。• δM是M的转移函数,它是从M×QM到QM的函数.设M=(QM,δM)是DFA. 我们用系统分析仪来表示在alpha betboundaryM上的有限字符串。函数δ^M:MM→QM,定义1第一作者感谢哥伦比亚国立大学Hermes研究项目(代码8943(32083))提供的资金支持2电子邮件:jamontoyaa@unal.edu.co3电子邮件:cnolascos@unal.edu.cohttps://doi.org/10.1016/j.entcs.2018.06.0061571-0661/© 2018作者。出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。86J.A. 蒙托亚角Nolasco/Electronic Notes in Theoretical Computer Science 339(2018)85M通过等式:δ^M(w1. wn,q)=δM。wn,δ^M(w1. wn−1,q),确定当自动机M扫描字符串w1.. wn,从状态Q开始。我们说一个自动机M是同步的,当且仅当存在一个同步字符串w∈M,使得对于所有p,q∈QM,等式δ^M(w,p)=δ^M(w,q)保持。有许多与上述概念相关的作品(参见[6])。这些工作大多集中在短同步弦的研究设M是一个n态同步器,它同步一个utomaton. ,并设w为最短同步对于M,很容易证明,|W| ∈ O得双曲余切值.|W|表示w的长度。C. N.Y强调,|W| ≤(n−1)2,这就是著名的C.(见[6])。一个相关的概念是子集同步的概念。给定一个自动机M,给定q1,..., q k∈QM,这k个状态的同步串,是一个串w,使得对于所有i,j≤k,等式δ^M(w,qi)=δ^M(w,qj)保持。我们对子集同步特别感兴趣。因此,我们决定研究子集同步游戏的新概念,专注于平面自动机。工作安排、贡献和与以往工作的关系这项工作分为三个部分。在第1节中,我们介绍了我们要研究的同步游戏,我们表明,以前在文献中研究过的其他一些游戏,例如可达性游戏(见[3]),是同步的特殊情况。 在第二节中,我们研究了最优博弈策略,专注于配对同步博弈。我们证明了一个二次上界,我们证明了这个二次界是最优的。为了实现后一个结果,我们展示了一系列的对同步的游戏,不能赢得的同步速度比给定的界限。我们观察到所构造的序列是平面的,然后我们问平面自动机是否是同步博弈的复杂性核心。在第三节中,我们研究了平面非同步自动机上的子集同步博弈。我们证明了它是co-NP难识别的平面游戏,同步器有一个胜利的战略,我们还证明了最长的可能的游戏,关于平面自动机这项工作与调查有关,C.N.Yn3J.A. 蒙托亚角Nolasco/Electronic Notes in Theoretical Computer Science 339(2018)8587其中的引用)。我们选择研究[2]中引入的同步博弈的新概念。有一些以前的工作从博弈论的角度研究自动机的同步:Fominykh等人的上述工作[2]定义了一类与同步相关的新的可访问性博弈,而Gonze和Jungers使用博弈论技术来研究自动机的同步时间[3]。 我们推广了同步博弈的概念,这种推广使我们能够研究可达性博弈(见[3])作为我们博弈的一个特例。然后,我们专注于平面自动机上的同步游戏。我们决定专注于后一种类型的自动机,因为我们之前已经证明了这种特殊的自动机代表了同步的复杂性[4]。2同步游戏Volkov等人[2]介绍了一类与同步有关的自动机上的组合博弈。定义2.1同步博弈由三元组(M,Sc,Sp)给出,使得:(i) M是一个同步自动机,假设M =(Q,δ,δ)。(ii) Sc,Sp游戏是由两个竞争者,同步器和扰流板。游戏规则规定,在奇数轮,同步器必须从Sc中选择一个角色,而在偶数轮,破坏者必须从SP中选择一个角色。同步器的目标是产生(尽管扰流板的选择)一个同步字符串的M。扰流板的目的是避免同步。我们说博弈(M,Sc,Sp)是标准的,当且仅当等式Sc=Sp= Sp成立。我们说M是可赢的,当且仅当,同步器有一个标准博弈的获胜策略(M,N,N)。Volkov等人证明了存在不可赢的同步自动机[2]。后一种类型的自动机的 例 子 是Cernyautomata。这是很自然的一个问题:哪些是可赢的自动机?定义2.2子集同步博弈由4元组(M,Sc,Sp,A)给出,使得:(i) M=(Q,θ,δ)是一个同步自动机。(ii) Sc,Sp(iii) 一个小Q。同步器的目标是同步集合A。Volkov等人[2]证明了一个自动机M是可赢的,当且仅当同步器在集合中的同步博弈中有获胜策略{(M,n,n,{p,q}):p,q ∈ Q}.88J.A. 蒙托亚角Nolasco/Electronic Notes in Theoretical Computer Science 339(2018)85MM因此,我们说,减少对适用于同步游戏4。还可以证明(见下文)同步器对于游戏(M,Sc,Sp)具有获胜策略,当且仅当,他对于集合{(M,Sc,Sp,{p,q}):p,q∈Q},这意味着,对的简化也适用于非标准博弈。我们使用术语配对同步博弈来指代形式为(M,Sc,Sp,{p,q})的博弈。减少到对产生一个多项式时间算法的识别的游戏,赢得了同步器,以及立方上界的长度,他的最佳策略。后面的上界是从最优的配对同步对策的策略具有二次长度。 (see下面)。值得注意的是,同步游戏的研究可以有重要的应用。我们要注意的是,许多不同的组合博弈可以表示为同步博弈的特殊情况。这是古列维奇等人研究的可及性游戏的情况[3]。一个可达对策由一个三元组(G,v,A)给出,其中G是一个有限有向图,v是G的一个节点,A是一个节点集。这个游戏是由两个竞争者玩的,我们称之为爱丽丝和鲍勃。在游戏开始时,一个代币被放置在节点v上。爱丽丝选择一条向外的边,比如(v,u)∈E(G),代币沿着这条边移动,被放置在节点u上。然后,Bob选择从u出去的边,并一致地移动令牌。游戏以这种方式继续,爱丽丝在奇数轮玩,鲍勃在偶数轮玩。Alice的目标是将令牌放置在集合A中包含的节点上。设G是一个k度正则有向图,即:设G的结点的出度等于k。给定v∈G,可以随机选择从v出去的边的线性排序。这样做与用字母{1,...,k}。它可以对G的所有节点同时进行。我们观察到,如果一个标签的所有边缘的G根据后一个程序,他得到一个自动机MG。假设我们已经构造了这样一个自动机。然后,我们可以添加一个新的节点s。给定一条边(v,a),使得a∈A,我们用一条新的边(v,s)替换这条边,并将(v,a)上的标签附加到(v,s)上。此外,给定i≤k,我们添加一个标签为k的循环(s,s)。我们注意到赢得(G,v,A)博弈和赢得标准博弈是一样(NG,{1,. k},{1,..., k},{v,s})。因此,可及性博弈(G,v,A)由后面的配对同步博弈正确地表示。现在假设G是非正则的,设k是G的节点的最大出度。给定v∈G,如果deg+(v) 2·n。 然后,存在两个奇数i j,C i= C j,|C i|= 2。如果同步器是发挥最佳,尽管这一点,他产生了一个循环,然后扰流板是迫使这个循环。扰流器可以多次迫使这个循环无限,而同步器没有获胜的策略(矛盾)。后一个矛盾表明,同步器赢得了游戏在不到2n+1步,前提是他能发挥最佳水平。⎝2⎠⎛n⎞人们自然会问,二次界2·λ λ是否是最优的。 我们证明了在这种情况下,我们构造了一个配对同步博弈序列,使得同步者对这些博弈有一个获胜策略,但是,序列中第n个博弈的最优博弈策略等于2·n-1。Q定理3.2上界2·n是最优的。是的。构造了一个配对同步对策序列{(Cn,Scn,Spn,{pn,qn})}n≥2.同步器有一个双赢的战略,游戏中的序列,但他需要时间2·100万赢得比赛(Cn,Sc n,Sp n,{pn,q n}). 首先,我们在集合{Cn:n ≥ 2}中定义自动机。 让n是固定的正整数。• 自动机Cn=(Q n,{a,b,c},δ n).• Q n={0,1,..., n − 1}。• 转换函数δn定义为:字母a表示有向循环0 → 1 →· ··→n− 1 → 0。字母b表示边的集合{(i,i):i/= 0}{(0, 1)},2J.A. 蒙托亚角Nolasco/Electronic Notes in Theoretical Computer Science 339(2018)8591ˇˇ⎛⎞⎝⎠2必须为该对选择最小同步字符串⎝2⎠1、[2]|.而字母c标记循环{(i,i):i = 0,1,., n − 1}。下图对应于自动机Cn的转移有向图。我们观察到,如果我们把α约束到集合{a,b}上,则自动机Cn就等于第n个Cerny自动机.回想一下,所有的Cerny自动机都是同步的,并且考虑到Cerny自动机是不可赢的。后面的事实表明,我们不能选择Sc=Sp= ψ。 我们想让同步器的工作变得尽可能容易,那么我们设置Sp ={c},并且Sc={a,b}。因此,同步器被限制为施加中性字符c,并且这意味着他不能停止同步器正在进行的同步工作。设p n= 1,q n=[n|. 如果同步器想要发挥最佳状态,2n到它。 让w1. w m是最小同步串,已知m=n(参见[5])。 最优策略的形式是w1cw2c. wn−1 cw n−2。它的长度等于2·n− 1。Q并根据92J.A. 蒙托亚角Nolasco/Electronic Notes in Theoretical Computer Science 339(2018)85值得注意的是,在上面的证明中构造的序列是平面的,这意味着所有这些游戏都是在平面自动机上进行的(自动机的过渡有向图是平面的,见[4])。我们问:平面自动机扮演什么角色?这些自动机代表了同步游戏的复杂性4同步对策与非同步平面自动机我们构建了一系列博弈,这些博弈表现出某种极端行为:赢得这些博弈是尽可能困难的。有趣的是,观察到所构造的序列是平面博弈的序列。这并不奇怪,考虑到我们以前对平面自动机同步的研究[4],从中我们可以得出结论,平面自动机代表了同步的复杂性。上述结构表明,平面自动机也代表了同步游戏的复杂行为(最难的游戏是平面游戏)。我们在这一节中研究一些与子集同步博弈相关的事实。一方面,我们限制了我们的调查范围集中在平面自动机。另一方面,我们通过考虑非同步自动机来扩展这个范围.在非同步自动机上玩的子集同步游戏一些不存在于C·N·Y的剧本。 首先,它可以是这表明,减少对不再有效。为了达到这个目的,展示一个自动机M=(Q,R,δ)和一个集合AQ就足够了,使得同步器对于A中包含的所有对都有一个获胜策略,但是对于集合A没有获胜策略。考虑自动机M=(Q,δ,δ),其定义为:(i) Q ={1,2,3,4,5}。(ii) n={a,b,c}。(iii) 转换函数δ由以下等式定义:δ(i,x)=i,若i=4,5且x=a,b,c,δ(1,a)=δ(2,a)= 4且δ(3,a)= 5,δ(1,b)=δ(3,b)= 5和δ(2,b)= 4,δ(2,c)= δ(3,c)= 5和δ(1,c)= 4。下图是自动机M的转移有向图。Notice that the set {1, 2, 3} cannot be synchronized, but notice also that thesynchronizer counts with a winning strategy for the standard games encoded by thepairs {1, 2} , {1, 3} and {2, 3}: He plays a in the game (M, {a, b, c} , {a, b, c} , {1, 2}) ,he plays b in the game (M, {a, b, c} , {a, b, c} , {1, 3}), and he plays c in the game(M, {a, b, c} , {a, b, c} , {2, 3}) .J.A. 蒙托亚角Nolasco/Electronic Notes in Theoretical Computer Science 339(2018)8593J2j−112N现在,减少对丢失,不清楚是否存在多项式时间算法来识别集合S={(M,N,A)},其中同步器赢得标准游戏(M,N,N,A)。定理4.1集合S是co-NP困难的。证据我们证明了TAUT是ptime可约的。回想一下,TAUT就是问题所在:• 输入:α,其中α是合取范式的公式• 问题:判断α是否是重言式。我们的还原与Eppstein的还原相似 令α =Ci(X2,X4,., X2n)i≤m是变量X 2的布尔公式,...,X2 n. 我们可以写条款C1(X1,…,X2 n)作为Y i <$···<$Y i,其中对于所有i ≤ m和所有j ≤ 2 n,则Y i∈ {X j,<$X j,o(X j)}。 符号o(X j)解释为:变量X j不会出现在给定的子句中。 请注意,我们选择了将公式对于所有i≤m和所有j≤n,等式Yi=o(X2j−1)保持。给定α,我们构造一个自动机Mα。M α的输入字母表等于{0,1}。 G(Mα)的节点集等于A1H· ··H A mH {c}(符号H表示不相交并集),其中:• A i={i1,., i2 n,i2 n +1}。转换定义如下:94J.A. 蒙托亚角Nolasco/Electronic Notes in Theoretical Computer Science 339(2018)85KKK..ΣΣM(k)的有向图,设sM(k)K首先,我们假设k≤ 2 n。如果a=1且Yi=<$Xk, o(Xk),δ(ik,a)=0⎪⎩c,如果a= 1且Yi=Xk,ik+1,如果a= 0且Yi=Xk,o(Xk),c,如果a = 0且Yi=<$X k.如果k= 2n +1,则δ(i2n +1,a)= i2n +1.此外,我们有,δ(c,a)= c.设置A α={11,.,m1}。我们观察到α是重言式,当且仅当集合Aα被所有的字符串u∈ {0, 1}2n同步。然后,如果α是重言式,同步器有一个非常简单的获胜策略(Mα,{0,1},{ 0,1},Aα):它可以随机玩。现在假设α不是重言式,存在 v2v4···v2n∈ {0 ,1}n 使 得 对 于 所 有 x1x3···x2n−1∈ {0 ,1}n , 碰 巧x1v2x3···x2n−1v2n不满足公式α。请注意,扰流板选择X2,., X2 n. 然后,如果破坏者选择按照字符串v2v4···v2 n来玩,他就赢了:字符串v2v4···v2 n发送一个代币,比如第k个代币,到状态k2 n +1。请注意,如果第k个令牌访问节点k2 n +1,则syn-就不可能实现时间同步。因此,我们有α是重言式,当且仅当同步器具有博弈的获胜策略(Mα,{0,1},{0,1},A α)。Q值得注意的是,对于所有α,所构造的自动机Mα是平面的。因此,我们得到S对平面自动机的限制也是co-NP困难的。 这一结果表明,平面自动机是同步问题的核心(见参考文献[4])。因此,如果一个人不固定一个上限的大小集同步,相应的算法问题变得困难。人们自然会问:如果我们固定这样一个上限,会发生什么?设k≥1,Sk为集合{(M,N,N,A)∈S:|一|≤k}。定理4.2对所有k ≥ 1,集合Sk可以在多项式时间内被识别。证据设(M,M,A)是S k的一个实例.给定M,我们可以在多项式时间内构造k-代数。eau touMato 设G为过渡等于集合{A∈Q:|一|= 1},我们有(M,G, G,A)∈ Sk,当且仅当,三元组G,A,sM(k)属于集合{(G,v,D):Alice赢得游戏(G,v,D)}。J.A. 蒙托亚角Nolasco/Electronic Notes in Theoretical Computer Science 339(2018)8595.克n.Σ我.Σnk对于所有i≤k,集合Bi等于q1,...,qpi,k1,.,kpi−1(i)Qn是集合B1<$B,2< $ ··<$Bk<${x}的不交并. 莫,让我们重新来过.我我我我我我1K上面的集合可以在多项式时间内很容易地识别(参见[3])。因此,我们有一个ptime减少到一个问题,属于类P(多项式时间),这意味着Sk也可以在多项式时间内识别Q我们已经证明了Sk可以是。在多项式时间内,我们也可以提供k子集同步对策的策略。这一事实的证明与定理3.1的证明非常相似。定理4.3假设同步器有一个获胜策略(M,Sc,Sp,A)∈ Sk,则同步器最多可在Onk步内获胜。人们自然会问:上述上限是最优的吗?定理4.4存在一个可赢k子集同步对策序列{(Mi,Sc i,Sp i,Ai)}i≥1,使得同步器需要时间Ω n来赢得对策(Mn,Sc n,Sp n,An).证据 设n是一个 大整数,设p1,..., p k是素数,使得2k ≤ p1<.
下载后可阅读完整内容,剩余1页未读,立即下载
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 保险服务门店新年工作计划PPT.pptx
- 车辆安全工作计划PPT.pptx
- ipqc工作总结PPT.pptx
- 车间员工上半年工作总结PPT.pptx
- 保险公司员工的工作总结PPT.pptx
- 报价工作总结PPT.pptx
- 冲压车间实习工作总结PPT.pptx
- ktv周工作总结PPT.pptx
- 保育院总务工作计划PPT.pptx
- xx年度现代教育技术工作总结PPT.pptx
- 出纳的年终总结PPT.pptx
- 贝贝班班级工作计划PPT.pptx
- 变电值班员技术个人工作总结PPT.pptx
- 大学生读书活动策划书PPT.pptx
- 财务出纳月工作总结PPT.pptx
- 大学生“三支一扶”服务期满工作总结(2)PPT.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)