{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T05:22:23Z","timestamp":1776316943286,"version":"3.50.1"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030719944","type":"print"},{"value":"9783030719951","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T00:00:00Z","timestamp":1616457600000},"content-version":"vor","delay-in-days":81,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We extend the<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathtt {L}^{\\!\\star }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>L<\/mml:mi><mml:mrow><mml:mspace\/><mml:mo>\u22c6<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>algorithm to learn bimonoids recognising pomset languages. We then identify a class of pomset automata that accepts precisely the class of pomset languages recognised by bimonoids and show how to convert between bimonoids and automata.<\/jats:p>","DOI":"10.1007\/978-3-030-71995-1_26","type":"book-chapter","created":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T17:03:39Z","timestamp":1616432619000},"page":"510-530","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Learning Pomset Automata"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0669-6865","authenticated-orcid":false,"given":"Gerco","family":"van Heerdt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6068-880X","authenticated-orcid":false,"given":"Tobias","family":"Kapp\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jurriaan","family":"Rot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5014-9784","authenticated-orcid":false,"given":"Alexandra","family":"Silva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,23]]},"reference":[{"key":"26_CR1","doi-asserted-by":"publisher","unstructured":"Aarts, F., Vaandrager, F.W.: Learning I\/O automata. In: CONCUR. pp. 71\u201385 (2010). https:\/\/doi.org\/10.1007\/978-3-642-15375-4_6","DOI":"10.1007\/978-3-642-15375-4_6"},{"key":"26_CR2","doi-asserted-by":"publisher","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87\u2013106 (1987). https:\/\/doi.org\/10.1016\/0890-5401(87)90052-6","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"26_CR3","doi-asserted-by":"publisher","unstructured":"Barlocco, S., Kupke, C.: Angluin learning via logic. In: LFCS. LNCS, vol. 10703, pp. 72\u201390. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-72056-2_5","DOI":"10.1007\/978-3-319-72056-2_5"},{"key":"26_CR4","doi-asserted-by":"publisher","unstructured":"Bojanczyk, M.: Recognisable languages over monads. In: DLT. pp. 1\u201313 (2015). https:\/\/doi.org\/10.1007\/978-3-319-21500-6_1","DOI":"10.1007\/978-3-319-21500-6_1"},{"key":"26_CR5","doi-asserted-by":"publisher","unstructured":"Chapman, M., Chockler, H., Kesseli, P., Kroening, D., Strichman, O., Tautschnig, M.: Learning the language of error. In: ATVA. pp. 114\u2013130 (2015). https:\/\/doi.org\/10.1007\/978-3-319-24953-7_9","DOI":"10.1007\/978-3-319-24953-7_9"},{"key":"26_CR6","doi-asserted-by":"publisher","unstructured":"Clark, A.: Distributional learning of some context-free languages with a minimally adequate teacher. In: ICGI. pp. 24\u201337 (2010). https:\/\/doi.org\/10.1007\/978-3-642-15488-1_4","DOI":"10.1007\/978-3-642-15488-1_4"},{"key":"26_CR7","doi-asserted-by":"publisher","unstructured":"Drewes, F., H\u00f6gberg, J.: Learning a regular tree language from a teacher. In: DLT. pp. 279\u2013291 (2003). https:\/\/doi.org\/10.1007\/3-540-45007-6_22","DOI":"10.1007\/3-540-45007-6_22"},{"key":"26_CR8","doi-asserted-by":"publisher","unstructured":"Drewes, F., H\u00f6gberg, J.: Query learning of regular tree languages: How to avoid dead states. Theory Comput. Syst. 40, 163\u2013185 (2007). https:\/\/doi.org\/10.1007\/s00224-005-1233-3","DOI":"10.1007\/s00224-005-1233-3"},{"key":"26_CR9","doi-asserted-by":"publisher","unstructured":"\u00c9sik, Z., N\u00e9meth, Z.L.: Higher dimensional automata. J. Autom. Lang. Comb. 9(1), 3\u201329 (2004). https:\/\/doi.org\/10.25596\/jalc-2004-003","DOI":"10.25596\/jalc-2004-003"},{"key":"26_CR10","doi-asserted-by":"publisher","unstructured":"Fahrenberg, U., Johansen, C., Struth, G., Thapa, R.B.: Generating posets beyond $$\\sf N$$. In: RAMiCS. pp. 82\u201399 (2020). https:\/\/doi.org\/10.1007\/978-3-030-43520-2_6","DOI":"10.1007\/978-3-030-43520-2_6"},{"key":"26_CR11","doi-asserted-by":"publisher","unstructured":"Ginsburg, S., Spanier, E.H.: Bounded ALGOL-like languages. Trans. Am. Math. Soc. 113(2), 333\u2013368 (1964). https:\/\/doi.org\/10.2307\/1994067","DOI":"10.2307\/1994067"},{"key":"26_CR12","doi-asserted-by":"publisher","unstructured":"Gischer, J.L.: The equational theory of pomsets. Theor. Comput. Sci. 61, 199\u2013224 (1988). https:\/\/doi.org\/10.1016\/0304-3975(88)90124-7","DOI":"10.1016\/0304-3975(88)90124-7"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Grabowski, J.: On partial languages. Fundam. Inform. 4(2), 427 (1981)","DOI":"10.3233\/FI-1981-4210"},{"key":"26_CR14","unstructured":"van Heerdt, G.: Efficient Inference of Mealy Machines. Bachelor\u2019s thesis, Radboud University (2014), https:\/\/www.cs.ru.nl\/bachelors-theses\/2014\/Gerco_van_Heerdt___4167503___Efficient_Inference_of_Mealy_Machines.pdf"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"van Heerdt, G., Kapp\u00e9, T., Rot, J., Silva, A.: Learning pomset automata (2021), to appear on arXiv.","DOI":"10.26226\/morressier.604907f41a80aac83ca25cc5"},{"key":"26_CR16","doi-asserted-by":"publisher","unstructured":"van Heerdt, G., Kupke, C., Rot, J., Silva, A.: Learning weighted automata over principal ideal domains. In: FOSSACS. pp. 602\u2013621 (2020). https:\/\/doi.org\/10.1007\/978-3-030-45231-5_31","DOI":"10.1007\/978-3-030-45231-5_31"},{"key":"26_CR17","doi-asserted-by":"publisher","unstructured":"Hoare, T., M\u00f6ller, B., Struth, G., Wehrman, I.: Concurrent Kleene algebra. In: Proc. Concurrency Theory (CONCUR). pp. 399\u2013414 (2009). https:\/\/doi.org\/10.1007\/978-3-642-04081-8_27","DOI":"10.1007\/978-3-642-04081-8_27"},{"key":"26_CR18","doi-asserted-by":"publisher","unstructured":"Howar, F., Steffen, B.: Active automata learning in practice - an annotated bibliography of the years 2011 to 2016. In: Machine Learning for Dynamic Software Analysis. pp. 123\u2013148 (2018). https:\/\/doi.org\/10.1007\/978-3-319-96562-8_5","DOI":"10.1007\/978-3-319-96562-8_5"},{"key":"26_CR19","doi-asserted-by":"publisher","unstructured":"Isberner, M., Howar, F., Steffen, B.: The TTT algorithm: A redundancy-free approach to active automata learning. In: RV. LNCS, vol.\u00a08734, pp. 307\u2013322. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-11164-3_26","DOI":"10.1007\/978-3-319-11164-3_26"},{"key":"26_CR20","doi-asserted-by":"publisher","unstructured":"Isberner, M., Howar, F., Steffen, B.: The open-source learnlib - A framework for active automata learning. In: CAV. pp. 487\u2013495 (2015). https:\/\/doi.org\/10.1007\/978-3-319-21690-4_32","DOI":"10.1007\/978-3-319-21690-4_32"},{"key":"26_CR21","doi-asserted-by":"publisher","unstructured":"Kapp\u00e9, T., Brunet, P., Luttik, B., Silva, A., Zanasi, F.: Brzozowski goes concurrent - A Kleene theorem for pomset languages. In: CONCUR. pp. 25:1\u201325:16 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2017.25","DOI":"10.4230\/LIPIcs.CONCUR.2017.25"},{"key":"26_CR22","unstructured":"Kapp\u00e9, T., Brunet, P., Luttik, B., Silva, A., Zanasi, F.: Equivalence checking for weak bi-Kleene algebra (2018), https:\/\/arxiv.org\/abs\/1807.02102, under submission"},{"key":"26_CR23","doi-asserted-by":"publisher","unstructured":"Kapp\u00e9, T., Brunet, P., Luttik, B., Silva, A., Zanasi, F.: On series-parallel pomset languages: Rationality, context-freeness and automata. J. Log. Algebr. Meth. Program. 103, 130\u2013153 (2019). https:\/\/doi.org\/10.1016\/j.jlamp.2018.12.001","DOI":"10.1016\/j.jlamp.2018.12.001"},{"key":"26_CR24","doi-asserted-by":"publisher","unstructured":"Kapp\u00e9, T., Brunet, P., Silva, A., Zanasi, F.: Concurrent Kleene algebra: Free model and completeness. In: ESOP. pp. 856\u2013882 (2018). https:\/\/doi.org\/10.1007\/978-3-319-89884-1_30","DOI":"10.1007\/978-3-319-89884-1_30"},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"Kearns, M.J., Vazirani, U.V.: An Introduction to Computational Learning Theory. MIT press (1994)","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"26_CR26","doi-asserted-by":"publisher","unstructured":"Laurence, M.R., Struth, G.: Completeness theorems for bi-Kleene algebras and series-parallel rational pomset languages. In: Proc. Relational and Algebraic Methods in Computer Science (RAMiCS). pp. 65\u201382 (2014). https:\/\/doi.org\/10.1007\/978-3-319-06251-8_5","DOI":"10.1007\/978-3-319-06251-8_5"},{"key":"26_CR27","doi-asserted-by":"publisher","unstructured":"Lodaya, K., Weil, P.: A Kleene iteration for parallelism. In: FSTTCS. pp. 355\u2013366 (1998). https:\/\/doi.org\/10.1007\/978-3-540-49382-2_33","DOI":"10.1007\/978-3-540-49382-2_33"},{"key":"26_CR28","doi-asserted-by":"publisher","unstructured":"Lodaya, K., Weil, P.: Series-parallel languages and the bounded-width property. Theoretical Computer Science 237(1), 347\u2013380 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(00)00031-1","DOI":"10.1016\/S0304-3975(00)00031-1"},{"key":"26_CR29","doi-asserted-by":"publisher","unstructured":"Maler, O., Pnueli, A.: On the learnability of infinitary regular sets. Inf. Comput. 118, 316\u2013326 (1995). https:\/\/doi.org\/10.1006\/inco.1995.1070","DOI":"10.1006\/inco.1995.1070"},{"key":"26_CR30","doi-asserted-by":"publisher","unstructured":"Parikh, R.: On context-free languages. J. ACM 13(4), 570\u2013581 (1966). https:\/\/doi.org\/10.1145\/321356.321364","DOI":"10.1145\/321356.321364"},{"key":"26_CR31","doi-asserted-by":"publisher","unstructured":"Sakakibara, Y.: Learning context-free grammars from structural data in polynomial time. Theor. Comput. Sci. 76(2-3), 223\u2013242 (1990). https:\/\/doi.org\/10.1016\/0304-3975(90)90017-C","DOI":"10.1016\/0304-3975(90)90017-C"},{"key":"26_CR32","doi-asserted-by":"publisher","unstructured":"Urbat, H., Ad\u00e1mek, J., Chen, L., Milius, S.: Eilenberg theorems for free. In: MFCS. pp. 43:1\u201343:15 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2017.43","DOI":"10.4230\/LIPIcs.MFCS.2017.43"},{"key":"26_CR33","doi-asserted-by":"publisher","unstructured":"Urbat, H., Schr\u00f6der, L.: Automata learning: An algebraic approach. In: LICS. pp. 900\u2013914 (2020). https:\/\/doi.org\/10.1145\/3373718.3394775","DOI":"10.1145\/3373718.3394775"},{"key":"26_CR34","doi-asserted-by":"publisher","unstructured":"Vaandrager, F.W.: Model learning. Commun. ACM 60(2), 86\u201395 (2017). https:\/\/doi.org\/10.1145\/2967606","DOI":"10.1145\/2967606"},{"key":"26_CR35","doi-asserted-by":"publisher","unstructured":"Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. SIAM J. Comput. 11(2), 298\u2013313 (1982). https:\/\/doi.org\/10.1137\/0211023","DOI":"10.1137\/0211023"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-71995-1_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,22]],"date-time":"2022-12-22T04:35:35Z","timestamp":1671683735000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-71995-1_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030719944","9783030719951"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-71995-1_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"23 March 2021","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":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 March 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 April 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2021\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"88","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3,2","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference changed to an online format due to the COVID-19 pandemic","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}