{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T05:13:36Z","timestamp":1771046016259,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T00:00:00Z","timestamp":1619740800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T00:00:00Z","timestamp":1619740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC 2050\/1-Project ID 390696704"],"award-info":[{"award-number":["EXC 2050\/1-Project ID 390696704"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The bigraph theory, devised by Robin Milner, is a recent mathematical framework for concurrent processes. Its generality is able to subsume many existing process calculi, for example, CCS, CSP, and Petri nets. Further, it provides a uniform proof of bisimilarity, which is a congruence. We present the first <jats:italic>canonical string encoding<\/jats:italic> for <jats:italic>pure and lean bigraphs<\/jats:italic> by lifting the breadth-first canonical form of rooted unordered trees to a unique representation for bigraphs up to isomorphism (i.e., <jats:italic>lean-support equivalence<\/jats:italic>). The encoding\u2019s applicability is limited to atomic alphabets. The time complexity is <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^{2}k\\, d \\log {d})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mspace\/>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>n<\/jats:italic> is the number of places, <jats:italic>d<\/jats:italic> the degree of the place graph and <jats:italic>k<\/jats:italic> the maximum arity of a bigraph\u2019s signature. We provide proof of the correctness of our method and also conduct experimental measurements to assess the complexity.<\/jats:p>","DOI":"10.1007\/s42979-021-00552-5","type":"journal-article","created":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T10:49:51Z","timestamp":1620038991000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Canonical String Encoding for Pure Bigraphs"],"prefix":"10.1007","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6334-2356","authenticated-orcid":false,"given":"Dominik","family":"Grzelak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uwe","family":"A\u00dfmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,30]]},"reference":[{"key":"552_CR1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-540-39644-4_6","volume-title":"Discovery science, lecture notes in computer science","author":"T Asai","year":"2003","unstructured":"Asai T, Arimura H, Uno T, Si Nakano. Discovering frequent substructures in large unordered trees. In: Grieser G, Tanaka Y, Yamamoto A, editors. Discovery science, lecture notes in computer science. Berlin: Springer; 2003. p. 47\u201361. https:\/\/doi.org\/10.1007\/978-3-540-39644-4_6."},{"key":"552_CR2","doi-asserted-by":"crossref","unstructured":"Babai L. Graph isomorphism in quasipolynomial time. CoRR. 2015. arxiv:1512.03547.","DOI":"10.1145\/2897518.2897542"},{"key":"552_CR3","doi-asserted-by":"publisher","unstructured":"Babai L. Graph isomorphism in quasipolynomial time [Extended Abstract]. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC \u201916. ACM; 2016. p. 684\u201397. https:\/\/doi.org\/10.1145\/2897518.2897542.","DOI":"10.1145\/2897518.2897542"},{"key":"552_CR4","doi-asserted-by":"publisher","unstructured":"Babai L, Luks EM. Canonical labeling of graphs. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC \u201983. ACM; 1983. p. 171\u201383. https:\/\/doi.org\/10.1145\/800061.808746.","DOI":"10.1145\/800061.808746"},{"key":"552_CR5","doi-asserted-by":"crossref","unstructured":"Bacci G, Grohmann D, Miculan M. DBtk: a toolkit for directed bigraphs. In: Proceedings of the 3rd International Conference on Algebra and Coalgebra in Computer Science, CALCO\u201909. Springer-Verlag; 2009. p. 413\u201322. http:\/\/dl.acm.org\/citation.cfm?id=1812941.1812978.","DOI":"10.1007\/978-3-642-03741-2_28"},{"key":"552_CR6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-662-45917-1_2","volume-title":"Trustworthy global computing, lecture notes in computer science","author":"G Bacci","year":"2014","unstructured":"Bacci G, Miculan M, Rizzi R. Finding a forest in a tree. In: Maffei M, Tuosto E, editors. Trustworthy global computing, lecture notes in computer science. Berlin: Springer; 2014. p. 17\u201333."},{"key":"552_CR7","doi-asserted-by":"crossref","unstructured":"Beamer S, Asanovi\u0107 K, Patterson D. Direction-optimizing breadth-first search. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC \u201912. IEEE Computer Society Press; 2012. p. 12:1\u201312:10.","DOI":"10.1109\/SC.2012.50"},{"key":"552_CR8","unstructured":"Beamer S, Asanovi\u0107 K, Patterson DA. Searching for a parent instead of fighting over children: a fast breadth-first search implementation for Graph500. 2011. Technical Report, UCB\/EECS-2011-117, EECS Department, University of California, Berkeley. URL http:\/\/www2.eecs.berkeley.edu\/Pubs\/TechRpts\/2011\/EECS-2011-117.html."},{"issue":"3","key":"552_CR9","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1016\/0095-8956(72)90058-5","volume":"13","author":"C Berge","year":"1972","unstructured":"Berge C, Rado R. Note on isomorphic hypergraphs and some extensions of Whitney\u2019s theorem to families of sets. J Combin Theory Ser B. 1972;13(3):226\u201341. https:\/\/doi.org\/10.1016\/0095-8956(72)90058-5.","journal-title":"J Combin Theory Ser B"},{"issue":"4","key":"552_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.entcs.2007.04.013","volume":"175","author":"L Birkedal","year":"2007","unstructured":"Birkedal L, Damgaard TC, Glenstrup AJ, Milner R. Matching of bigraphs. Electron Notes Theor Comput Sci. 2007;175(4):3\u201319. https:\/\/doi.org\/10.1016\/j.entcs.2007.04.013.","journal-title":"Electron Notes Theor Comput Sci"},{"key":"552_CR11","doi-asserted-by":"publisher","first-page":"287","DOI":"10.3233\/FI-2014-1103","volume":"134","author":"R Bruni","year":"2014","unstructured":"Bruni R, Montanari U, Plotkin G, Terreni D. On hierarchical graphs: reconciling bigraphs, Gs-monoidal theories and Gs-graphs. Fundamenta Informaticae. 2014;134:287\u2013317. https:\/\/doi.org\/10.3233\/FI-2014-1103.","journal-title":"Fundamenta Informaticae"},{"key":"552_CR12","unstructured":"Buluc A, Beamer S, Madduri K, Asanovic K, Patterson D. Distributed-memory breadth-first search on massive graphs. CoRR. 2017. arxiv:1705.04590."},{"key":"552_CR13","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/11553595_57","volume-title":"Image analysis and processing\u2013ICIAP 2005","author":"H Bunke","year":"2005","unstructured":"Bunke H, Dickinson P, Kraetzl M. Theoretical and algorithmic framework for hypergraph matching. In: Roli F, Vitulano S, editors. Image analysis and processing\u2013ICIAP 2005, vol. 3617. Berlin: Springer; 2005. p. 463\u201370. https:\/\/doi.org\/10.1007\/11553595_57."},{"issue":"1\u20132","key":"552_CR14","first-page":"161","volume":"66","author":"Y Chi","year":"2005","unstructured":"Chi Y, Muntz RR, Nijssen S, Kok JN. Frequent subtree mining\u2014an overview. Fundamenta Informaticae. 2005;66(1\u20132):161\u201398.","journal-title":"Fundamenta Informaticae"},{"issue":"2","key":"552_CR15","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s10115-004-0180-7","volume":"8","author":"Y Chi","year":"2005","unstructured":"Chi Y, Yang Y, Muntz RR. Canonical forms for labelled trees and their applications in frequent subtree mining. Knowl Inf Syst. 2005;8(2):203\u201334. https:\/\/doi.org\/10.1007\/s10115-004-0180-7.","journal-title":"Knowl Inf Syst"},{"key":"552_CR16","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-030-51372-6_3","volume-title":"Graph transformation, lecture notes in computer science","author":"A Chiapperini","year":"2020","unstructured":"Chiapperini A, Miculan M, Peressotti M. Computing embeddings of directed bigraphs. In: Gadducci F, Kehrer T, editors. Graph transformation, lecture notes in computer science. Springer International Publishing: Berlin; 2020. p. 38\u201356. https:\/\/doi.org\/10.1007\/978-3-030-51372-6_3."},{"key":"552_CR17","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1007\/11523468_62","volume-title":"Automata, languages and programming, lecture notes in computer science","author":"G Conforti","year":"2005","unstructured":"Conforti G, Macedonio D, Sassone V. Spatial logics for bigraphs. In: Caires L, Italiano GF, Monteiro L, Palamidessi C, Yung M, editors. Automata, languages and programming, lecture notes in computer science. Berlin: Springer; 2005. p. 766\u201378."},{"issue":"03","key":"552_CR18","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1142\/S0218001404003228","volume":"18","author":"D Conte","year":"2004","unstructured":"Conte D, Foggia P, Sansone C, Vento M. Thirty years of graph matching in pattern recognition. Int J Pattern Recognit Artif Intell. 2004;18(03):265\u201398. https:\/\/doi.org\/10.1142\/S0218001404003228.","journal-title":"Int J Pattern Recognit Artif Intell"},{"issue":"2","key":"552_CR19","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s00165-011-0184-5","volume":"25","author":"TC Damgaard","year":"2013","unstructured":"Damgaard TC, Glenstrup AJ, Birkedal L, Milner R. An inductive characterization of matching in binding bigraphs. Formal Aspects Comput. 2013;25(2):257\u201388. https:\/\/doi.org\/10.1007\/s00165-011-0184-5.","journal-title":"Formal Aspects Comput"},{"key":"552_CR20","volume-title":"Monographs in theoretical computer science. An EATCS series","author":"H Ehrig","year":"2006","unstructured":"Ehrig H, Ehrig K, Prange U, Taentzer G. Fundamentals of algebraic graph transformation. In: Monographs in theoretical computer science. An EATCS series. Berlin: Springer; 2006."},{"key":"552_CR21","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/3-540-64299-4_36","volume-title":"Recent trends in algebraic development techniques, lecture notes in computer science","author":"F Gadducci","year":"1998","unstructured":"Gadducci F, Heckel R. An inductive view of graph transformation. In: Presicce FP, editor. Recent trends in algebraic development techniques, lecture notes in computer science. Berlin: Springer; 1998. p. 223\u201337. https:\/\/doi.org\/10.1007\/3-540-64299-4_36."},{"key":"552_CR22","volume-title":"Computers and intractability: a guide to the theory of np-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS. Computers and intractability: a guide to the theory of np-completeness. New York: W. H. Freeman & Co; 1979."},{"key":"552_CR23","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.dam.2018.07.006","volume":"253","author":"A Gassara","year":"2019","unstructured":"Gassara A, Bouassida Rodriguez I, Jmaiel M, Drira K. Executing bigraphical reactive systems. Discrete Appl Math. 2019;253:73\u201392. https:\/\/doi.org\/10.1016\/j.dam.2018.07.006.","journal-title":"Discrete Appl Math"},{"key":"552_CR24","unstructured":"Glenstrup AJ, Damgaard TC, Birkedal L, H\u00f8jsgaard E. An implementation of bigraph matching. 2010. Technical Report, TR-2010-135, IT University of Copenhagen, Denmark. ISSN 1600\u20136100. ISBN 978\u201387\u20137949\u2013228\u20138."},{"key":"552_CR25","unstructured":"Grzelak D, Priwitzer B, A\u00dfmann U. Generating random bigraphs with preferential attachment. CoRR. 2020. arxiv:2002.07448."},{"key":"552_CR26","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/479\/09345","author":"S Hartke","year":"2013","unstructured":"Hartke S, Radcliffe A. McKay\u2019s canonical graph labeling algorithm. Contemp Math Book Ser. 2013. https:\/\/doi.org\/10.1090\/conm\/479\/09345.","journal-title":"Contemp Math Book Ser."},{"key":"552_CR27","unstructured":"H\u00f8jsgaard E. Bigraphical languages and their simulation. 2012. PhD Dissertation. https:\/\/core.ac.uk\/download\/pdf\/50526631.pdf."},{"key":"552_CR28","unstructured":"Luccio F, Mesa\u00a0Enriquez A, Olivares\u00a0Rieumont P, Pagli L. Bottom-up subtree isomorphism for unordered labeled trees. 2004. Technical Report, TR-04-13, Dipartimento di Informatica, Universit\u00e0 di Pisa, Italy. http:\/\/compass2.di.unipi.it\/TR\/files\/TR-04-13.ps.gz."},{"key":"552_CR29","doi-asserted-by":"publisher","unstructured":"Luks EM. Isomorphism of graphs of bounded valence can be tested in polynomial time. In: 21st Annual Symposium on Foundations of Computer Science (Sfcs 1980). 1980. p. 42\u20139. https:\/\/doi.org\/10.1109\/SFCS.1980.24.","DOI":"10.1109\/SFCS.1980.24"},{"key":"552_CR30","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","volume":"60","author":"BD McKay","year":"2014","unstructured":"McKay BD, Piperno A. Practical graph isomorphism, II. J Symb Computat. 2014;60:94\u2013112. https:\/\/doi.org\/10.1016\/j.jsc.2013.09.003.","journal-title":"J Symb Computat"},{"key":"552_CR31","unstructured":"Miculan M, Peressotti M. A CSP implementation of the bigraph embedding problem. CoRR. 2014. arxiv:1412.1042."},{"key":"552_CR32","unstructured":"Milner R. Bigraphical reactive systems: basic theory. 2001. Technical Report UCAM-CL-TR-523, University of Cambridge, Computer Laboratory. ISSN 1476-2986."},{"key":"552_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626661","volume-title":"The space and motion of communicating agents","author":"R Milner","year":"2009","unstructured":"Milner R. The space and motion of communicating agents. 1st ed. Cambridge: Cambridge University Press; 2009.","edition":"1"},{"key":"552_CR34","unstructured":"Nijssen S, Kok JN. Efficient discovery of frequent unordered trees. In: In First International Workshop on Mining Graphs, Trees and Sequences. 2003. p. 55\u201364."},{"key":"552_CR35","unstructured":"Perrone G. Domain-specific modelling languages in bigraphs; 2013. PhD Dissertation, IT University of Copenhagen, Denmark."},{"key":"552_CR36","unstructured":"Prud\u2019homme C, Fages JG, Lorca X. Choco solver documentation. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S. 2016. http:\/\/www.choco-solver.org."},{"key":"552_CR37","doi-asserted-by":"publisher","unstructured":"R\u00fcckert U, Kramer S. Frequent free tree discovery in graph data. In: Proceedings of the 2004 ACM Symposium on Applied Computing, SAC \u201904. ACM; 2004. p. 564\u201370. https:\/\/doi.org\/10.1145\/967900.968018.","DOI":"10.1145\/967900.968018"},{"key":"552_CR38","doi-asserted-by":"crossref","unstructured":"Schweitzer P, Wiebking D. A unifying method for the design of algorithms canonizing combinatorial objects. CoRR. 2019. arxiv:1806.07466.","DOI":"10.1145\/3313276.3316338"},{"key":"552_CR39","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.tcs.2015.02.011","volume":"577","author":"M Sevegnani","year":"2015","unstructured":"Sevegnani M, Calder M. Bigraphs with sharing. Theoret Comput Sci. 2015;577:43\u201373. https:\/\/doi.org\/10.1016\/j.tcs.2015.02.011.","journal-title":"Theoret Comput Sci"},{"key":"552_CR40","doi-asserted-by":"publisher","unstructured":"Sevegnani M, Calder M. BigraphER: rewriting and analysis engine for bigraphs. In: Chaudhuri S, Farzan A, editors. 28th International Conference on Computer Aided Verification, vol. 9780. Springer International Publishing; 2016. p. 494\u2013501. https:\/\/doi.org\/10.1007\/978-3-319-41540-6_27.","DOI":"10.1007\/978-3-319-41540-6_27"},{"key":"552_CR41","unstructured":"Sevegnani M, Unsworth C, Calder M. A SAT based algorithm for the matching problem in bigraphs with sharing. 2010. Technical Report. University of Glasgow. http:\/\/dcs.gla.ac.uk\/~michele\/papers\/tech_match.pdf."},{"issue":"2","key":"552_CR42","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1999.1044","volume":"33","author":"R Shamir","year":"1999","unstructured":"Shamir R, Tsur D. Faster subtree isomorphism. J Algorithms. 1999;33(2):267\u201380. https:\/\/doi.org\/10.1006\/jagm.1999.1044.","journal-title":"J Algorithms"},{"issue":"1","key":"552_CR43","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"JR Ullmann","year":"1976","unstructured":"Ullmann JR. An algorithm for subgraph isomorphism. J ACM. 1976;23(1):31\u201342. https:\/\/doi.org\/10.1145\/321921.321925.","journal-title":"J ACM"},{"key":"552_CR44","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04921-1","volume-title":"Algorithms on trees and graphs","author":"G Valiente","year":"2002","unstructured":"Valiente G. Algorithms on trees and graphs. Berlin: Springer; 2002. https:\/\/doi.org\/10.1007\/978-3-662-04921-1."},{"key":"552_CR45","unstructured":"Wachter M, Haenni R. Propositional DAGs: a new graph-based language for representing boolean functions. In: Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasoning, KR\u201906. AAAI Press; 2006. p. 277\u201385."}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00552-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-021-00552-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-021-00552-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,26]],"date-time":"2021-06-26T20:11:35Z","timestamp":1624738295000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-021-00552-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,30]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["552"],"URL":"https:\/\/doi.org\/10.1007\/s42979-021-00552-5","relation":{},"ISSN":["2662-995X","2661-8907"],"issn-type":[{"value":"2662-995X","type":"print"},{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,30]]},"assertion":[{"value":"19 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"246"}}