{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T04:12:29Z","timestamp":1775016749499,"version":"3.50.1"},"reference-count":25,"publisher":"Pleiades Publishing Ltd","issue":"7","license":[{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2019,12,1]],"date-time":"2019-12-01T00:00:00Z","timestamp":1575158400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Program Comput Soft"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1134\/s0361768819070041","type":"journal-article","created":{"date-parts":[[2019,12,16]],"date-time":"2019-12-16T11:02:45Z","timestamp":1576494165000},"page":"357-364","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Path Querying with Conjunctive Grammars by Matrix Multiplication"],"prefix":"10.1134","volume":"45","author":[{"given":"R.","family":"Azimov","sequence":"first","affiliation":[]},{"given":"S.","family":"Grigorev","sequence":"additional","affiliation":[]}],"member":"137","published-online":{"date-parts":[[2019,12,16]]},"reference":[{"issue":"3","key":"7080_CR1","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1137\/S0097539798337716","volume":"30","author":"Chris Barrett","year":"2000","unstructured":"Barrett, Ch., Jacob, R., and Marathe, M., Formal-language-constrained path problems, SIAM J. Comput., 2000, vol. 30, no. 3, pp. 09\u2013837.","journal-title":"SIAM Journal on Computing"},{"key":"7080_CR2","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1145\/2775051.2676977","volume":"50","author":"O. Bastani","year":"2015","unstructured":"Bastani, O., Anand, S., and Aiken, A., Specification inference using context-free language reachability, ACM SIGPLAN Notices, ACM, 2015, vol. 50, pp.\u00a0553\u2013566.","journal-title":"ACM SIGPLAN Notices, ACM"},{"key":"7080_CR3","first-page":"98","volume":"9","author":"G. Xu","year":"2009","unstructured":"Xu, G., Rountev, A., and Sridharan, M., Scaling c-reachability-based points-to analysis using context-sensitive must-not-alias analysis, ECOOP, Springer, 2009, vol. 9, pp. 98\u2013122.","journal-title":"ECOOP, Springer"},{"key":"7080_CR4","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1016\/S0950-5849(98)00093-7","volume":"40","author":"T. Reps","year":"1998","unstructured":"Reps, T., Program analysis via graph reachability, Inf. Software Technol., 1998, vol. 40, no. 11, pp. 701\u2013726.","journal-title":"Inf. Software Technol."},{"key":"7080_CR5","doi-asserted-by":"crossref","unstructured":"Zhang, Q. and Su, Z., Context-sensitive data-dependence analysis via linear conjunctive language reachability, Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, ACM, 2017, pp. 344\u2013358.","DOI":"10.1145\/3009837.3009848"},{"key":"7080_CR6","unstructured":"Hellings, J., Conjunctive Context-Free Path Queries, 2014."},{"key":"7080_CR7","doi-asserted-by":"crossref","unstructured":"Azimov, R. and Grigorev, S., Context-free path querying by matrix multiplication, Proceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA), ACM, 2018, p. 5.","DOI":"10.1145\/3210259.3210264"},{"key":"7080_CR8","doi-asserted-by":"crossref","unstructured":"Grigorev, S. and Ragozina, A., Context-free path querying with structural representation of result, Proceedings of the 13th Central and Eastern European Software Engineering Conference in Russia, ACM, 2017, p. 10.","DOI":"10.1145\/3166094.3166104"},{"key":"7080_CR9","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1515\/jib-2008-100","volume":"5","author":"P. Sevon","year":"2008","unstructured":"Sevon, P. and Eronen, L., Subgraph queries by context-free grammars, J. Integrative Bioinformatics, 2008, vol.\u00a05, no. 2, p. 100.","journal-title":"J. Integrative Bioinformatics"},{"key":"7080_CR10","doi-asserted-by":"crossref","unstructured":"Zhang, X., Feng, Z., Wang, X., Rao, G., and Wu, W., Context-free path queries on rdf graphs, International Semantic Web Conference, Springer, 2016, pp. 632\u2013648.","DOI":"10.1007\/978-3-319-46523-4_38"},{"key":"7080_CR11","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.cosrev.2013.06.001","volume":"9","author":"A. Okhotin","year":"2013","unstructured":"Okhotin, A., Conjunctive and boolean grammars: the true general case of the context-free grammars, Comput. Sci. Rev., 2013, vol. 9, pp. 27\u201359.","journal-title":"Comput. Sci. Rev."},{"key":"7080_CR12","first-page":"519","volume":"6","author":"A. Okhotin","year":"2001","unstructured":"Okhotin, A., Conjunctive grammars, J. Automata, Languages,Combinatorics, 2001, vol. 6, no. 4, pp. 519\u2013535.","journal-title":"Combinatorics"},{"key":"7080_CR13","doi-asserted-by":"crossref","unstructured":"Abiteboul, S. and Vianu, V., Regular path queries with constraints, Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ACM, 1997, pp. 122\u2013133.","DOI":"10.1145\/263661.263676"},{"key":"7080_CR14","doi-asserted-by":"crossref","unstructured":"Fan, W., Li, J., Ma, Sh., Tang, N., and Wu, Y., Adding regular expressions to graph reachability and pattern queries, Data Engineering (ICDE),2011IEEE 27th International Conference on, IEEE, 2011, pp. 39\u201350.","DOI":"10.1109\/ICDE.2011.5767858"},{"key":"7080_CR15","doi-asserted-by":"crossref","unstructured":"Nol\u00e9, M. and Sartiani, C., Regular path queries on massive graphs, Proceedings of the 28th International Conference on Scientific and Statistical Database Management, ACM, 2016, p. 13.","DOI":"10.1145\/2949689.2949711"},{"key":"7080_CR16","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s00224-016-9676-2","volume":"61","author":"J.L. Reutter","year":"2017","unstructured":"Reutter, J.L., Romero, M., and Vardi, M.Y., Regular queries on graph databases, Theory Comput. Systems, 2017, vol. 61, no. 1, pp. 31\u201383.","journal-title":"Theory Comput. Systems"},{"key":"7080_CR17","volume-title":"An efficient recognition and syntax analysis algorithm for context-free languages, Technical report","author":"T. Kasami","year":"1965","unstructured":"Kasami, T., An efficient recognition and syntax analysis algorithm for context-free languages, Technical report, DTIC Document, 1965."},{"key":"7080_CR18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0019-9958(67)80007-X","volume":"10","author":"D.H. Younger","year":"1967","unstructured":"Younger, D.H., Recognition and parsing of context-free languages in time n3, Information and Control, 1967, vol. 10, no. 2, pp. 189\u2013208.","journal-title":"Information and Control"},{"key":"7080_CR19","volume-title":"Parsing Techniques (Monographs in Computer Science)","author":"D. Grune","year":"2006","unstructured":"Grune, D. and Jacobs, C.J.H., Parsing Techniques (Monographs in Computer Science), NJ, USA, Secaucus: Springer-Verlag-New York, Inc., 2006."},{"key":"7080_CR20","unstructured":"Hellings, J., Querying for paths in graphs using context-free path queries, arXiv preprint arXiv:1502.02242, 2015."},{"key":"7080_CR21","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/j.entcs.2010.08.041","volume":"253","author":"E. Scott","year":"2010","unstructured":"Scott, E. and Johnstone, A., Gll parsing, Electronic Notes in Theoretical Computer Science, 2010, vol. 253, no. 7, pp. 177\u2013189.","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"7080_CR22","doi-asserted-by":"crossref","unstructured":"Syme, D., Granicz, A., and Cisternino, A., Expert F# 3.0, Springer, 2012.","DOI":"10.1007\/978-1-4302-4651-0"},{"key":"7080_CR23","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/2370036.2145831","volume":"47","author":"M. Mendez-Lojo","year":"2012","unstructured":"Mendez-Lojo, M., Burtscher, M., and Pingali, K., A gpu implementation of inclusion-based points-to analysis, ACM SIGPLAN Notices, 2012, vol. 47, no. 8, pp.\u00a0107\u2013116.","journal-title":"ACM SIGPLAN Notices"},{"key":"7080_CR24","doi-asserted-by":"crossref","unstructured":"Yu Su, Ding Ye, and Jingling Xue, Accelerating inclusion-based pointer analysis on heterogeneous cpu-gpu systems, High Performance Computing (HiPC),201320th International Conference on, IEEE, 2013, pp. 149\u2013158.","DOI":"10.1109\/HiPC.2013.6799110"},{"key":"7080_CR25","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1109\/TPDS.2015.2397933","volume":"27","author":"Yu Su","year":"2016","unstructured":"Yu Su, Ding Ye, Jingling Xue, and Xiang-Ke Liao, An efficient gpu implementation of inclusion-based pointer analysis, IEEE Transactions on Parallel and Distributed Systems, 2016, vol. 27, no. 2, pp. 353\u2013366.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"}],"container-title":["Programming and Computer Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S0361768819070041.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1134\/S0361768819070041","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S0361768819070041.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T02:39:12Z","timestamp":1775011152000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1134\/S0361768819070041"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":25,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["7080"],"URL":"https:\/\/doi.org\/10.1134\/s0361768819070041","relation":{},"ISSN":["0361-7688","1608-3261"],"issn-type":[{"value":"0361-7688","type":"print"},{"value":"1608-3261","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12]]},"assertion":[{"value":"13 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 December 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}