请输入您要查询的百科知识:

 

词条 Stuttering equivalence
释义

  1. References

{{technical|date=July 2012}}

In theoretical computer science, stuttering equivalence,[1] a relation written as

,

can be seen as a partitioning of path and into blocks, so that states in the block of one path are labeled () the same as states in the block of the other path. Corresponding blocks may have different lengths.

Formally, this can be expressed as two infinite paths and which are stuttering equivalent () if there are two infinite sequences of integers and such that for every block holds .

Stuttering equivalence is not the same as bisimulation, since bisimulation cannot capture the semantics of the 'eventually' (or 'finally') operator found in linear temporal/computation tree logic(branching time logic)(modal logic). So-called branching bisimulation has to be used.{{Citation needed|date=April 2012}}

References

1. ^{{cite book | first1 = Jan Friso | last1 = Groote | first2 = Frits W. | last2 = Vaandrager | url = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.1834 | chapter = An efficient algorithm for branching bisimulation and stuttering equivalence | title = Proceedings of the 17th International Colloquium on Automata, Languages and Programming | editor1-first = Michael S. | editor1-last = Paterson | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | volume = 443 | pages = 626–638 | year = 1990 | isbn = 0-387-52826-1 | doi = 10.1007/BFb0032063 }}
{{Comp-sci-theory-stub}}

2 : Formal methods|Logic in computer science

随便看

 

开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。

 

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间:2024/11/11 13:23:20