{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:51:13Z","timestamp":1756000273849,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2018,8,29]],"date-time":"2018-08-29T00:00:00Z","timestamp":1535500800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100007296","name":"Infosys Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007296","id-type":"DOI","asserted-by":"crossref"}]},{"name":"DFG","award":["SCHW 678\/6-1 and SCHW 678\/6-2"],"award-info":[{"award-number":["SCHW 678\/6-1 and SCHW 678\/6-2"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"<jats:p>Patnaik and Immerman introduced the dynamic complexity class DynFO of database queries that can be maintained by first-order dynamic programs with the help of auxiliary relations under insertions and deletions of edges. This article confirms their conjecture that the reachability query is in DynFO.<\/jats:p>\n          <jats:p>As a byproduct, it is shown that the rank of a matrix with small values can be maintained in DynFO. It is further shown that the (size of the) maximum matching of a graph can be maintained in non-uniform DynFO, an extension of DynFO, with non-uniform initialisation of the auxiliary relations.<\/jats:p>","DOI":"10.1145\/3212685","type":"journal-article","created":{"date-parts":[[2018,8,30]],"date-time":"2018-08-30T13:45:11Z","timestamp":1535636711000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Reachability Is in DynFO"],"prefix":"10.1145","volume":"65","author":[{"given":"Samir","family":"Datta","sequence":"first","affiliation":[{"name":"Chennai Mathematical Institute 8 UMI ReLaX, Siruseri, Kelambakkam, India"}]},{"given":"Raghav","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, Siruseri, Kelambakkam, India"}]},{"given":"Anish","family":"Mukherjee","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, Siruseri, Kelambakkam, India"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Dortmund, Germany"}]},{"given":"Thomas","family":"Zeume","sequence":"additional","affiliation":[{"name":"TU Dortmund University, Dortmund, Germany"}]}],"member":"320","published-online":{"date-parts":[[2018,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1627"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187922"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465216"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_30"},{"key":"e_1_2_1_7_1","first-page":"46","article-title":"Maintaining transitive closure of graphs in SQL","volume":"51","author":"Dong Guozhu","year":"1999","unstructured":"Guozhu Dong , Leonid Libkin , Jianwen Su , and Limsoon Wong . 1999 . Maintaining transitive closure of graphs in SQL . Int. J. Inform. Technol. 51 , 1 (1999), 46 . Guozhu Dong, Leonid Libkin, Jianwen Su, and Limsoon Wong. 1999. Maintaining transitive closure of graphs in SQL. Int. J. Inform. Technol. 51, 1 (1999), 46.","journal-title":"Int. J. Inform. Technol."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00017-8"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 4th International Workshop on Database Programming Languages (DBPL\u201993)","author":"Dong Guozhu","year":"1993","unstructured":"Guozhu Dong and Jianwen Su . 1993 . First-order incremental evaluation of datalog queries . In Proceedings of the 4th International Workshop on Database Programming Languages (DBPL\u201993) 1993. 295--308. Guozhu Dong and Jianwen Su. 1993. First-order incremental evaluation of datalog queries. In Proceedings of the 4th International Workshop on Database Programming Languages (DBPL\u201993) 1993. 295--308."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018951521198"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1565"},{"volume-title":"Proceedings of the 4th International Conference on Database Theory (ICDT\u201992)","author":"Dong Guozhu","key":"e_1_2_1_12_1","unstructured":"Guozhu Dong and Rodney W. Topor . 1992. Incremental evaluation of datalog queries . In Proceedings of the 4th International Conference on Database Theory (ICDT\u201992) . 282--296. Guozhu Dong and Rodney W. Topor. 1992. Incremental evaluation of datalog queries. In Proceedings of the 4th International Conference on Database Theory (ICDT\u201992). 282--296."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275514"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.012"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2287718.2287719"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274601"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00740-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/645683.664594"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.21"},{"key":"e_1_2_1_21_1","volume-title":"Johnson","author":"Horn Roger A.","year":"2012","unstructured":"Roger A. Horn and Charles R . Johnson . 2012 . Matrix Analysis. Cambridge University Press . Roger A. Horn and Charles R. Johnson. 2012. Matrix Analysis. Cambridge University Press."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Neil Immerman. 1999. Descriptive Complexity. Springer. I--XVI 1--268 pages.  Neil Immerman. 1999. Descriptive Complexity. Springer. I--XVI 1--268 pages.","DOI":"10.1007\/978-1-4612-0539-5_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Stasys Jukna. 2001. Extremal Combinatorics Vol. 2. Springer.  Stasys Jukna. 2001. Extremal Combinatorics Vol. 2. Springer.","DOI":"10.1007\/978-3-662-04650-0"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45220-1_23"},{"volume-title":"Fast Parallel Algorithms for Graph Matching Problems","author":"Karpinski Marek","key":"e_1_2_1_25_1","unstructured":"Marek Karpinski and Wojciech Rytter . 1998. Fast Parallel Algorithms for Graph Matching Problems . Oxford University Press, Inc. , New York . Marek Karpinski and Wojciech Rytter. 1998. Fast Parallel Algorithms for Graph Matching Problems. Oxford University Press, Inc., New York."},{"key":"e_1_2_1_27_1","series-title":"An Eatcs Series","volume-title":"Texts in Theoretical Computer Science","author":"Libkin Leonid","unstructured":"Leonid Libkin . 2004. Elements Of Finite Model Theory , Texts in Theoretical Computer Science . An Eatcs Series . Springer-Verlag . Leonid Libkin. 2004. Elements Of Finite Model Theory, Texts in Theoretical Computer Science. An Eatcs Series. Springer-Verlag."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494529"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the International Symposium of Fundamentals of Computation Theory (FCT)","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1979","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 1979 . On determinants, matchings, and random algorithms . In Proceedings of the International Symposium of Fundamentals of Computation Theory (FCT) 1979. 565--574. L\u00e1szl\u00f3 Lov\u00e1sz. 1979. On determinants, matchings, and random algorithms. In Proceedings of the International Symposium of Fundamentals of Computation Theory (FCT) 1979. 565--574."},{"key":"e_1_2_1_30_1","volume-title":"Matching Theory","volume":"29","author":"Lov\u00e1sz L.","unstructured":"L. Lov\u00e1sz and M. D. Plummer . 1986 . Matching Theory , Vol. 29 . North-Holland Publishing Co. L. Lov\u00e1sz and M. D. Plummer. 1986. Matching Theory, Vol. 29. North-Holland Publishing Co."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979122370X"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/343374"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 19th International Conference on Database Theory (ICDT\u201916)","author":"Mu\u00f1oz Pablo","year":"2016","unstructured":"Pablo Mu\u00f1oz , Nils Vortmeier , and Thomas Zeume . 2016 . Dynamic graph queries . In Proceedings of the 19th International Conference on Database Theory (ICDT\u201916) . 14:1--14:18. Pablo Mu\u00f1oz, Nils Vortmeier, and Thomas Zeume. 2016. Dynamic graph queries. In Proceedings of the 19th International Conference on Database Theory (ICDT\u201916). 14:1--14:18."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182614"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1520"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90005-9"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798339041"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1255631807"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.25"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Sankowski Piotr","year":"2007","unstructured":"Piotr Sankowski . 2007 . Faster dynamic matchings and vertex connectivity . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907) 2007. 118--126. http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283397. Piotr Sankowski. 2007. Faster dynamic matchings and vertex connectivity. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907) 2007. 118--126. http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283397."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2948896.2948899"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1312-0"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2206869.2206879"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.011"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3212685","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3212685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:54:16Z","timestamp":1750287256000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3212685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,29]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3212685"],"URL":"https:\/\/doi.org\/10.1145\/3212685","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2018,8,29]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}