{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T17:47:55Z","timestamp":1648835275212},"reference-count":5,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2002,6]]},"abstract":"<jats:p> A temporal logic of causality (TLC) was introduced by Alur, Penczek, and Peled in [1]. It is basically a linear time temporal logic interpreted over Mazurkiewicz traces which allows quantification over causal chains. Through this device one can directly formulate causality properties of distributed systems. In this paper we consider an extension of TLC by strengthening the chain quantification operators. We show that our logic TLC* adds to the expressive power of TLC. We doso by defining an Ehrenfeucht-Fra\u00efss\u00e9 game to capture the expressive power of TLC. We then exhibit a property and by means of this game prove that the chosen property is not definable in TLC. We then show that the same property is definable in TLC*. We prove in fact the stronger result that TLC* is expressively stronger than TLC exactly when the dependency relation associated with the underlying trace alphabet is not transitive. We then show that TLC* defines only regular trace languages by embedding it into the monadic second-order logic. Finally, the relative expressive power of TLC* and similar logics for traces is compared. <\/jats:p>","DOI":"10.1142\/s0129054102001151","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:05:54Z","timestamp":1027767954000},"page":"341-360","source":"Crossref","is-referenced-by-count":1,"title":["AN EXPRESSIVE EXTENSION OF TLC"],"prefix":"10.1142","volume":"13","author":[{"given":"JESPER","family":"GULMANN HENRIKSEN","sequence":"first","affiliation":[{"name":"BRICS (Basic Research in Computer Science, Centre of the Danish National Research Foundation.), Department of Computer Science, University of Aarhus, Building 540, Ny  Munkegade, DK-8000 Aarhus C, Denmark"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1145\/5397.5399"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00130-1"},{"key":"p_11","first-page":"269","volume":"267","author":"Hafer Th.","year":"1987","journal-title":"Proceedings of the 14th International Colloquium on Automata, Languages and Programming (ICALP,87), Lecture Notes in Computer Science"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90125-6"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.1007\/BF00709154"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054102001151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:34:33Z","timestamp":1565192073000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054102001151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,6]]},"references-count":5,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2002,6]]}},"alternative-id":["10.1142\/S0129054102001151"],"URL":"https:\/\/doi.org\/10.1142\/s0129054102001151","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,6]]}}}