Dynamic algebras: Examples, constructions, applications
Dynamic algebras: Examples, constructions, applications
复制标题
动态代数：示例、构造、应用
DOI：
10.1007/bf00370685
复制
发表时间：
1991
期刊：
影响因子：
0.7
通讯作者：
V. Pratt
中科院分区：
文献类型：
--
作者：
V. Pratt
动态代数将布尔代数（B∨' 0）和正则代数（R∪;*）组合成一个有限公化的代数（B R-），类似于带有“标量”乘法-的R模。基本的结果是*是自反的传递闭包，这与直觉相反，直觉认为这个概念应该需要量词来定义它。利用这一结果，我们给出了几个与加性函数、二元关系、状态轨迹、语言和流程图有关的自然产生的动态代数的例子。主要结果是自由动力代数是剩余有限的（即作为有限动力代数的子直接积的因子），重要的是因为有限可分动力代数与Kripke结构同构。应用包括对介词动态逻辑的Segerberg公理化的一个新的完备性证明，以及正则代数的另一个概念。
Dynamic algebras combine the classes of Boolean (B ∨ ′ 0) and regular (R ∪; *) algebras into a single finitely axiomatized variety (B R ◊) resembling an R-module with “scalar” multiplication ◊. The basic result is that * is reflexive transitive closure, contrary to the intuition that this concept should require quantifiers for its definition. Using this result we give several examples of dynamic algebras arising naturally in connection with additive functions, binary relations, state trajectories, languages, and flowcharts. The main result is that free dynamic algebras are residually finite (i.e. factor as a subdirect product of finite dynamic algebras), important because finite separable dynamic algebras are isomorphic to Kripke structures. Applications include a new completeness proof for the Segerberg axiomatization of prepositional dynamic logic, and yet another notion of regular algebra.