命题动态逻辑（三）

并证明没有与它相当的PDL0公式。 因此，PDL具有比PDL0更具表现力的功率。 他们的论点实际上可以概括如下。 对于所有N≥0，让PDLN + 1是PDL的子集，其中程序可以包含测试A？ 只有当A是PDLN公式时才。 对于所有N≥0，Berman和Paterson认为PDLN + 1公式AN + 1定义

⟨while⟨whileπn⟩⟨πn⟩an，

其中A0 = P和π0=π并证明所有N≥0，没有与+ 1相当的PDLN公式。 因此，对于所有N≥0，PDLN + 1具有比PDLN更具表现力的功率。

4.2有逆转的PDL

CPDL是具有交谈的PDL的扩展。 它是自PDL开头以来被考虑的构造。 对于所有程序α，让α-1用语义代表新程序

XR（α-1）Y IFF YR（α）x。

匡威构造使我们能够表达关于当前第一所在州的事实以及落后于程序的原因。 例如，[α-1] a的装置，在执行α之前，a必须保持。 我们有

⊨a→[α]⟨α-1⟩a

⊨a→[α-1]⟨α⟩a

逆转构造的添加不会以任何显着方式改变PDL的计算属性。 通过添加以下Axiom模式的每个实例

（奥迪a8）

一个→[α]⟨α-1⟩a（a9的）

一个→[α-1]⟨α⟩a

对于PDL的验证系统，我们以扩展语言获得声音和完整的推动性谓词。 有关详细信息，请参阅Parikh [1978]。 CPDL具有小型型号，而（CPDL-SAT）是EXPTIME-CLEFED。

很容易注意到CPDL具有比PDL更多的表现力量。 要查看此，请考虑CPDL公式⟨π-1⟩1和LTSS m =（w，r，v）和m'=（w'，r'，v'），其中w = {x，y}，r（π）= {（x，y）}，w'= {y'}，r'（π）=∅和v（x）= v（y）= v'（y'）=∅。 自M，Y SAT⟨π-1⟩1，不是M'，Y'SAT⟨π-1⟩1，并且因为对于所有PDL公式A，它是M，Y SAT A IFF M'，Y'SAT A，那么显然没有PDL公式相当于⟨π-1⟩1。

4.3 PDL重复和循环

通过引入RPDL，我们已经暴露了第3.3节中重复的力量。 在这里，我们总结了关于RPDL的更多结果及其与重复计划概念的其他变化的结果。

关于RPDL的复杂性理论，Streett [1982]已经确定RPDL有有限的模型财产; 正是在A的长度中，每个RPDL满足公式A在尺寸的大小型号中是满足的。允许的自动机构学分允许得出结论，在确定性三次中可以解决问题（RPDL-SAT）指数时间（3-exptime）。 因此打开该近义（RPDL-SAT）的上限（RPDL-SAT）和简单指数时间下限的间隙被打开。 问题发现本身非常与计算机科学家越来越多的兴趣，在建立时间逻辑的复杂性，更具体地是由于kozen引起的（命题）模态μ微积分（MMC）[1983]，因为RPDL具有线性吹 - 向MMC翻译。 在Vardi和Stockmeyer [1985]中，显示了非确定性指数时间的上限。 在艾默生和贾特拉[1988]中，并在艾默生和jutla [1999]的最终形式，表明（MMC-SAT）和（RPDL-SAT）是EXPTIME-完成的。 如果我们添加第4.2节的Conferse Operator获取CRPDL。 （CRPDL-SAT）的复杂性仍然持续了几年，但也可以显示出exptime-ressime。 这是通过组合艾默生和jutla的技术[1988]和vardi [1985]，如在vardi [1998]。

在第3.3节中，我们已经定义了谓词∞，其中∞（α）意味着程序α可以具有非终止计算。 我们将LPDL调用通过增强PDL与谓词∞一起获得的逻辑。 显然，RPDL至少与LPDL一样表达; RPDL语言中的∞（α）的归纳定义是它的见证。 RPDL实际上严格富有表现力，而不是LPDL。 这是在Harel和Sherman的[1982]。 可以怀疑，RPDL和LPDL均具有比PDL更多的表现力。 通过证明RPDL和LPDL的一些公式建立了它，在PDL中没有等同的表达。 证据涉及过滤技术，该技术旨在折叠到有限模型的一点，同时留下某种公式的真实性或虚假性。 对于某些组PDL公式X，它在分组到等价类中，该类别满足X中完全相同的公式的LTS的状态。如此获得的状态等同类成为滤波器模型的状态，并且建立了转换适当地过他们。

通过仔细选择的集合FL（a）取决于PDL公式A（A的副配方的组合型的所谓的Fischer-Ladner闭合），LTS M的过滤产生有限滤液模型M'，使得A且才能在M在滤液中的等效类中满足，仅在M个U中满意。 （见Fischer和Ladner [1979]。）

我们现在可以考虑LTS M =（W，R，V）的过滤

w = {（i，j）：j和i整数，1≤j≤i}∪{u}

（i，j）r（π）（i，j-1）当1≤j≤i时

我（Π）（我，我）每我都有

v（p）=∅对于每个p∈φ0

在一个句子中，M在M中是什么，来自世界你，有一个无限数量的增长长度的有限π路径。 我们有M，U SAT¬Δπ和M，U SAT¬∞（π*）。 然而，对于每个PDL公式A，我们将在通过用FL（a）的过滤获得的模型中的模型中的uΔπ和ζ（π*）。 实际上，过滤必须折叠一些州并创建一些环。 因此，不存在可以表达Δπ的PDL公式，并且不存在可以表达∞（π*）的PDL公式。

