{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T05:21:46Z","timestamp":1776316906403,"version":"3.50.1"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031682780","type":"print"},{"value":"9783031682797","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-68279-7_13","type":"book-chapter","created":{"date-parts":[[2024,8,11]],"date-time":"2024-08-11T23:03:07Z","timestamp":1723417387000},"page":"207-224","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Undecidability of\u00a0the\u00a0Positive Calculus of\u00a0Relations with\u00a0Transitive Closure and\u00a0Difference: Hypothesis Elimination Using Graph Loops"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4106-0408","authenticated-orcid":false,"given":"Yoshiki","family":"Nakamura","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,12]]},"reference":[{"issue":"4","key":"13_CR1","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1007\/BF01225472","volume":"33","author":"H Andr\u00e9ka","year":"1995","unstructured":"Andr\u00e9ka, H., Bredikhin, D.A.: The equational theory of union-free algebras of relations. Algebra Universalis 33(4), 516\u2013532 (1995). https:\/\/doi.org\/10.1007\/BF01225472","journal-title":"Algebra Universalis"},{"key":"13_CR2","doi-asserted-by":"publisher","unstructured":"Berger, R.: The Undecidability of the Domino Problem. No.\u00a066 in Memoirs of the American Mathematical Society, American Mathematical Society (1966). https:\/\/doi.org\/10.1090\/memo\/0066","DOI":"10.1090\/memo\/0066"},{"key":"13_CR3","doi-asserted-by":"publisher","unstructured":"Brunet, P., Pous, D.: Petri automata for Kleene allegories. In: LICS. pp. 68\u201379. IEEE (2015). https:\/\/doi.org\/10.1109\/LICS.2015.17","DOI":"10.1109\/LICS.2015.17"},{"key":"13_CR4","doi-asserted-by":"publisher","unstructured":"Brunet, P., Pous, D.: Petri automata. Logical Methods in Computer Science 13(3) (2017). https:\/\/doi.org\/10.23638\/LMCS-13(3:33)2017","DOI":"10.23638\/LMCS-13(3:33)2017"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"B\u00f6rger, E., Gr\u00e4del, E., Gurevich, Y.: The Classical Decision Problem. Springer (1997), https:\/\/link.springer.com\/9783540423249","DOI":"10.1007\/978-3-642-59207-2"},{"key":"13_CR6","doi-asserted-by":"publisher","unstructured":"Danecki, R.: Propositional dynamic logic with strong loop predicate. In: MFCS. LNCS, vol.\u00a0176, pp. 573\u2013581. Springer (1984). https:\/\/doi.org\/10.1007\/BFb0030342","DOI":"10.1007\/BFb0030342"},{"issue":"4","key":"13_CR7","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/1183278.1183285","volume":"7","author":"J Desharnais","year":"2006","unstructured":"Desharnais, J., M\u00f6ller, B., Struth, G.: Kleene algebra with domain. ACM Trans. Comput. Log. 7(4), 798\u2013833 (2006). https:\/\/doi.org\/10.1145\/1183278.1183285","journal-title":"ACM Trans. Comput. Log."},{"issue":"2","key":"13_CR8","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/0022-0000(79)90046-1","volume":"18","author":"MJ Fischer","year":"1979","unstructured":"Fischer, M.J., Ladner, R.E.: Propositional dynamic logic of regular programs. J. Comput. Syst. Sci. 18(2), 194\u2013211 (1979). https:\/\/doi.org\/10.1016\/0022-0000(79)90046-1","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR9","doi-asserted-by":"publisher","unstructured":"F\u00fcrer, M.: The complexity of the inequivalence problem for regular expressions with intersection. In: ICALP. LNCS, vol.\u00a085, pp. 234\u2013245. Springer (1980). https:\/\/doi.org\/10.1007\/3-540-10003-2_74","DOI":"10.1007\/3-540-10003-2_74"},{"key":"13_CR10","doi-asserted-by":"publisher","unstructured":"Goldblatt, R., Jackson, M.: Well-structured program equivalence is highly undecidable. ACM Transactions on Computational Logic 13(3), 26:1-26:8 (2012). https:\/\/doi.org\/10.1145\/2287718.2287726","DOI":"10.1145\/2287718.2287726"},{"issue":"2","key":"13_CR11","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BF00971620","volume":"13","author":"YS Gurevich","year":"1972","unstructured":"Gurevich, Y.S., Koryakov, I.O.: Remarks on Berger\u2019s paper on the domino problem. Sib. Math. J. 13(2), 319\u2013321 (1972). https:\/\/doi.org\/10.1007\/BF00971620","journal-title":"Sib. Math. J."},{"issue":"1","key":"13_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(83)90097-X","volume":"27","author":"JY Halpern","year":"1983","unstructured":"Halpern, J.Y., Reif, J.H.: The propositional dynamic logic of deterministic, well-structured programs. Theoret. Comput. Sci. 27(1), 127\u2013165 (1983). https:\/\/doi.org\/10.1016\/0304-3975(83)90097-X","journal-title":"Theoret. Comput. Sci."},{"key":"13_CR13","unstructured":"Hardin, C., Kozen, D.: On the elimination of hypotheses in Kleene algebra with tests. Tech. rep., Cornell University (2002), https:\/\/hdl.handle.net\/1813\/5855"},{"issue":"7","key":"13_CR14","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1145\/358886.358892","volume":"23","author":"D Harel","year":"1980","unstructured":"Harel, D.: On folk theorems. Commun. ACM 23(7), 379\u2013389 (1980). https:\/\/doi.org\/10.1145\/358886.358892","journal-title":"Commun. ACM"},{"key":"13_CR15","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/2516.001.0001","author":"D Harel","year":"2000","unstructured":"Harel, D., Kozen, D., Tiuryn, J.: Dynamic Logic. The MIT Press (2000). https:\/\/doi.org\/10.7551\/mitpress\/2516.001.0001","journal-title":"Dynamic Logic. The MIT Press"},{"key":"13_CR16","doi-asserted-by":"publisher","unstructured":"Hirsch, R.: Decidability of equational theories for subsignatures of relation algebra. In: RAMiCS. LNCS, vol. 11194, pp. 87\u201396. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-030-02149-8_6","DOI":"10.1007\/978-3-030-02149-8_6"},{"issue":"3","key":"13_CR17","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1145\/256167.256195","volume":"19","author":"D Kozen","year":"1997","unstructured":"Kozen, D.: Kleene algebra with tests. ACM Trans. Program. Lang. Syst. 19(3), 427\u2013443 (1997). https:\/\/doi.org\/10.1145\/256167.256195","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"13_CR18","doi-asserted-by":"publisher","unstructured":"Kozen, D., Smith, F.: Kleene algebra with tests: Completeness and decidability. In: CSL. LNCS, vol.\u00a01258, pp. 244\u2013259. Springer (1996). https:\/\/doi.org\/10.1007\/3-540-63172-0_43","DOI":"10.1007\/3-540-63172-0_43"},{"key":"13_CR19","doi-asserted-by":"publisher","unstructured":"Nakamura, Y.: Partial derivatives on graphs for Kleene allegories. In: LICS. pp. 1\u201312. IEEE (2017). https:\/\/doi.org\/10.1109\/LICS.2017.8005132","DOI":"10.1109\/LICS.2017.8005132"},{"key":"13_CR20","doi-asserted-by":"publisher","unstructured":"Nakamura, Y.: The undecidability of FO3 and the calculus of relations with just one binary relation. In: ICLA. LNTCS, vol. 11600, pp. 108\u2013120. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-662-58771-3_11","DOI":"10.1007\/978-3-662-58771-3_11"},{"key":"13_CR21","doi-asserted-by":"publisher","unstructured":"Nakamura, Y.: Expressive power and succinctness of the positive calculus of relations. In: RAMiCS. LNTCS, vol. 12062, pp. 204\u2013220. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-43520-2_13","DOI":"10.1007\/978-3-030-43520-2_13"},{"key":"13_CR22","doi-asserted-by":"publisher","unstructured":"Nakamura, Y.: Expressive power and succinctness of the positive calculus of binary relations. Journal of Logical and Algebraic Methods in Programming 127, 100760 (2022). https:\/\/doi.org\/10.1016\/j.jlamp.2022.100760","DOI":"10.1016\/j.jlamp.2022.100760"},{"key":"13_CR23","doi-asserted-by":"publisher","unstructured":"Nakamura, Y.: Existential calculi of relations with transitive closure: Complexity and edge saturations. In: LICS. pp. 1\u201313. IEEE (2023). https:\/\/doi.org\/10.1109\/LICS56636.2023.10175811","DOI":"10.1109\/LICS56636.2023.10175811"},{"key":"13_CR24","doi-asserted-by":"publisher","unstructured":"Pous, D.: On the positive calculus of relations with transitive closure. In: STACS. LIPIcs, vol.\u00a096, pp. 3:1\u20133:16. Schloss Dagstuhl (2018). https:\/\/doi.org\/10.4230\/LIPICS.STACS.2018.3","DOI":"10.4230\/LIPICS.STACS.2018.3"},{"key":"13_CR25","doi-asserted-by":"publisher","unstructured":"Pous, D., Rot, J., Wagemaker, J.: On tools for completeness of Kleene algebra with hypotheses. In: RAMiCS. pp. 378\u2013395. LNCS, Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-88701-8_23","DOI":"10.1007\/978-3-030-88701-8_23"},{"key":"13_CR26","doi-asserted-by":"publisher","unstructured":"Smolka, S., Foster, N., Hsu, J., Kapp\u00e9, T., Kozen, D., Silva, A.: Guarded Kleene algebra with tests: verification of uninterpreted programs in nearly linear time. Proceedings of the ACM on Programming Languages 4(POPL), 61:1-61:28 (2019). https:\/\/doi.org\/10.1145\/3371129","DOI":"10.1145\/3371129"},{"issue":"3","key":"13_CR27","doi-asserted-by":"publisher","first-page":"73","DOI":"10.2307\/2268577","volume":"6","author":"A Tarski","year":"1941","unstructured":"Tarski, A.: On the calculus of relations. The Journal of Symbolic Logic 6(3), 73\u201389 (1941). https:\/\/doi.org\/10.2307\/2268577","journal-title":"The Journal of Symbolic Logic"},{"key":"13_CR28","doi-asserted-by":"publisher","unstructured":"Tarski, A., Givant, S.: A Formalization of Set Theory without Variables, vol.\u00a041. American Mathematical Society (1987). https:\/\/doi.org\/10.1090\/coll\/041","DOI":"10.1090\/coll\/041"}],"container-title":["Lecture Notes in Computer Science","Relational and Algebraic Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-68279-7_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,11]],"date-time":"2024-08-11T23:07:49Z","timestamp":1723417669000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-68279-7_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031682780","9783031682797"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-68279-7_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"12 August 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RAMiCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Relational and Algebraic Methods in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ramics2023a","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ramics-conf.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}