{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T23:31:11Z","timestamp":1673307071951},"reference-count":42,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T00:00:00Z","timestamp":1236124800000},"content-version":"unspecified","delay-in-days":5847,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[1993,3]]},"abstract":"<jats:p>We focus attention on a language \u2112 generated by a set of elementary actions under operations of sequential composition, external binary choice, iteration, and non-nested disjoint parallel composition: that is, on an especially simple parallel language without explicit internal, or \u2018local\u2019, nondeterminism. \u2112 is nondeterministic, despite the restriction to external choice, since a given action may occur in both subterms <jats:italic>F<\/jats:italic> and <jats:italic>G<\/jats:italic> of the parallel composition <jats:italic>F<\/jats:italic> \u2551 <jats:italic>G<\/jats:italic>. We exhibit a single set of equations that axiomatizes both step bisimulation and pomset equivalence on \u2112 Given that step bisimulation and pomset equivalence are incomparable on the language \u2112<jats:sup>+<\/jats:sup> obtained from \u2112 by relaxing just the constraint on choice, the coincidence of these equivalences on \u2112 suggests that the elimination of explicit internal choice can result in simplifications at the semantic level. We reinforce this impression by showing for \u2112 that step bisimulation (i) coincides with pomset bisimulation equivalence, (ii) is real-time consistent, and (iii) has step trees as concrete representatives of its equivalence classes. Moreover, we show that none of these results holds for the language \u2112<jats:sup>+<\/jats:sup> Finally, step trace equivalence is proved not to coincide with step bisimulation equivalence on \u2112.<\/jats:p>","DOI":"10.1017\/s0960129500000116","type":"journal-article","created":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T04:01:47Z","timestamp":1236139307000},"page":"25-62","source":"Crossref","is-referenced-by-count":8,"title":["Step bisimulation is pomset equivalence on a parallel language without explicit internal choice"],"prefix":"10.1017","volume":"3","author":[{"given":"Douglas R.","family":"Troeger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,3,4]]},"reference":[{"key":"S0960129500000116_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(87)90032-8"},{"key":"S0960129500000116_ref024","doi-asserted-by":"publisher","DOI":"10.1145\/3318.3322"},{"key":"S0960129500000116_ref010","volume-title":"On Concurrent Programs","author":"Brinch Hansen","year":"1987"},{"key":"S0960129500000116_ref020","article-title":"On the Relationship of CCS and Petri Nets","volume":"172","author":"Goltz","year":"1984","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref016","first-page":"267","volume":"430","author":"van Glabbeek","year":"1990","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref021","doi-asserted-by":"publisher","DOI":"10.1145\/359576.359585"},{"key":"S0960129500000116_ref009","first-page":"123","article-title":"On the Semantics of Concurrency: Partial Orders and Transition Systems. In: Proceedings TAPSOFT \u201887","volume":"249","author":"Boudol","year":"1987","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref011","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76369"},{"key":"S0960129500000116_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90016-1"},{"key":"S0960129500000116_ref029","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90112-2"},{"key":"S0960129500000116_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/BF01178506"},{"key":"S0960129500000116_ref028","volume-title":"Refinement","author":"Murphy","year":"1990"},{"key":"S0960129500000116_ref032","article-title":"Strong Bisimilarity on Nets: a New Concept for Comparing Net Semantics, Linear Time, Branching Time, and Partial Order in Logics and Models for Concurrency","volume":"354","author":"Olderog","year":"1989","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref025","article-title":"A Calculus of Communicating Systems","volume":"92","author":"Milner","year":"1980","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref013","doi-asserted-by":"crossref","unstructured":"Devillers R. (1991) Maximality Preservation and the ST-idea for Action Refinements, Technical Report LIT-242, Universite Libre de Bruxelles.","DOI":"10.1007\/3-540-55610-9_170"},{"key":"S0960129500000116_ref008","volume":"395","author":"Boudol","year":"1985","journal-title":"Notes on Algebraic Calculi of Processes"},{"key":"S0960129500000116_ref015","unstructured":"Gischer J. (1984) Partial Orders and the Axiomatic Theory of Shuffle, Ph.D. Thesis, Computer Science Dept., Stanford University."},{"key":"S0960129500000116_ref005","first-page":"416","article-title":"COSY: Its Relationship to Nets and to CSP","volume":"255","author":"Best","year":"1987","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref003","first-page":"445","article-title":"The Metric Space of Infinite Trees. Algebraic and Topological Properties","volume":"III","author":"Arnold","year":"1980","journal-title":"Annales Societatis Mathematicae Polonae"},{"key":"S0960129500000116_ref034","article-title":"Summary of a Workshop on Combining Compositionality and Concurrency","volume":"320","author":"Olderog","year":"1988","journal-title":"Arbeitspapiere der GMD"},{"key":"S0960129500000116_ref031","article-title":"Operational Petri Net Semantics for CCSP","volume":"266","author":"Olderog","year":"1987","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref038","article-title":"Finite Representations of CCS and TCSP Programs by Finite Automata and Petri Nets","volume":"369","author":"Taubner","year":"1989","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref037","doi-asserted-by":"publisher","DOI":"10.1007\/BF01379149"},{"key":"S0960129500000116_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80025-X"},{"key":"S0960129500000116_ref019","article-title":"CCS and Petri Nets","volume":"467","author":"Goltz","year":"1990","journal-title":"Arbeitspapiere der GMD"},{"key":"S0960129500000116_ref022","volume-title":"On the Construction of Programs","author":"Hoare","year":"1980"},{"key":"S0960129500000116_ref036","first-page":"381","article-title":"Some Equivalence Notions for Concurrent Systems","volume":"222","author":"Pomello","year":"1986","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref018","first-page":"224","article-title":"Petri Net Models for Algebraic Theories of Concurrency, PARLE","volume":"259","author":"van Glabbeek","year":"1987","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref002","article-title":"Full Abstraction for Series-Parallel Pomsets. In: Proceedings TAPSOFT 91","volume":"493","author":"Aceto","year":"1991","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref023","volume-title":"Communicating Sequential Processes","author":"Hoare","year":"1985"},{"key":"S0960129500000116_ref017","first-page":"309","article-title":"Equivalences and Refinement","volume":"469","author":"van Glabbeek","year":"1990","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref027","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90023-0"},{"key":"S0960129500000116_ref030","first-page":"89","article-title":"Degrees of Non-Determinism and Concurrency: A Petri-Net View","volume":"181","author":"Nielson","year":"1984","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref033","article-title":"Nets, Terms, and Formulas","volume":"23","author":"Olderog","year":"1991","journal-title":"Cambridge Tracts in Theoretical Computer Science"},{"key":"S0960129500000116_ref039","first-page":"348","article-title":"The Step Failure Semantics","volume":"247","author":"Taubner","year":"1987","journal-title":"Springer-Verlag LNCS"},{"key":"S0960129500000116_ref001","volume-title":"Eliminating Local Non-Determinism: A New Semantics for CCS","author":"Abramsky","year":"1981"},{"key":"S0960129500000116_ref040","first-page":"101","article-title":"Covering Morphisms and Unique Minimal D-Schemes","volume":"10","author":"Tindell","year":"1991","journal-title":"Ada Cybernetica"},{"key":"S0960129500000116_ref041","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90333-W"},{"key":"S0960129500000116_ref042","volume-title":"Mathematica","author":"Wolfram","year":"1988"},{"key":"S0960129500000116_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90031-8"},{"key":"S0960129500000116_ref026","doi-asserted-by":"publisher","DOI":"10.1145\/800220.806687"},{"key":"S0960129500000116_ref035","first-page":"167","article-title":"Concurrency and Automata on Infinite Sequences","volume":"104","author":"Park","year":"1981","journal-title":"Springer-Verlag LNCS"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129500000116","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T19:40:53Z","timestamp":1557949253000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129500000116\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,3]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1993,3]]}},"alternative-id":["S0960129500000116"],"URL":"https:\/\/doi.org\/10.1017\/s0960129500000116","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,3]]}}}