{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:52:47Z","timestamp":1740099167134,"version":"3.37.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030001506"},{"type":"electronic","value":"9783030001513"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-00151-3_6","type":"book-chapter","created":{"date-parts":[[2018,8,25]],"date-time":"2018-08-25T09:54:31Z","timestamp":1535190871000},"page":"91-107","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Perfect Timed Communication Is Hard"],"prefix":"10.1007","author":[{"given":"Parosh Aziz","family":"Abdulla","sequence":"first","affiliation":[]},{"given":"Mohamed Faouzi","family":"Atig","sequence":"additional","affiliation":[]},{"given":"Shankara Narayanan","family":"Krishna","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,26]]},"reference":[{"key":"6_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/3-540-45740-2_5","volume-title":"Applications and Theory of Petri Nets 2001","author":"PA Abdulla","year":"2001","unstructured":"Abdulla, P.A., Nyl\u00e9n, A.: Timed Petri nets and BQOs. In: Colom, J.-M., Koutny, M. (eds.) ICATPN 2001. LNCS, vol. 2075, pp. 53\u201370. Springer, Heidelberg (2001). \nhttps:\/\/doi.org\/10.1007\/3-540-45740-2_5"},{"key":"6_CR2","unstructured":"Abdulla, P.A., Atig, M.F., Cederberg, J.: Timed lossy channel systems. In: FSTTCS 2012, LIPIcs, 15\u201317 December 2012, Hyderabad, India, vol. 18, pp. 374\u2013386. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"key":"6_CR3","unstructured":"Abdulla, P.A., Atig, M.F., Krishna, S.N.: What is decidable about perfect timed channels? CoRR, abs\/1708.05063 (2017)"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Abdulla, P.A., Atig, M.F., Stenman, J.: Dense-timed pushdown automata. In: Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, 25\u201328 June 2012, pp. 35\u201344. IEEE Computer Society (2012)","DOI":"10.1109\/LICS.2012.15"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Abdulla, P.A., Jonsson, B.: Verifying programs with unreliable channels. In: LICS. IEEE Computer Society (1993)","DOI":"10.1109\/LICS.1993.287591"},{"key":"6_CR6","doi-asserted-by":"publisher","unstructured":"Abdulla, P., Mahata, P., Mayr, R.: Dense-timed Petri nets: checking zenoness, token liveness and boundedness. Log. Methods Comput. Sci. 3(1) (2007). \nhttps:\/\/doi.org\/10.2168\/LMCS-3(1:1)2007","DOI":"10.2168\/LMCS-3(1:1)2007"},{"key":"6_CR7","unstructured":"Akshay, S., Gastin, P., Krishna, S.N.: Analyzing timed systems using tree automata. In: 27th International Conference on Concurrency Theory, CONCUR 2016, 23\u201326 August 2016, LIPIcs, Qu\u00e9bec City, Canada, vol. 59, pp. 27:1\u201327:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-319-39086-4_18","volume-title":"Application and Theory of Petri Nets and Concurrency","author":"S Akshay","year":"2016","unstructured":"Akshay, S., Genest, B., H\u00e9lou\u00ebt, L.: Decidable classes of unbounded Petri nets with time and urgency. In: Kordon, F., Moldt, D. (eds.) PETRI NETS 2016. LNCS, vol. 9698, pp. 301\u2013322. Springer, Cham (2016). \nhttps:\/\/doi.org\/10.1007\/978-3-319-39086-4_18"},{"issue":"2","key":"6_CR9","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(94)90010-8","volume":"126","author":"R Alur","year":"1994","unstructured":"Alur, R., Dill, D.L.: A theory of timed automata. Theor. Comput. Sci. 126(2), 183\u2013235 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/11562948_23","volume-title":"Automated Technology for Verification and Analysis","author":"B B\u00e9rard","year":"2005","unstructured":"B\u00e9rard, B., Cassez, F., Haddad, S., Lime, D., Roux, O.H.: Comparison of different semantics for time Petri nets. In: Peled, D.A., Tsay, Y.-K. (eds.) ATVA 2005. LNCS, vol. 3707, pp. 293\u2013307. Springer, Heidelberg (2005). \nhttps:\/\/doi.org\/10.1007\/11562948_23"},{"key":"6_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-662-53132-7_4","volume-title":"Developments in Language Theory","author":"D Bhave","year":"2016","unstructured":"Bhave, D., Dave, V., Krishna, S.N., Phawade, R., Trivedi, A.: A perfect class of context-sensitive timed languages. In: Brlek, S., Reutenauer, C. (eds.) DLT 2016. LNCS, vol. 9840, pp. 38\u201350. Springer, Heidelberg (2016). \nhttps:\/\/doi.org\/10.1007\/978-3-662-53132-7_4"},{"key":"6_CR12","unstructured":"Bocchi, L., Lange, J., Yoshida, N.: Meeting deadlines together. In: Aceto, L., de Frutos Escrig, D. (eds.) 26th International Conference on Concurrency Theory (CONCUR 2015), Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, vol. 42, pp. 283\u2013296. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015)"},{"key":"6_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/3-540-60472-3_4","volume-title":"Hybrid Systems II","author":"A Bouajjani","year":"1995","unstructured":"Bouajjani, A., Echahed, R., Robbana, R.: On the automatic verification of systems with continuous variables and unbounded discrete data structures. In: Antsaklis, P., Kohn, W., Nerode, A., Sastry, S. (eds.) HS 1994. LNCS, vol. 999, pp. 64\u201385. Springer, Heidelberg (1995). \nhttps:\/\/doi.org\/10.1007\/3-540-60472-3_4"},{"issue":"1\u20132","key":"6_CR14","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(99)00033-X","volume":"221","author":"A Bouajjani","year":"1999","unstructured":"Bouajjani, A., Habermehl, P.: Symbolic reachability analysis of FIFO-channel systems with nonregular sets of configurations. Theor. Comput. Sci. 221(1\u20132), 211\u2013250 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.entcs.2009.05.038","volume":"239","author":"F Bouchy","year":"2009","unstructured":"Bouchy, F., Finkel, A., Sangnier, A.: Reachability in timed counter systems. Electron. Notes Theor. Comput. Sci. 239, 167\u2013178 (2009)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"issue":"2","key":"6_CR16","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1145\/322374.322380","volume":"30","author":"D Brand","year":"1983","unstructured":"Brand, D., Zafiropulo, P.: On communicating finite-state machines. J. ACM 30(2), 323\u2013342 (1983)","journal-title":"J. ACM"},{"issue":"2","key":"6_CR17","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.ic.2005.05.006","volume":"202","author":"G C\u00e9c\u00e9","year":"2005","unstructured":"C\u00e9c\u00e9, G., Finkel, A.: Verification of programs with half-duplex communication. Inf. Comput. 202(2), 166\u2013190 (2005)","journal-title":"Inf. Comput."},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-540-85361-9_28","volume-title":"CONCUR 2008 - Concurrency Theory","author":"P Chambart","year":"2008","unstructured":"Chambart, P., Schnoebelen, P.: Mixing lossy and perfect FIFO channels. In: van Breugel, F., Chechik, M. (eds.) CONCUR 2008. LNCS, vol. 5201, pp. 340\u2013355. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-85361-9_28"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-642-37075-5_6","volume-title":"Foundations of Software Science and Computation Structures","author":"L Clemente","year":"2013","unstructured":"Clemente, L., Herbreteau, F., Stainer, A., Sutre, G.: Reachability of communicating timed processes. In: Pfenning, F. (ed.) FoSSaCS 2013. LNCS, vol. 7794, pp. 81\u201396. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-37075-5_6"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Clemente, L., Lasota, S.: Timed pushdown automata revisited. In: 30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, 6\u201310 July 2015, pp. 738\u2013749. IEEE Computer Society (2015)","DOI":"10.1109\/LICS.2015.73"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Clemente, L., Lasota, S., Lazic, R., Mazowiecki, F.: Timed pushdown automata and branching vector addition systems. In: 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, 20\u201323 June 2017, pp. 1\u201312. IEEE Computer Society (2017)","DOI":"10.1109\/LICS.2017.8005083"},{"issue":"1\u20133","key":"6_CR22","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0304-3975(02)00743-0","volume":"302","author":"Z Dang","year":"2003","unstructured":"Dang, Z.: Pushdown timed automata: a binary reachability characterization and safety verification. Theor. Comput. Sci. 302(1\u20133), 93\u2013121 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/11730637_17","volume-title":"Hybrid Systems: Computation and Control","author":"M Emmi","year":"2006","unstructured":"Emmi, M., Majumdar, R.: Decision problems for the verification of real-time software. In: Hespanha, J.P., Tiwari, A. (eds.) HSCC 2006. LNCS, vol. 3927, pp. 200\u2013211. Springer, Heidelberg (2006). \nhttps:\/\/doi.org\/10.1007\/11730637_17"},{"key":"6_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-642-04368-0_14","volume-title":"Formal Modeling and Analysis of Timed Systems","author":"P Ganty","year":"2009","unstructured":"Ganty, P., Majumdar, R.: Analyzing real-time event-driven programs. In: Ouaknine, J., Vaandrager, F.W. (eds.) FORMATS 2009. LNCS, vol. 5813, pp. 164\u2013178. Springer, Heidelberg (2009). \nhttps:\/\/doi.org\/10.1007\/978-3-642-04368-0_14"},{"key":"6_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/11817963_24","volume-title":"Computer Aided Verification","author":"P Krcal","year":"2006","unstructured":"Krcal, P., Yi, W.: Communicating timed automata: the more synchronous, the more difficult to verify. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 249\u2013262. Springer, Heidelberg (2006). \nhttps:\/\/doi.org\/10.1007\/11817963_24"},{"key":"6_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-540-78800-3_21","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"S Torre La","year":"2008","unstructured":"La Torre, S., Madhusudan, P., Parlato, G.: Context-bounded analysis of concurrent queue systems. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 299\u2013314. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-78800-3_21"},{"key":"6_CR27","unstructured":"Pachl, J.K.: Reachability problems for communicating finite state machines. Ph.D. thesis, Faculty of Mathematics, University of Waterloo, Ontario (1982)"},{"key":"6_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/978-3-642-15643-4_23","volume-title":"Automated Technology for Verification and Analysis","author":"A Trivedi","year":"2010","unstructured":"Trivedi, A., Wojtczak, D.: Recursive timed automata. In: Bouajjani, A., Chin, W.-N. (eds.) ATVA 2010. LNCS, vol. 6252, pp. 306\u2013324. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-642-15643-4_23"}],"container-title":["Lecture Notes in Computer Science","Formal Modeling and Analysis of Timed Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-00151-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,8,25]],"date-time":"2018-08-25T09:56:30Z","timestamp":1535190990000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-00151-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030001506","9783030001513"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-00151-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}