{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T13:56:58Z","timestamp":1789999018275,"version":"4.0.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540406716","type":"print"},{"value":"9783540451389","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45138-9_37","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T18:41:48Z","timestamp":1277232108000},"page":"429-438","source":"Crossref","is-referenced-by-count":4,"title":["Local LTL with Past Constants Is Expressively Complete for Mazurkiewicz Traces"],"prefix":"10.1007","author":[{"given":"Paul","family":"Gastin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhavan","family":"Mukund","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"K. Narayan","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"37_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1007\/3-540-45465-9_79","volume-title":"Automata, Languages and Programming","author":"B. Adsul","year":"2002","unstructured":"Adsul, B., Sohoni, M.: Complete and tractable local linear time temporal logics over traces. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 926\u2013937. Springer, Heidelberg (2002)"},{"key":"37_CR2","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0022-0000(93)90005-H","volume":"46","author":"J. Cohen","year":"1993","unstructured":"Cohen, J., Perrin, D., Pin, J.-E.: On the expressive power of temporal logic. Journal of Computer and System Sciences\u00a046, 271\u2013295 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"37_CR3","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-45653-8_4","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"V. Diekert","year":"2001","unstructured":"Diekert, V., Gastin, P.: Local temporal logic is expressively complete for cograph dependence alphabets. In: Nieuwenhuis, R., Voronkov, A. (eds.) LPAR 2001. LNCS (LNAI), vol.\u00a02250, pp. 55\u201369. Springer, Heidelberg (2001)"},{"key":"37_CR4","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1006\/jcss.2001.1817","volume":"64","author":"V. Diekert","year":"2002","unstructured":"Diekert, V., Gastin, P.: LTL is expressively complete for Mazurkiewicz traces. Journal of Computer and System Sciences\u00a064, 396\u2013418 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"37_CR5","volume-title":"The Book of Traces","year":"1995","unstructured":"Diekert, V., Rozenberg, G. (eds.): The Book of Traces. World Scientific, Singapore (1995)"},{"key":"37_CR6","unstructured":"Ebinger, W.: Charakterisierung von Sprachklassen unendlicher Spuren durch Logiken. Dissertation, Institut f\u00fcr Informatik, Universit\u00e4t Stuttgart (1994)"},{"key":"37_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0304-3975(95)00130-1","volume":"154","author":"W. Ebinger","year":"1996","unstructured":"Ebinger, W., Muscholl, A.: Logical definability on infinite traces. Theoretical Computer Science\u00a0154, 67\u201384 (1996)","journal-title":"Theoretical Computer Science"},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"Gabbay, D., Pnueli, A., Shelah, S., Stavi, J.: On the temporal analysis of fairness. In: Proc. of PoPL 1980, Las Vegas, pp. 163\u2013173 (November 1980)","DOI":"10.1145\/567446.567462"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Gastin, P., Kuske, D.: Satisfiability and model checking for MSO-definable temporal logics are in PSPACE. To appear in Proc. of CONCUR 2003 (2003)","DOI":"10.1007\/978-3-540-45187-7_15"},{"key":"37_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"938","DOI":"10.1007\/3-540-45465-9_80","volume-title":"Automata, Languages and Programming","author":"P. Gastin","year":"2002","unstructured":"Gastin, P., Mukund, M.: An elementary expressively complete temporal logic for Mazurkiewicz traces. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 938\u2013949. Springer, Heidelberg (2002)"},{"key":"37_CR11","doi-asserted-by":"crossref","unstructured":"Gastin, P., Mukund, M., Narayan Kumar, K.: Local LTL with past constants is expressively complete for Mazurkiewicz traces. Tech. Rep. 2003-008, LIAFA, Universit\u00e9 Paris 7 (France) (2003)","DOI":"10.1007\/978-3-540-45138-9_37"},{"key":"37_CR12","unstructured":"Kamp, J.A.W.: Tense Logic and the Theory of Linear Order. PhD thesis, University of California, Los Angeles, California (1968)"},{"key":"37_CR13","doi-asserted-by":"crossref","unstructured":"Mazurkiewicz, A.: Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus (1977)","DOI":"10.7146\/dpb.v6i78.7691"},{"key":"37_CR14","volume-title":"Counter-Free Automata","author":"R. McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press, Cambridge (1971)"},{"key":"37_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/BFb0030294","volume-title":"Mathematical Foundations of Computer Science 1984","author":"D. Perrin","year":"1984","unstructured":"Perrin, D.: Recent results on automata and infinite words. In: Chytil, M.P., Koubek, V. (eds.) MFCS 1984. LNCS, vol.\u00a0176, pp. 134\u2013148. Springer, Heidelberg (1984)"},{"key":"37_CR16","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/0022-0000(86)90037-1","volume":"32","author":"D. Perrin","year":"1986","unstructured":"Perrin, D., Pin, J.-E.: First order logic and star-free sets. Journal of Computer and System Sciences\u00a032, 393\u2013406 (1986)","journal-title":"Journal of Computer and System Sciences"},{"key":"37_CR17","doi-asserted-by":"crossref","unstructured":"Pnueli, A.: The temporal logic of programs. In: FOCS 1977, pp. 46\u201357 (1977)","DOI":"10.1109\/SFCS.1977.32"},{"key":"37_CR18","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"M.-P. Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.-P.: On finite monoids having only trivial subgroups. Information and Control\u00a08, 190\u2013194 (1965)","journal-title":"Information and Control"},{"key":"37_CR19","doi-asserted-by":"crossref","unstructured":"Thiagarajan, P.S., Walukiewicz, I.: An expressively complete linear time temporal logic for Mazurkiewicz traces. In: Proc. of LICS 1997, pp. 183\u2013194 (1997)","DOI":"10.1109\/LICS.1997.614946"},{"key":"37_CR20","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/S0019-9958(79)90629-6","volume":"42","author":"W. Thomas","year":"1979","unstructured":"Thomas, W.: Star-free regular sets of \u03c9-sequences. Information and Control\u00a042, 148\u2013156 (1979)","journal-title":"Information and Control"},{"key":"37_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/BFb0055048","volume-title":"Automata, Languages and Programming","author":"I. Walukiewicz","year":"1998","unstructured":"Walukiewicz, I.: Difficult configurations \u2013 on the complexity of LTrL. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 140\u2013151. Springer, Heidelberg (1998)"},{"issue":"2","key":"37_CR22","first-page":"259","volume":"7","author":"I. Walukiewicz","year":"2002","unstructured":"Walukiewicz, I.: Local logics for traces. Journal of Automata, Languages and Combinatorics\u00a07(2), 259\u2013290 (2002)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"37_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/3-540-49116-3_3","volume-title":"STACS 99","author":"T.. Wilke","year":"1999","unstructured":"Wilke, T.: Classifying discrete temporal properties. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 32\u201346. Springer, Heidelberg (1999)"},{"key":"37_CR24","first-page":"99","volume":"21","author":"W. Zielonka","year":"1987","unstructured":"Zielonka, W.: Notes on finite asynchronous automata. R.A.I.R.O. \u2014 Informatique Th\u00e9orique et Applications\u00a021, 99\u2013135 (1987)","journal-title":"R.A.I.R.O. \u2014 Informatique Th\u00e9orique et Applications"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45138-9_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T05:54:02Z","timestamp":1559195642000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45138-9_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540406716","9783540451389"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45138-9_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}