{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T04:16:23Z","timestamp":1775016983306,"version":"3.50.1"},"reference-count":32,"publisher":"Pleiades Publishing Ltd","issue":"1","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:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[[2021,1]]},"DOI":"10.1134\/s036176882008006x","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T19:04:50Z","timestamp":1614020690000},"page":"88-98","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Path Querying on Acyclic Graphs Using Boolean Grammars"],"prefix":"10.1134","volume":"47","author":[{"given":"E. N.","family":"Shemetova","sequence":"first","affiliation":[]},{"given":"S. V.","family":"Grigorev","sequence":"additional","affiliation":[]}],"member":"137","published-online":{"date-parts":[[2021,2,23]]},"reference":[{"key":"3577_CR1","doi-asserted-by":"crossref","unstructured":"Barcel\u00f3 Baeza, P., Querying graph databases, Proc. 32nd ACM SIGMOD-SIGACTSIGAI Symp. Principles of Database Systems (PODS), 2013, pp. 175\u2013188.","DOI":"10.1145\/2463664.2465216"},{"key":"3577_CR2","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/S009753979122370X","volume":"24","author":"A. Mendelzon","year":"1995","unstructured":"Mendelzon, A. and Wood, P., Finding regular simple paths in graph databases, SIAM J. Comput., 1995, vol.\u00a024, no. 6, pp. 1235\u20131258.","journal-title":"SIAM J. Comput."},{"key":"3577_CR3","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-149","volume-title":"Quantifying variances in comparative RNA secondary structure prediction","author":"J.W. Anderson","year":"2013","unstructured":"Anderson, J.W., et al., Quantifying variances in comparative RNA secondary structure prediction, BMC Bioinf., 2013, vol. 14."},{"key":"3577_CR4","unstructured":"Chaudhary, A. and Faisal, A., Role of graph databases in social networks, 2016. http:\/\/www.researchgate.net\/publication\/304462174_Role_of_graph_databases_in_social_networks."},{"key":"3577_CR5","first-page":"271","volume":"33","author":"\u0141. Warcha\u0142","year":"2012","unstructured":"Warcha\u0142, \u0141., Using Neo4j graph database in social network analysis, Studia Inf., 2012, vol. 33, no. 2A, pp.\u00a0271\u2013279.","journal-title":"Studia Inf."},{"key":"3577_CR6","unstructured":"Reps, T., Program analysis via graph reachability, Proc. Int. Symp. Logic Programming (ILPS), 1997, pp. 5\u201319."},{"key":"3577_CR7","doi-asserted-by":"crossref","unstructured":"Zhang, Q. and Su, Z., Context-sensitive data-dependence analysis via linear conjunctive language reachability, Proc. 44th ACM SIGPLAN Symp. Principles of Programming Languages, 2017, pp. 344\u2013358.","DOI":"10.1145\/3009837.3009848"},{"key":"3577_CR8","doi-asserted-by":"crossref","unstructured":"Yuan, H. and Eugster, P., An efficient algorithm for solving the Dyck-CFL reachability problem on trees, Proc. 18th Eur. Symp. Programming Languages and Systems as part of Jt. Eur. Conf. Theory and Practice of Software (ETAPS), 2009, pp. 175\u2013189.","DOI":"10.1007\/978-3-642-00590-9_13"},{"key":"3577_CR9","unstructured":"Neo4j Inc., Neo4j's graph query language: An introduction to Cypher. https:\/\/neo4j.com\/developer\/cypher-query-language."},{"key":"3577_CR10","doi-asserted-by":"crossref","unstructured":"Rodriguez, M.A., The gremlin graph traversal machine and language (invited talk), Proc. 15th Symp. Database Programming Languages, 2015, pp. 1\u201310.","DOI":"10.1145\/2815072.2815073"},{"key":"3577_CR11","unstructured":"Prud\u2019hommeaux, E. and Seaborne, A., Eds., SPARQL query language for RDF.\nhttp:\/\/www.w3.org\/TR\/2008\/REC-rdf-sparql-query-20080115."},{"key":"3577_CR12","first-page":"519","volume":"6","author":"A. Okhotin","year":"2001","unstructured":"Okhotin, A., Conjunctive grammars, J. Autom., \n               Lang. Combinatorics, 2001, vol. 6, no. 4, pp. 519\u2013535.","journal-title":"Lang. Combinatorics"},{"key":"3577_CR13","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.ic.2004.03.006","volume":"194","author":"A. Okhotin","year":"2004","unstructured":"Okhotin, A., Boolean grammars, Inf. Comput., 2004, vol. 194, no. 1, pp. 19\u201348.","journal-title":"Inf. Comput."},{"key":"3577_CR14","unstructured":"Hellings, J., Querying for paths in graphs using context-free path queries, 2015."},{"key":"3577_CR15","unstructured":"Hellings, J., Conjunctive context-free path queries, Proc. Int. Conf. Database Theory (ICDT), 2014, pp. 119\u2013130."},{"key":"3577_CR16","doi-asserted-by":"crossref","unstructured":"Sevon, P. and Eronen, L., Subgraph queries by context-free grammars, J. Integr. Bioinf., 2008, vol. 5, no. 2.","DOI":"10.1515\/jib-2008-100"},{"key":"3577_CR17","doi-asserted-by":"crossref","unstructured":"Zhang, X., et al., Context-free path queries on RDF graphs, Proc. Int. Semantic Web Conf., 2016, pp. 632\u2013648.","DOI":"10.1007\/978-3-319-46523-4_38"},{"key":"3577_CR18","doi-asserted-by":"crossref","unstructured":"Grigorev, S. and Ragozina, A., Context-free path querying with structural representation of result, Proc. 13th Cent. East. Eur. Software Engineering Conf. Russia (CEESECR), 2017.","DOI":"10.1145\/3166094.3166104"},{"key":"3577_CR19","doi-asserted-by":"crossref","unstructured":"Azimov, R.Sh. and Grigorev, S.V., Context-free path querying by matrix multiplication, 2017.","DOI":"10.1145\/3210259.3210264"},{"key":"3577_CR20","doi-asserted-by":"publisher","unstructured":"Azimov, R.Sh. and Grigorev, S.V., Path querying using conjunctive grammars, Tr. Inst. Sist. Program. Ross. Akad. Nauk (Proc. Inst. Syst. Program. Russ. Acad. Sci.), 2018, vol. 30, no. 2, pp. 149\u2013166. https:\/\/doi.org\/10.15514\/ISPRAS-2018-30(2)-8","DOI":"10.15514\/ISPRAS-2018-30(2)-8"},{"key":"3577_CR21","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"L.G. Valiant","year":"1975","unstructured":"Valiant, L.G., General context-free recognition in less than cubic time, J. Comput. Syst. Sci., 1975, vol. 10, no.\u00a02, pp. 308\u2013315.","journal-title":"J. Comput. Syst. Sci."},{"key":"3577_CR22","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.tcs.2013.09.011","volume":"516","author":"A. Okhotin","year":"2014","unstructured":"Okhotin, A., Parsing by matrix multiplication generalized to Boolean grammars, Theor. Comput. Sci., 2014, vol. 516, pp. 101\u2013120.","journal-title":"Theor. Comput. Sci."},{"key":"3577_CR23","first-page":"487","volume":"194","author":"V.L. Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., Dinitz, Y.A., Kronrod, M.A., and Faradzhev, I.A., On economical construction of the transitive closure of an oriented graph, Dokl. Akad. Nauk SSSR, 1970, vol. 194, no. 3, pp. 487\u2013488.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"3577_CR24","doi-asserted-by":"crossref","unstructured":"Vassilevska, W.V., Multiplying matrices faster than Coppersmith-Winograd, Proc. 44th Symp. Theory of Computing, (STOC), 2012, pp. 887\u2013898.","DOI":"10.1145\/2213977.2214056"},{"key":"3577_CR25","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E., Depth-first search and linear graph algorithms, Proc. 12th Annu. Symp. Switching and Automata Theory (SWAT), 1971, pp. 114\u2013121.","DOI":"10.1109\/SWAT.1971.10"},{"key":"3577_CR26","doi-asserted-by":"crossref","unstructured":"Koschmieder, A. and Leser, U., Regular path queries on large graphs, Proc. 24th Int. Conf. Scientific and Statistical Database Management (SSDBM), 2012, pp. 177\u2013194.","DOI":"10.1007\/978-3-642-31235-9_12"},{"key":"3577_CR27","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, Theor. Comput. Syst., 2017, vol. 61, no. 1, pp. 31\u201383.","journal-title":"Theor. Comput. Syst."},{"key":"3577_CR28","doi-asserted-by":"publisher","first-page":"2086","DOI":"10.1109\/TKDE.2016.2546243","volume":"28","author":"C. Lu","year":"2016","unstructured":"Lu, C., Yu, J.X., Li, R., and Wei, H., Exploring hierarchies in online social networks, IEEE Trans. Knowledge Data Eng., 2016, vol. 28, no. 8, pp. 2086\u20132100.","journal-title":"IEEE Trans. Knowledge Data Eng."},{"key":"3577_CR29","doi-asserted-by":"crossref","unstructured":"Sridharan, M., Gopan, D., Shan, L., and Bod\u00edk, R., Demand-driven points-to analysis for Java, Proc. 20th Annu. ACM SIGPLAN Conf. Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2005, pp. 59\u201376.","DOI":"10.1145\/1094811.1094817"},{"key":"3577_CR30","volume-title":"History and architecture of a project RescueWare","author":"A.N. Terekhov","year":"2000","unstructured":"Terekhov, A.N., Erlikh, L.A., and Terekhov, A.A., History and architecture of a project RescueWare, Autom. Software Reeng., 2000, pp. 7\u201319."},{"key":"3577_CR31","doi-asserted-by":"crossref","unstructured":"Medeiros, C.M., Musicante, M.A., and Costa, U.S., Efficient evaluation of context-free path queries for graph databases, Proc. 33rd Annu. ACM Symp. Applied Computing (SAC), 2018, pp. 1230\u20131237.","DOI":"10.1145\/3167132.3167265"},{"key":"3577_CR32","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1016\/S0019-9958(70)90446-8","volume":"17","author":"D.J. Rosenkrantz","year":"1970","unstructured":"Rosenkrantz, D.J. and Stearns, R.E., Properties of deterministic top-down grammars, Inf. Control, 1970, vol.\u00a017, no. 3, pp. 226\u2013256.","journal-title":"Inf. Control"}],"container-title":["Programming and Computer Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S036176882008006X.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1134\/S036176882008006X","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S036176882008006X.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T02:41:14Z","timestamp":1775011274000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1134\/S036176882008006X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["3577"],"URL":"https:\/\/doi.org\/10.1134\/s036176882008006x","relation":{},"ISSN":["0361-7688","1608-3261"],"issn-type":[{"value":"0361-7688","type":"print"},{"value":"1608-3261","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]},"assertion":[{"value":"22 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 March 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 April 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}