{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T08:41:13Z","timestamp":1759740073996,"version":"build-2065373602"},"reference-count":38,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T00:00:00Z","timestamp":1759622400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"12th batch of Wenzhou Science and Technology Commissioner Project","award":["12"],"award-info":[{"award-number":["12"]}]},{"name":"Third Phase of the Ministry of Education\u2019s supply and Demand Docking Employment and Education Project","award":["2023122963332"],"award-info":[{"award-number":["2023122963332"]}]},{"name":"Second Phase of the Ministry of Education\u2019s supply and Demand Docking Employment and Education Project","award":["20230112193"],"award-info":[{"award-number":["20230112193"]}]}],"content-domain":{"domain":["www.mdpi.com"],"crossmark-restriction":true},"short-container-title":["Symmetry"],"abstract":"<jats:p>A graph simulation and its variants are widely used in graph pattern matching. Among them, there have been related works involving the addition of regular expressions to graph patterns, which can discover more meaningful data and solve problems in polynomial time. In this research, which is based on Fan\u2019s investigations, we first propose an approximation of graph simulation using the concept of metric and formal verification techniques, and then give the definition of approximate matching between pattern graphs with regular expressions and data graphs, which introduces a symmetric tolerance for errors, bridging exact and approximate matching. Finally, we present a logical characterization of the approximate graph simulation by extending Hennessy\u2013Milner logic.<\/jats:p>","DOI":"10.3390\/sym17101659","type":"journal-article","created":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T08:10:51Z","timestamp":1759738251000},"page":"1659","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Logical Characterization for Approximate Matching of Pattern Graphs with Regular Expressions"],"prefix":"10.3390","volume":"17","author":[{"given":"Xinfei","family":"Liao","sequence":"first","affiliation":[{"name":"Faculty Development Center, Wenzhou Polytechnic, Wenzhou 325035, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zuoli","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Intelligent Manufacturing, Wenzhou Polytechnic, Wenzhou 325035, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinyu","family":"Cui","sequence":"additional","affiliation":[{"name":"School of Computer and Information Security, Guilin University of Electronic Science and Technology, Guilin 541004, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jin","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer and Information Security, Guilin University of Electronic Science and Technology, Guilin 541004, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Intelligent Manufacturing, Wenzhou Polytechnic, Wenzhou 325035, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuelei","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Intelligent Manufacturing, Wenzhou Polytechnic, Wenzhou 325035, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,10,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Aceto, L., Ing\u00f3lfsd\u00f3ttir, A., Larsen, K.G., and Srba, J. (2007). Reactive Systems: Modelling, Specification and Verification, Cambridge University Press.","DOI":"10.1017\/CBO9780511814105"},{"key":"ref_2","unstructured":"Baier, C., and Katoen, J.P. (2008). Principles of Model Checking, MIT Press."},{"key":"ref_3","unstructured":"Milner, R. (1989). Communication and Concurrency, Prentice Hall."},{"key":"ref_4","unstructured":"Milner, R. (1999). Communicating and Mobile Systems: The \u03c0-Calculus, Cambridge University Press."},{"key":"ref_5","unstructured":"Munkres, J.R. (1975). Typology, Prentice Hall."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Sangiorgi, D. (2012). Introduction to Bisimulation and Coinduction, Cambridge University Press.","DOI":"10.1017\/CBO9780511777110"},{"key":"ref_7","unstructured":"Hopcroft, J.E., Motwani, R., and Ullman, J.D. (1979). Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1109\/TSE.2008.106","article-title":"Linear and branching system metrics","volume":"35","author":"Faella","year":"2009","journal-title":"IEEE Trans. Softw. Eng."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"782","DOI":"10.1109\/TAC.2007.895849","article-title":"Approximation metrics for discrete and continuous systems","volume":"52","author":"Girard","year":"2007","journal-title":"IEEE Trans. Autom. Control"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/s11704-012-1312-y","article-title":"Adding regular expressions to graph reachability and pattern queries","volume":"6","author":"Fan","year":"2012","journal-title":"Front. Comput. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3439724","article-title":"A survey on distributed graph pattern matching in massive graphs","volume":"54","author":"Bouhenni","year":"2021","journal-title":"ACM Comput. Surv."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2528937","article-title":"Strong simulation: Capturing topology in graph pattern matching","volume":"39","author":"Ma","year":"2014","journal-title":"ACM Trans. Database Syst."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1016\/j.ijar.2013.11.009","article-title":"Simulation for lattice-valued doubly labeled transition systems","volume":"55","author":"Pan","year":"2014","journal-title":"Int. J. Approx. Reason."},{"key":"ref_14","unstructured":"Henzinger, M.R., Henzinger, T.A., and Kopke, P.W. (1995, January 23\u201325). Computing simulations on finite and infinite graphs. Proceedings of the 36th Annual Symposium on Foundations of Computer Science, Milwaukee, WI, USA."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/2489791","article-title":"Incremental graph pattern matching","volume":"38","author":"Fan","year":"2013","journal-title":"ACM Trans. Database Syst."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Chen, X.S., Lai, L., Qin, L., Lin, X.M., and Liu, B. (2021, January 19\u201322). A framework to quantify approximate simulation on graph data. Proceedings of the 37th IEEE International Conference on Data Engineering, Chania, Greece.","DOI":"10.1109\/ICDE51399.2021.00117"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/j.patrec.2020.03.019","article-title":"Error-Tolerant Approximate Graph Matching Utilizing Node Centrality Information","volume":"133","author":"Dwivedi","year":"2020","journal-title":"Pattern Recogn. Lett."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"7050","DOI":"10.1109\/TPAMI.2021.3121646","article-title":"LogicENN: A Neural Based Knowledge Graphs Embedding Model with Logical Rules","volume":"45","author":"Nayyeri","year":"2023","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_19","unstructured":"Barcel\u00f3, P., Kostylev, E.V., Mika\u00ebl, M., P\u00e9rez, J., Reutter, J., and Silva, J.P. (2020, January 26\u201330). The Logical Expressiveness of Graph Neural Networks. Proceedings of the 8th International Conference on Learning Representations, Addis Ababa, Ethiopia."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/TNNLS.2020.2978386","article-title":"A Comprehensive Survey on Graph Neural Networks","volume":"32","author":"Wu","year":"2021","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_21","unstructured":"Zhang, M., and Chen, Y. (2018, January 3\u20138). Link Prediction Based on Graph Neural Networks. Proceedings of the 32nd Conference on Neural Information Processing Systems, NIPS 2018, Montr\u00e9al, QC, Canada."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Cui, X.Y., Li, Z.K., Chang, Y.T., and Pan, H.Y. (2022, January 26\u201328). Approximate Simulation for Transition Systems with Regular Expressions. Proceedings of the 2nd Artificial Intelligence Logic and Applications, AILA 2022, Shanghai, China.","DOI":"10.1007\/978-981-19-7510-3_4"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1050","DOI":"10.1109\/TKDE.2017.2785824","article-title":"MCS-GPM: Multi-constrained simulation based graph pattern matching in contextual social graphs","volume":"30","author":"Liu","year":"2018","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.knosys.2017.11.008","article-title":"Personalized graph pattern matching via limited simulation","volume":"141","author":"Du","year":"2018","journal-title":"Knowl.-Based Syst."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/321921.321925","article-title":"An algorithm for subgraph isomorphism","volume":"23","author":"Ullmann","year":"1976","journal-title":"J. ACM."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.14778\/1920841.1920988","article-title":"Subgraph indexing and approximate matching in large graphs","volume":"3","author":"Zhang","year":"2010","journal-title":"Proc. VLDB Endow."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1016\/j.jlap.2010.07.010","article-title":"Quantitative analysis of weighted transition system","volume":"79","author":"Thrane","year":"2010","journal-title":"J. Log. Algebr. Program."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/j.tcs.2011.08.002","article-title":"Simulation distances","volume":"413","author":"Henzinger","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"104498","DOI":"10.1016\/j.ic.2019.104498","article-title":"Model checking interval temporal logics with regular expressions","volume":"272","author":"Bozzelli","year":"2020","journal-title":"Inf. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.fss.2015.09.012","article-title":"Logical characterizations of simulation and bisimulation for fuzzy transition systems","volume":"301","author":"Wu","year":"2016","journal-title":"Fuzzy Sets Syst."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.ic.2017.01.002","article-title":"Model theory of XPath on data trees","volume":"255","author":"Abriola","year":"2017","journal-title":"Inf. Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/j.ic.2010.11.024","article-title":"Probabilistic logical characterization","volume":"209","author":"Hermanns","year":"2011","journal-title":"Inf. Comput."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s00236-014-0210-1","article-title":"Revisiting bisimilarity and its modal logic for nondeterministic and probabilistic processes","volume":"52","author":"Bernardo","year":"2015","journal-title":"Acta Inform."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.tcs.2013.07.030","article-title":"The quantitative linear-time-branching-time spectrum","volume":"538","author":"Fahrenberg","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.ijar.2016.11.020","article-title":"Nondeterministic fuzzy automata with membership values in complete residuated lattices","volume":"82","author":"Pan","year":"2017","journal-title":"Int. J. Approx. Reason."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1016\/j.jlap.2012.03.008","article-title":"Modal transition systems with weight intervals","volume":"81","author":"Juhl","year":"2012","journal-title":"J. Log. Algebr. Program."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/j.tcs.2003.09.013","article-title":"Metrics for labelled Markov processes","volume":"318","author":"Desharnais","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/2455.2460","article-title":"Algebraic Laws for Nondeterminism and Concurrency","volume":"32","author":"Hennessy","year":"1985","journal-title":"J. ACM"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/10\/1659\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T08:21:09Z","timestamp":1759738869000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/10\/1659"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,5]]},"references-count":38,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2025,10]]}},"alternative-id":["sym17101659"],"URL":"https:\/\/doi.org\/10.3390\/sym17101659","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,5]]}}}