{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T02:27:03Z","timestamp":1747189623097,"version":"3.40.5"},"reference-count":26,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Patt. Recogn. Artif. Intell."],"published-print":{"date-parts":[[2021,3,15]]},"abstract":"<jats:p> Graph pattern matching that aims to seek out answer graphs in a data graph matching a provided graph, plays a fundamental role as a part of graph search for graph databases. \u201cMatching\u201d indicates that the two graphs are correlated, such as bisimulation, isomorphism, simulation, etc. The strictness of bisimulation is between simulation and isomorphism. Seldom work has been done to search for bisimulation subgraphs. This research focuses on the problem. The symbol [Formula: see text] is introduced to fundamental modal logic language, thereby yielding [Formula: see text] language; the symbols [Formula: see text] is added for forming [Formula: see text] formulas. Then conclusions about graph bisimulations are shown. Subsequently, a theorem with detailed proof is presented, stating that [Formula: see text] formulas characterize finite directed graphs modulo bisimulation. According to the conclusions and theorem, algorithms for finding subgraphs are proposed. After dividing the query graph, the match graphs undergo the characterization using [Formula: see text] formulas. In the data graphs, by model checking the formulas, the answer graphs exhibiting bisimilarity to the match graphs are able to be captured. <\/jats:p>","DOI":"10.1142\/s0218001421500117","type":"journal-article","created":{"date-parts":[[2020,8,31]],"date-time":"2020-08-31T05:45:02Z","timestamp":1598852702000},"page":"2150011","source":"Crossref","is-referenced-by-count":1,"title":["Graph Pattern Matching: Capturing Bisimilar Subgraph"],"prefix":"10.1142","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2604-6675","authenticated-orcid":false,"given":"Rui","family":"Qiao","sequence":"first","affiliation":[{"name":"College of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan, P.\u00a0R.\u00a0China"},{"name":"Hubei Province Key Laboratory of Intelligent Information, Processing and Real-Time Industrial System, Wuhan, P.\u00a0R.\u00a0China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Feng","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan, P.\u00a0R.\u00a0China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heng","family":"He","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan, P.\u00a0R.\u00a0China"},{"name":"Hubei Province Key Laboratory of Intelligent Information, Processing and Real-Time Industrial System, Wuhan, P.\u00a0R.\u00a0China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaolei","family":"Zhong","sequence":"additional","affiliation":[{"name":"Yunnan University, Yunnan, P.\u00a0R.\u00a0China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2020,10,28]]},"reference":[{"key":"S0218001421500117BIB002","doi-asserted-by":"publisher","DOI":"10.1145\/1322432.1322433"},{"key":"S0218001421500117BIB003","volume-title":"Modal Logic","volume":"53","author":"Blackburn P.","year":"2002"},{"key":"S0218001421500117BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90098-9"},{"volume-title":"Model Checking","year":"1999","author":"Clarke E. M.","key":"S0218001421500117BIB005"},{"key":"S0218001421500117BIB006","doi-asserted-by":"publisher","DOI":"10.1093\/pcp\/pcv200"},{"issue":"2","key":"S0218001421500117BIB008","first-page":"143","volume":"35","author":"Dovier A.","year":"2009","journal-title":"Comput. Lang. Syst. Str."},{"key":"S0218001421500117BIB010","doi-asserted-by":"publisher","DOI":"10.1145\/3310230"},{"key":"S0218001421500117BIB011","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380585"},{"key":"S0218001421500117BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-016-0025-x"},{"key":"S0218001421500117BIB013","first-page":"427","author":"Fan W.","year":"2018","journal-title":"International Conference on Management of Data"},{"key":"S0218001421500117BIB014","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"},{"key":"S0218001421500117BIB015","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920986"},{"key":"S0218001421500117BIB016","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00060"},{"key":"S0218001421500117BIB018","doi-asserted-by":"publisher","DOI":"10.1145\/2489791"},{"key":"S0218001421500117BIB019","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915232"},{"key":"S0218001421500117BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16901-4_38"},{"key":"S0218001421500117BIB021","first-page":"45","volume-title":"National Conference on Artificial Intelligence","author":"Gallagher B.","year":"2006"},{"volume-title":"Concepts, Algorithms, and Tools for Model Checking","year":"1999","author":"Katoen J.-P.","key":"S0218001421500117BIB024"},{"key":"S0218001421500117BIB025","first-page":"310","author":"Ma S.","year":"2011","journal-title":"Very Large Data Bases"},{"key":"S0218001421500117BIB026","doi-asserted-by":"publisher","DOI":"10.1145\/2528937"},{"key":"S0218001421500117BIB027","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187963"},{"key":"S0218001421500117BIB028","doi-asserted-by":"publisher","DOI":"10.1109\/DTA.2015.8"},{"key":"S0218001421500117BIB029","doi-asserted-by":"publisher","DOI":"10.1007\/b94902"},{"volume-title":"Graph Database: New Opportunities for Connected Data","year":"2015","author":"Robinson I.","key":"S0218001421500117BIB030"},{"key":"S0218001421500117BIB031","first-page":"199","volume-title":"International Conference on Computing for Sustainable Global Development","author":"Singh K.","year":"2016"},{"volume-title":"A Survey of Tools for Model Checking and Model-Based Development","year":"2006","author":"Strunk E. A.","key":"S0218001421500117BIB032"}],"container-title":["International Journal of Pattern Recognition and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218001421500117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,18]],"date-time":"2021-03-18T10:22:10Z","timestamp":1616062930000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218001421500117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,28]]},"references-count":26,"journal-issue":{"issue":"03","published-print":{"date-parts":[[2021,3,15]]}},"alternative-id":["10.1142\/S0218001421500117"],"URL":"https:\/\/doi.org\/10.1142\/s0218001421500117","relation":{},"ISSN":["0218-0014","1793-6381"],"issn-type":[{"type":"print","value":"0218-0014"},{"type":"electronic","value":"1793-6381"}],"subject":[],"published":{"date-parts":[[2020,10,28]]}}}