{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T02:15:49Z","timestamp":1648692949556},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2010,4]]},"abstract":"<jats:p> Message Sequence Charts (MSCs) and High-level Message Sequence Charts (HMSCs) are formalisms used to describe scenarios of message passing protocols. We propose using Allen's logic to represent the temporal order of the messages. We introduce the concept of discord to quantify the discrepancies between the intuition and the semantics of the ordering between messages in different nodes of an HMSC. We study the algorithmic properties of this concept: we show that while the discord of a pair of messages is hard to compute in general, the problem becomes polynomial-time computable if the number of nodes of the HMSC or the number of processes is constant. Moreover, for a given HMSC, it is always computationally easy to identify a pair of messages that exhibits the worst-case discord and compute the discord of this pair. <\/jats:p>","DOI":"10.1142\/s0129054110007210","type":"journal-article","created":{"date-parts":[[2010,3,31]],"date-time":"2010-03-31T11:08:49Z","timestamp":1270033729000},"page":"211-233","source":"Crossref","is-referenced-by-count":2,"title":["QUANTIFYING THE DISCORD: ORDER DISCREPANCIES IN MESSAGE SEQUENCE CHARTS"],"prefix":"10.1142","volume":"21","author":[{"given":"EDITH","family":"ELKIND","sequence":"first","affiliation":[{"name":"Division of Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link, 637371, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BLAISE","family":"GENEST","sequence":"additional","affiliation":[{"name":"IRISA\/CNRS, Campus de Beaulieu, Rennes, 35000, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DORON","family":"PELED","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Bar Ilan University, Ramat Gan 52900, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PAOLA","family":"SPOLETINI","sequence":"additional","affiliation":[{"name":"Universit\u00e0 dell'Insubria via Valleggio 11, Como, 22100, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1145\/182.358434"},{"key":"rf2","first-page":"70","volume":"17","author":"Alur R.","journal-title":"Software \u2014 Concepts and Tools"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.09.034"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1145\/322374.322380"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011227529550"},{"key":"rf9","first-page":"356","author":"Floyd R. W.","journal-title":"Communications of the ACM"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-002-0085-2"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19029-2"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/876638.876639"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.10.002"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054110007210","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:22:47Z","timestamp":1565191367000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054110007210"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4]]},"references-count":11,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2010,4]]}},"alternative-id":["10.1142\/S0129054110007210"],"URL":"https:\/\/doi.org\/10.1142\/s0129054110007210","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4]]}}}