{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T16:02:54Z","timestamp":1765123374277,"version":"3.40.4"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031908965"},{"type":"electronic","value":"9783031908972"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T00:00:00Z","timestamp":1746057600000},"content-version":"vor","delay-in-days":120,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We consider process algebras with branching parametrized by an equational theory <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsf{T}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>T<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, and show that it is possible to axiomatize bisimilarity under certain conditions on <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\textsf{T}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>T<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. Our proof abstracts an earlier argument due to Grabmayer and Fokkink (LICS\u201920), and yields new completeness theorems for skip-free process algebras with probabilistic (guarded) branching, while also covering existing completeness results.<\/jats:p>","DOI":"10.1007\/978-3-031-90897-2_13","type":"book-chapter","created":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T08:17:53Z","timestamp":1746001073000},"page":"265-286","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A General Completeness Theorem for Skip-Free Star Algebras"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6068-880X","authenticated-orcid":false,"given":"Tobias","family":"Kapp\u00e9","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9838-2363","authenticated-orcid":false,"given":"Todd","family":"Schmid","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,1]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Adamek, J., Rosicky, J.: Locally Presentable and Accessible Categories. London Mathematical Society Lecture Note Series, Cambridge University Press (1994)","DOI":"10.1017\/CBO9780511600579"},{"key":"13_CR2","doi-asserted-by":"publisher","unstructured":"Antimirov, V.M.: Partial derivates of regular expressions and finite automata constructions. In: STACS. pp. 455\u2013466 (1995). https:\/\/doi.org\/10.1007\/3-540-59042-0_96","DOI":"10.1007\/3-540-59042-0_96"},{"key":"13_CR3","doi-asserted-by":"publisher","unstructured":"Baeten, J.C.M., Bergstra, J.A.: Process algebra with a zero object. In: CONCUR. pp. 83\u201398 (1990). https:\/\/doi.org\/10.1007\/BFB0039053","DOI":"10.1007\/BFB0039053"},{"key":"13_CR4","doi-asserted-by":"publisher","unstructured":"Bonchi, F., Sokolova, A., Vignudelli, V.: Presenting convex sets of probability distributions by convex semilattices and unique bases ((co)algebraic pearls). In: CALCO. pp. 11:1\u201311:18 (2021). https:\/\/doi.org\/10.4230\/LIPICS.CALCO.2021.11","DOI":"10.4230\/LIPICS.CALCO.2021.11"},{"key":"13_CR5","doi-asserted-by":"publisher","unstructured":"Grabmayer, C.: Milner\u2019s proof system for regular expressions modulo bisimilarity is complete: Crystallization: Near-collapsing process graph interpretations of regular expressions. In: LICS. pp. 34:1\u201334:13 (2022). https:\/\/doi.org\/10.1145\/3531130.3532430","DOI":"10.1145\/3531130.3532430"},{"key":"13_CR6","doi-asserted-by":"publisher","unstructured":"Grabmayer, C., Fokkink, W.J.: A complete proof system for 1-free regular expressions modulo bisimilarity. In: LICS. pp. 465\u2013478 (2020). https:\/\/doi.org\/10.1145\/3373718.3394744","DOI":"10.1145\/3373718.3394744"},{"key":"13_CR7","doi-asserted-by":"publisher","unstructured":"Jacobs, B.: Introduction to Coalgebra: Towards Mathematics of States and Observation, Cambridge Tracts in Theoretical Computer Science, vol.\u00a059. Cambridge University Press (2016). https:\/\/doi.org\/10.1017\/CBO9781316823187","DOI":"10.1017\/CBO9781316823187"},{"key":"13_CR8","unstructured":"Kapp\u00e9, T., Schmid, T.: A general completeness theorem for skip-free star algebras (2025), https:\/\/arxiv.org\/abs\/2501.15325"},{"key":"13_CR9","doi-asserted-by":"publisher","unstructured":"Kapp\u00e9, T., Schmid, T., Silva, A.: A complete inference system for skip-free guarded Kleene algebra with tests. In: ESOP. pp. 309\u2013336 (2023). https:\/\/doi.org\/10.1007\/978-3-031-30044-8_12","DOI":"10.1007\/978-3-031-30044-8_12"},{"key":"13_CR10","doi-asserted-by":"publisher","unstructured":"Keimel, K., Plotkin, G.D.: Mixed powerdomains for probability and nondeterminism. Log. Methods Comput. Sci. 13(1) (2017). https:\/\/doi.org\/10.23638\/LMCS-13(1:2)2017","DOI":"10.23638\/LMCS-13(1:2)2017"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Kleene, S.C.: Representation of events in nerve nets and finite automata. Automata studies 34, 3\u201341 (1956)","DOI":"10.1515\/9781400882618-002"},{"key":"13_CR12","doi-asserted-by":"publisher","unstructured":"Kozen, D.: Kleene algebra with tests. ACM Trans. Program. Lang. Syst. 19(3), 427\u2013443 (1997). https:\/\/doi.org\/10.1145\/256167.256195","DOI":"10.1145\/256167.256195"},{"key":"13_CR13","doi-asserted-by":"publisher","unstructured":"Kozen, D., Tseng, W.D.: The B\u00f6hm-Jacopini theorem is false, propositionally. In: MPC. pp. 177\u2013192 (2008). https:\/\/doi.org\/10.1007\/978-3-540-70594-9_11","DOI":"10.1007\/978-3-540-70594-9_11"},{"key":"13_CR14","doi-asserted-by":"publisher","unstructured":"Liell-Cock, J., Staton, S.: Compositional imprecise probability: A solution from graded monads and markov categories. In: POPL. pp. 1596\u20131626 (2025). https:\/\/doi.org\/10.1145\/3704890","DOI":"10.1145\/3704890"},{"key":"13_CR15","doi-asserted-by":"publisher","unstructured":"Milner, R.: A complete inference system for a class of regular behaviours. J. Comput. Syst. Sci. 28(3), 439\u2013466 (1984). https:\/\/doi.org\/10.1016\/0022-0000(84)90023-0","DOI":"10.1016\/0022-0000(84)90023-0"},{"key":"13_CR16","doi-asserted-by":"publisher","unstructured":"Mislove, M.W., Ouaknine, J., Worrell, J.: Axioms for probability and nondeterminism. In: EXPRESS. pp. 7\u201328 (2003). https:\/\/doi.org\/10.1016\/J.ENTCS.2004.04.019","DOI":"10.1016\/J.ENTCS.2004.04.019"},{"key":"13_CR17","doi-asserted-by":"publisher","unstructured":"Pir\u00f3g, M., Staton, S.: Backtracking with cut via a distributive law and left-zero monoids. J. Funct. Program. 27, \u00a0e17 (2017). https:\/\/doi.org\/10.1017\/S0956796817000077","DOI":"10.1017\/S0956796817000077"},{"key":"13_CR18","doi-asserted-by":"publisher","unstructured":"Plotkin, G.D., Power, J.: Semantics for algebraic operations. In: MFCS. pp. 332\u2013345 (2001). https:\/\/doi.org\/10.1016\/S1571-0661(04)80970-8","DOI":"10.1016\/S1571-0661(04)80970-8"},{"key":"13_CR19","doi-asserted-by":"publisher","unstructured":"Plotkin, G.D., Power, J.: Notions of computation determine monads. In: FOSSACS. pp. 342\u2013356 (2002). https:\/\/doi.org\/10.1007\/3-540-45931-6_24","DOI":"10.1007\/3-540-45931-6_24"},{"key":"13_CR20","unstructured":"Riehl, E.: Category theory in context. Aurora Dover Modern Math Originals, Dover Publications, Inc., Mineola, NY (2016)"},{"key":"13_CR21","doi-asserted-by":"publisher","unstructured":"Rozowski, W., Kapp\u00e9, T., Kozen, D., Schmid, T., Silva, A.: Probabilistic guarded KAT modulo bisimilarity: Completeness and complexity. In: ICALP. vol.\u00a0261, pp. 136:1\u2013136:20 (2023). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2023.136","DOI":"10.4230\/LIPICS.ICALP.2023.136"},{"key":"13_CR22","doi-asserted-by":"publisher","unstructured":"Rozowski, W., Silva, A.: A completeness theorem for probabilistic regular expressions. In: LICS. pp. 66:1\u201366:14. ACM (2024). https:\/\/doi.org\/10.1145\/3661814.3662084","DOI":"10.1145\/3661814.3662084"},{"key":"13_CR23","doi-asserted-by":"publisher","unstructured":"Rutten, J.J.M.M.: Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249(1), 3\u201380 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(00)00056-6","DOI":"10.1016\/S0304-3975(00)00056-6"},{"key":"13_CR24","doi-asserted-by":"publisher","unstructured":"Salomaa, A.: Two complete axiom systems for the algebra of regular events. J. ACM 13(1), 158\u2013169 (1966). https:\/\/doi.org\/10.1145\/321312.321326","DOI":"10.1145\/321312.321326"},{"key":"13_CR25","unstructured":"Schmid, T.: Coalgebraic Completeness Theorems for Effectful Process Algebras. Ph.D. thesis, University College London (2024)"},{"key":"13_CR26","doi-asserted-by":"publisher","unstructured":"Schmid, T., Kapp\u00e9, T., Kozen, D., Silva, A.: Guarded Kleene algebra with tests: Coequations, coinduction, and completeness. In: ICALP. pp. 142:1\u2013142:14 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.142","DOI":"10.4230\/LIPIcs.ICALP.2021.142"},{"key":"13_CR27","doi-asserted-by":"publisher","unstructured":"Schmid, T., Rot, J., Silva, A.: On star expressions and coalgebraic completeness theorems. In: CALCO. pp. 242\u2013259 (2021). https:\/\/doi.org\/10.4204\/EPTCS.351.15","DOI":"10.4204\/EPTCS.351.15"},{"key":"13_CR28","doi-asserted-by":"publisher","unstructured":"Schmid, T., Rozowski, W., Silva, A., Rot, J.: Processes parametrised by an algebraic theory. In: ICALP. pp. 132:1\u2013132:20 (2022). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2022.132","DOI":"10.4230\/LIPICS.ICALP.2022.132"},{"key":"13_CR29","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. In: POPL. pp. 61:1\u201361:28 (2020). https:\/\/doi.org\/10.1145\/3371129","DOI":"10.1145\/3371129"},{"key":"13_CR30","doi-asserted-by":"publisher","unstructured":"Sokolova, A., Woracek, H.: Congruences of convex algebras. Journal of Pure and Applied Algebra 219(8), 3110\u20133148 (2015). https:\/\/doi.org\/10.1016\/j.jpaa.2014.10.005","DOI":"10.1016\/j.jpaa.2014.10.005"},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Stark, E.W., Smolka, S.A.: A complete axiom system for finite-state probabilistic processes. In: Proof, Language, and Interaction, Essays in Honour of Robin Milner. pp. 571\u2013596. MIT Press (2000)","DOI":"10.7551\/mitpress\/5641.003.0027"},{"key":"13_CR32","unstructured":"\u015awirszcz, T.: Monadic functors and categories of convex sets. Institute of Mathematics, Polish Academy of Sciences (1974)"},{"key":"13_CR33","doi-asserted-by":"publisher","unstructured":"Turi, D., Plotkin, G.D.: Towards a mathematical operational semantics. In: LICS. pp. 280\u2013291 (1997). https:\/\/doi.org\/10.1109\/LICS.1997.614955","DOI":"10.1109\/LICS.1997.614955"},{"key":"13_CR34","doi-asserted-by":"publisher","unstructured":"Varacca, D., Winskel, G.: Distributing probability over non-determinism. Mathematical Structures in Computer Science 16(1), 87\u2013113 (2006). https:\/\/doi.org\/10.1017\/S0960129505005074","DOI":"10.1017\/S0960129505005074"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-90897-2_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T08:18:02Z","timestamp":1746001082000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-90897-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031908965","9783031908972"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-90897-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"1 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hamilton, ON","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","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":"3 May 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 May 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2025\/conferences\/fossacs\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}