{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T00:10:14Z","timestamp":1758586214021,"version":"3.44.0"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032046994","type":"print"},{"value":"9783032047007","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-04700-7_24","type":"book-chapter","created":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T23:45:33Z","timestamp":1758498333000},"page":"322-335","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Disjointness, Inclusion, and\u00a0Regularity of\u00a0$$\\omega $$-Rational Trace Languages \u2013 Extended Abstract \u2013"],"prefix":"10.1007","author":[{"given":"Dietrich","family":"Kuske","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,11]]},"reference":[{"key":"24_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02088289","volume":"22","author":"I Aalbersberg","year":"1989","unstructured":"Aalbersberg, I., Hoogeboom, H.: Characterizations of the decidability of some problems for regular trace languages. Math. Syst. Theory 22, 1\u201319 (1989)","journal-title":"Math. Syst. Theory"},{"key":"24_CR2","doi-asserted-by":"crossref","unstructured":"Aalbersberg, I., Welzl, E.: Trace languages defined by regular string languages. RAIRO, Inf. Th\u00e9or. Appl. 20,pp. 103\u2013119 (1986)","DOI":"10.1051\/ita\/1986200201031"},{"key":"24_CR3","doi-asserted-by":"publisher","unstructured":"Breuers, S., L\u00f6ding, C., Olschewski, J.: Improved Ramsey-Based B\u00fcchi Complementation. In: Birkedal, L. (ed.) FoSSaCS 2012. LNCS, vol. 7213, pp. 150\u2013164. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28729-9_10","DOI":"10.1007\/978-3-642-28729-9_10"},{"key":"24_CR4","doi-asserted-by":"publisher","unstructured":"Probl\u00e8mes combinatoires de commutation et r\u00e9arrangements. LNM, vol. 85. Springer, Heidelberg (1969). https:\/\/doi.org\/10.1007\/BFb0079468","DOI":"10.1007\/BFb0079468"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Castro, J., Cucker, F.: Nondeterministic $$\\omega $$-computations and the analytical hierarchy. Zeitschr. f. math. Logik und Grundlagen d. Math. 35,pp.333-342 (1989)","DOI":"10.1002\/malq.19890350406"},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(78)90002-6","volume":"6","author":"R Cohen","year":"1978","unstructured":"Cohen, R., Gold, A.: $$\\omega $$-computations on Turing machines. Theoret. Comput. Sci. 6, 1\u201323 (1978)","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR7","doi-asserted-by":"publisher","unstructured":"Diekert, V., Muscholl, A.: Deterministic asynchronous automata for infinite traces. In: Enjalbert, P., Finkel, A., Wagner, K.W. (eds.) STACS 1993. LNCS, vol. 665, pp. 617\u2013628. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-56503-5_61","DOI":"10.1007\/3-540-56503-5_61"},{"key":"24_CR8","doi-asserted-by":"publisher","DOI":"10.1142\/2563","volume-title":"The Book of Traces","author":"V Diekert","year":"1995","unstructured":"Diekert, V., Rozenberg, G.: The Book of Traces. World Scientific Publ, Co (1995)"},{"key":"24_CR9","doi-asserted-by":"publisher","unstructured":"Ebinger, W., Muscholl, A.: Logical definability on infinite traces. In: Lingas, A., Karlsson, R., Carlsson, S. (eds.) ICALP 1993. LNCS, vol. 700, pp. 335\u2013346. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-56939-1_84","DOI":"10.1007\/3-540-56939-1_84"},{"key":"24_CR10","doi-asserted-by":"crossref","unstructured":"Ganardi, M., Majumdar, R., Zetzsche, G.: The complexity of bidirected reachability in valence systems. In: LICS\u201922, pp. 26:1\u201326:15. ACM (2022)","DOI":"10.1145\/3531130.3533345"},{"key":"24_CR11","doi-asserted-by":"publisher","unstructured":"Gastin, P.: Infinite traces. In: Guessarian, I. (ed.) LITP 1990. LNCS, vol. 469, pp. 277\u2013308. Springer, Heidelberg (1990). https:\/\/doi.org\/10.1007\/3-540-53479-2_12","DOI":"10.1007\/3-540-53479-2_12"},{"key":"24_CR12","doi-asserted-by":"publisher","unstructured":"Gastin, P.: Recognizable and rational languages of finite and infinite traces. In: Choffrut, C., Jantzen, M. (eds.) STACS 1991. LNCS, vol. 480, pp. 89\u2013104. Springer, Heidelberg (1991). https:\/\/doi.org\/10.1007\/BFb0020790","DOI":"10.1007\/BFb0020790"},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0304-3975(94)90254-2","volume":"125","author":"P Gastin","year":"1994","unstructured":"Gastin, P., Petit, A., Zielonka, W.: An extension of Kleene\u2019s and Ochmanski\u2019s theorems to infinite traces. Theoret. Comput. Sci. 125, 167\u2013204 (1994)","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR14","unstructured":"Hopcroft, J., Ullman, J.: Introduction to automata theory, languages, and computation. Addison Wesley (1979)"},{"issue":"2","key":"24_CR15","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1016\/j.ic.2018.09.008","volume":"262","author":"M Hutagalung","year":"2018","unstructured":"Hutagalung, M., Hundeshagen, N., Kuske, D., Lange, M., Lozes, \u00c9.: Multi-buffer simulations: decidability and complexity. Inf. Comput. 262(2), 280\u2013310 (2018)","journal-title":"Inf. Comput."},{"issue":"1","key":"24_CR16","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"O Ibarra","year":"1978","unstructured":"Ibarra, O.: Reversal-bounded multicounter machines and their decision problems. J. ACM 25(1), 116\u2013133 (1978)","journal-title":"J. ACM"},{"key":"24_CR17","doi-asserted-by":"crossref","unstructured":"K\u00f6cher, C., Kuske, D.: Backwards-reachability for cooperating multi-pushdown systems. J. Comput. Syst. Sci. 148 (2025), article no. 103601","DOI":"10.1016\/j.jcss.2024.103601"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"Kuske, D.: The theory of reachability in trace-pushdown systems. In: CiE 2025, pp. 283\u2013298. Lecture Notes in Comp. Science. vol. 15764, Springer (2025)","DOI":"10.1007\/978-3-031-95908-0_20"},{"key":"24_CR19","unstructured":"Lohrey, M., Steinberg, B.: The submonoid and rational subset membership problems for graph groups. In: LATA\u201907, pp. 367\u2013378. Report 35\/07, Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona (2007)"},{"key":"24_CR20","unstructured":"Lohrey, M., Zetzsche, G.: The complexity of knapsack in graph groups. In: STACS\u201917. LIPIcs, vol.\u00a066, pp. 52:1\u201352:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"24_CR21","volume-title":"Hilbert\u2019s Tenth Problem","author":"Y Matijasevich","year":"1993","unstructured":"Matijasevich, Y.: Hilbert\u2019s Tenth Problem. MIT Press, Foundations of Computing Series (1993)"},{"key":"24_CR22","doi-asserted-by":"crossref","unstructured":"Mazurkiewicz, A.: Concurrent program schemes and their interpretation. Tech. rep., DAIMI Report PB-78, Aarhus University (1977)","DOI":"10.7146\/dpb.v6i78.7691"},{"key":"24_CR23","doi-asserted-by":"crossref","unstructured":"Minsky, M.: Recursive unsolvability of Post\u2019s problem of \u201ctag\u201d and other topics in theory of Turing machines. Ann. Math. 74(3),pp. 437\u2013455 (1961)","DOI":"10.2307\/1970290"},{"key":"24_CR24","unstructured":"Muscholl, A.: Decision and complexity issues on concurrent systems (1999), Habilitationsschrift, Universit\u00e4t Stuttgart"},{"key":"24_CR25","unstructured":"Odifreddi, P.: Classical recursion theory. The theory of functions and sets of natural numbers, Stud. Logic Found. Math., vol.\u00a0125. Amsterdam etc. North-Holland (1989)"},{"issue":"2","key":"24_CR26","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0304-3975(97)00219-3","volume":"195","author":"D Peled","year":"1998","unstructured":"Peled, D., Wilke, T., Wolper, P.: An algorithmic approach for checking closure properties of temporal logic specifications and omega-regular languages. Theoret. Comput. Sci. 195(2), 183\u2013203 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR27","unstructured":"Perrin, D., Pin, J.E.: Infinite words. Pure and Applied Mathematics vol. 141, Elsevier (2004)"},{"key":"24_CR28","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0304-3975(87)90080-6","volume":"52","author":"J Sakarovitch","year":"1987","unstructured":"Sakarovitch, J.: On regular trace languages. Theor. Comput. Sci. 52, 59\u201375 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"24_CR29","doi-asserted-by":"crossref","unstructured":"Sakarovitch, J.: The \"last\" decision problem for rational trace languages. In: LATIN\u201992, pp. 460\u2013473. Lecture Notes in Comp. Science vol. 583, Springer (1992)","DOI":"10.1007\/BFb0023848"},{"key":"24_CR30","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Automata on infinite objects. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, pp. 133\u2013191. Elsevier Science Publ. B.V. (1990)","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"key":"24_CR31","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1090\/S0002-9939-1962-0172273-0","volume":"13","author":"E Wolk","year":"1962","unstructured":"Wolk, E.: The comparability graph of a tree. Proc. AMS 13, 789\u2013795 (1962)","journal-title":"Proc. AMS"},{"key":"24_CR32","doi-asserted-by":"publisher","unstructured":"Zetzsche, G.: Silent transitions in automata with storage. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7966, pp. 434\u2013445. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39212-2_39","DOI":"10.1007\/978-3-642-39212-2_39"},{"key":"24_CR33","doi-asserted-by":"crossref","unstructured":"Zetzsche, G.: The emptiness problem for valence automata over graph monoids. Inf. Comput. 277 (2021), article no.\u00a0104583","DOI":"10.1016\/j.ic.2020.104583"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-04700-7_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T23:45:36Z","timestamp":1758498336000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-04700-7_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,11]]},"ISBN":["9783032046994","9783032047007"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-04700-7_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,11]]},"assertion":[{"value":"11 September 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Wroc\u0142aw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/fct.ii.uni.wroc.pl","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}