还有其他方法可以使程序永远能够执行的断言。 例如，Danecki [1984A]提出了一个谓词Sloop，以限定能够进入强循环的程序，即：

v（单桅帆船（α））= {x：xr（α）x}。

让我们调用slpdl通过使用公式Sloop（α）增强PDL获得的逻辑。 RPDL和SLPDL基本上是无与伦比的：谓词Δ在SLPDL中不可知，并且谓词SLOOP在RPDL中不可知。 SLPDL没有有限的模型属性。 例如，公式

[π*]（⟨π⟩1∧¬sloop（π+））

只在无限LTS上满足。 尽管如此，Danecki [1984A]在确定性指数时间中建立了（SLPDL-SAT）公式的可解锁性。

4.4 PDL与交叉点

另一个构建体已经研究：程序的交叉点。 通过将程序添加到PDL，我们获取逻辑IPDL。 在IPDL中，对于所有程序α，β，表达式α∩β代表一个新程序用语义

XR（ανβ）Y IFF XR（α）Y和XR（β）y。

例如，如果我们在当前状态下执行α和β的预期读数，则存在满足A的两个程序可以到达的状态。结果，我们有

⊨⟨α∩β⟩a→⟨α⟩a∧⟨β⟩a，

但是，一般来说，我们有

不是⊨⟨α⟩a∧⟨β⟩a→⟨α∩β⟩a。

虽然方案的交汇表在PDL对人工智能和计算机科学的各种应用中很重要（例如，在并发的背景下），但多年来，PDL的证明理论和复杂性理论仍未开发。 关于IPDL的复杂性理论，当考虑有限型号物业时，出现困难。 实际上，构建体（α）可以在IPDL中表达。 在具有交叉点的命题动态逻辑中，它相当于⟨α∩1？⟩1。 因此，我们可以调整第4.3节SLPDL的公式，我们有那个

[π*]（⟨π⟩1∧[π+∩1？] 0）

只在无限LTS上满足。 换句话说，IPDL没有有限的模型属性。 Danecki [1984B]调查了IPDL的复杂性理论，并显示了决定（IPDL-SAT）在确定性的双指数时间中进行。 （在Göller，Lohrey和Lutz [2007]中介绍了现代证据由Fischer和Ladner获得[1979]仍然开放了二十多年。 2004年，Lange [2005]建立了（IPDL-SAT）指数空间的下限。 在2006年，Lange和Lutz [2005]在没有指数空间有限交替图测机器的单词问题的情况下，对IPDL的可满足问题的双指数 - 时间下限的证据证明了IPDL的双指数 - 时间下限。 在这种降低中，迭代构建体的作用是必不可少的，因为根据Massacci [2001]，无需测试的无迭代IPDL的可满足问题只是PSPace完整。 将匡威构造添加到IPDL，我们获取ICPDL。 ICPDL的可满足性问题已被证明是Göller，Lohrey和Lutz [2007]的2-Exptime-Termining。

关于IPDL的证明理论，当我们意识到没有交叉点的PDL语言“对应”到语义XR（ανβ）Y和XR（β）和XR（β））α∩β的y。 也就是说，例如，例如，不用例如同一方式，即分别对程序α;β和ανβ的语义的公理模式（A1）和（A2）“对应”。 出于这个原因，在Balbiani和Vakarelov开发的完整证明系统之前，PDL与交叉点的公理化打开[2003]。

在另一种PDL的变体中，由于PELEG [1987]并通过Goldblatt [1992b]进一步研究，表达αχβ并联作用“α和β”。 在此上下文中，二进制关系R（α）和R（β）不再是具有x和y世界的形式（x，y）对，而是与x个世界和一组世界的形式（x，y）成对一组。 它受到Parikh [1985]的游戏逻辑的启发，将PDL的融合与“作为游戏的计划”进行了融合。 游戏逻辑提供了一个额外的程序构造，即两种程序，从而允许将程序定义为程序之间的非确定性选择的双重。

结论

本文专注于命题动态逻辑和其一些重要的变体。 现在有许多书籍 - 戈德布拉特[1982]，戈尔布拉特[1992A]，哈尔[1979]和哈尔，苏格兰和蒂尤[2000] - 调查论文 - 哈尔[1984]，苏Tiuryn [1990]，Parikh [1983] - 治疗PDL和相关形式主义。 普拉特在普拉特[2017]关于发展的动态逻辑的非正式和个人视角，也具有历史价值。 对PDL的研究机构当然有助于开发系统动态的许多逻辑理论。 但是，这些理论可以说是出于本文的范围。 van Eijck和Stokhof [2006]是更新的主题概述，利用动态逻辑，解决了哲学家某种兴趣的各种主题：例如，通信的动态或自然语言语义。 最近的书籍正在进行有关较新主题的详细信息，例如Van Ditmarsch，Van der Hoek和Kooi [2007]的动态知识逻辑（动态认知逻辑），以及连续和混合系统（差分动态逻辑）的动态逻辑Platzer [2010]。 PDL主要是为了推理计划的构思。 莫代逻辑有许多其他应用程序的推理。 算法逻辑更接近PDL，因为它允许一个人明确地说话。 邀请读者咨询Mirkowska和Salwicki的工作[1987]。 时间逻辑现在是理论计算机科学的主要逻辑，并与程序逻辑密切连接。 它们允许人们用摘要远离标签（因此程序）来表达转换系统的时间行为。 参见“施奈德[2004]概述了本研究领域的基础。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。