Abstract
Which amount of parallel resources is needed for updating a query result after changing an input? In this work we study the amount of work required for dynamically answering membership and range queries for formal languages in parallel constant time with polynomially many processors. As a prerequisite, we propose a framework for specifying dynamic, parallel, constant-time programs that require small amounts of work. This framework is based on the dynamic descriptive complexity framework by Patnaik and Immerman.
A full version of the paper is available at [21], https://arxiv.org/abs/2101.08735
Chapter PDF
Similar content being viewed by others
References
Abboud, A., Backurs, A., Bringmann, K., Künnemann, M.: Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. pp. 192–203. IEEE Computer Society (2017). https://doi.org/10.1109/FOCS.2017.26
Abboud, A., Backurs, A., Williams, V.V.: If the current clique algorithms are optimal, so is Valiant’s parser. SIAM J. Comput. 47(6), 2527–2555 (2018)
Alstrup, S., Husfeldt, T., Rauhe, T.: Dynamic nested brackets. Inf. Comput. 193(2), 75–83 (2004). https://doi.org/10.1016/j.ic.2004.04.006, https://doi.org/10.1016/j.ic.2004.04.006
Börger, E.: Abstract state machines: a unifying view of models of computation and of system design frameworks. Ann. Pure Appl. Log. 133(1-3), 149–171 (2005). https://doi.org/10.1016/j.apal.2004.10.007
Datta, S., Kulkarni, R., Mukherjee, A., Schwentick, T., Zeume, T.: Reachability is in DynFO. J. ACM 65(5), 33:1–33:24 (2018). https://doi.org/10.1145/3212685
Dong, G., Su, J.: First-order incremental evaluation of datalog queries. In: Database Programming Languages (DBPL-4), Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, Manhattan, New York City, USA, 30 August - 1 September 1993. pp. 295–308 (1993)
Dong, G., Topor, R.W.: Incremental evaluation of datalog queries. In: Database Theory - ICDT’92, 4th International Conference, Berlin, Germany, October 14-16, 1992, Proceedings. pp. 282–296 (1992). https://doi.org/10.1007/3-540-56039-4_48
Frandsen, G.S., Husfeldt, T., Miltersen, P.B., Rauhe, T., Skyum, S.: Dynamic algorithms for the Dyck languages. In: Akl, S.G., Dehne, F.K.H.A., Sack,J., Santoro, N. (eds.) Algorithms and Data Structures, 4th International Workshop, WADS ’95, Kingston, Ontario, Canada, August 16-18, 1995, Proceedings. Lecture Notes in Computer Science, vol. 955, pp. 98–108. Springer (1995). https://doi.org/10.1007/3-540-60220-8_54
Frandsen, G.S., Miltersen, P.B., Skyum, S.: Dynamic word problems. J. ACM 44(2), 257–271 (1997). https://doi.org/10.1145/256303.256309
Gall, F.L.: Powers of tensors and fast matrix multiplication. In: International Symposium on Symbolic and Algebraic Computation, ISSAC ’14, Kobe, Japan, July 23-25, 2014. pp. 296–303 (2014)
Gelade, W., Marquardt, M., Schwentick, T.: The dynamic complexity of formal languages. ACM Trans. Comput. Log. 13(3), 19 (2012). https://doi.org/10.1145/2287718.2287719
Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723–760 (2001). https://doi.org/10.1145/502090.502095
Holm, J., Rotenberg, E.: Fully-dynamic planarity testing in polylogarithmic time. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. pp. 167–180. ACM (2020). https://doi.org/10.1145/3357713.3384249
Immerman, N.: Descriptive complexity. Graduate texts in computer science, Springer (1999). https://doi.org/10.1007/978-1-4612-0539-5
Immerman, N.: Descriptive complexity. Springer Science & Business Media (2012)
JáJá, J.: An Introduction to Parallel Algorithms. Addison-Wesley (1992)
Libkin, L.: Elements of Finite Model Theory. Springer (2004). https://doi.org/10.1007/978-3-662-07003-1
McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press (1971)
Miltersen, P.B., Subramanian, S., Vitter, J.S., Tamassia, R.: Complexity models for incremental computation. Theor. Comput. Sci. 130(1), 203–236 (1994). https://doi.org/10.1016/0304-3975(94)90159-7
Patnaik, S., Immerman, N.: Dyn-FO: A parallel, dynamic complexity class. In: PODS. pp. 210–221 (1994)
Schmidt, J., Schwentick, T., Tantau, T., Vortmeier, N., Zeume, T.: Work-sensitive Dynamic Complexity of Formal Languages. CoRR abs/2101.08735 (2021), https://arxiv.org/abs/2101.08735
Schwentick, T., Vortmeier, N., Zeume, T.: Sketches of dynamic complexity. SIGMOD Rec. 49(2), 18–29 (2020). https://doi.org/10.1145/3442322.3442325
Schwentick, T., Zeume, T.: Dynamic Complexity: Recent Updates. SIGLOG News 3(2), 30–52 (2016). https://doi.org/10.1145/2948896.2948899
Sherlekar, D.D., Pawagi, S., Ramakrishnan, I.V.: O(1) parallel time incremental graph algorithms. In: Maheshwari, S.N. (ed.) Foundations of Software Technology and Theoretical Computer Science, Fifth Conference, New Delhi, India, December 16-18, 1985, Proceedings. Lecture Notes in Computer Science, vol. 206, pp. 477–495. Springer (1985). https://doi.org/10.1007/3-540-16042-6_27
Straubing, H.: Finite automata, formal logic, and circuit complexity. Birkhauser Verlag (1994)
Vollmer, H.: Introduction to circuit complexity: a uniform approach. Springer Science & Business Media (2013)
Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: Karloff, H.J., Pitassi, T. (eds.) Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012. pp. 887–898. ACM (2012). https://doi.org/10.1145/2213977.2214056
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2021 The Author(s)
About this paper
Cite this paper
Schmidt, J., Schwentick, T., Tantau, T., Vortmeier, N., Zeume, T. (2021). Work-sensitive Dynamic Complexity of Formal Languages. In: Kiefer, S., Tasson, C. (eds) Foundations of Software Science and Computation Structures. FOSSACS 2021. Lecture Notes in Computer Science(), vol 12650. Springer, Cham. https://doi.org/10.1007/978-3-030-71995-1_25
Download citation
DOI: https://doi.org/10.1007/978-3-030-71995-1_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-71994-4
Online ISBN: 978-3-030-71995-1
eBook Packages: Computer ScienceComputer Science (R0)