Virtual symmetry reduction
Virtual symmetry reduction
复制标题
虚拟对称性降低
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Richard J. Trefler
中科院分区：
文献类型：
--
作者：
E. Emerson;John Havlicek;Richard J. Trefler
我们提供了一个一般的方法，改善状态爆炸通过对称性约减在某些非对称系统，如系统有许多类似的，但不相同的过程。该方法适用于其结构（即，状态转移图）具有比弧对称更多的状态对称性。我们引入了一个新的概念“虚对称”，严格地包含了早期的概念“粗糙对称”和“近对称”（爱默生和Tünier，1999）。虚对称是一个系统的结构与它的商通过一组状态对称自然双相似的最一般的条件。我们给出了几个示例系统表现出虚拟对称性，不服从对称性减少由早期的技术：一个车道的桥梁系统，其中的方向与优先级交叉动态变化;一个抽象的系统与不对称的通信网络;和一个系统与不对称的资源共享的动机从饮酒的哲学家的问题。这些例子表明，虚对称约化适用于比以前可以处理的更广泛的一类非对称系统。
We provide a general method for ameliorating state explosion via symmetry reduction in certain asymmetric systems, such as systems with many similar, but not identical, processes. The method applies to systems whose structures (i.e., state transition graphs) have more state symmetries than arc symmetries. We introduce a new notion of "virtual symmetry" that strictly subsumes earlier notions of "rough symmetry" and "near symmetry" (Emerson and Trefler, 1999). Virtual symmetry is the most general condition under which the structure of a system is naturally bisimilar to its quotient by a group of state symmetries. We give several example systems exhibiting virtual symmetry that are not amenable to symmetry reduction by earlier techniques: a one-lane bridge system, where the direction with priority for crossing changes dynamically; an abstract system with asymmetric communication network; and a system with asymmetric resource sharing motivated from the drinking philosophers problem. These examples show that virtual symmetry reduction applies to a significantly broader class of asymmetric systems than could be handled before.