Linear vs. branching time: A semantical perspective

[摘要] The discussion of the relative merits of linear versus branching-time goes back to early 1980s. The dominating belief has been that the linear-time framework is not expressive enough semantically, marking linear-time logics as weak. Here we examine this issue from the perspective of process equivalence, one of the most fundamental notions in concurrency theory. We postulate three principles that we view as fundamental to any discussion of process equivalence. First, we take contextual equivalence as the primary notion of equivalence. Second, we require the description of a process to fully specify all relevant behavioral aspects of the process. Finally, we require observable process behavior to be reflected in input/output behavior. Under these postulates the distinctions between the linear and branching semantics tend to evaporate. Applying them to the framework of transducers, we show that our postulates result in a unique notion of process equivalence, which is trace based, rather than tree based.

[发布机构] Rice University

[效力级别] science