Work-sensitive dynamic complexity of formal languages
From MaRDI portal
Publication:2233429
DOI10.1007/978-3-030-71995-1_25OpenAlexW3142840804MaRDI QIDQ2233429
Thomas Schwentick, Nils Vortmeier, Till Tantau, Thomas Zeume, Jonas Schmidt
Publication date: 18 October 2021
Full work available at URL: https://arxiv.org/abs/2101.08735
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Elements of finite model theory.
- Complexity models for incremental computation
- Dyn-FO: A parallel, dynamic complexity class
- Abstract state machines: a unifying view of models of computation and of system design frameworks
- Dynamic nested brackets
- Work-sensitive dynamic complexity of formal languages
- Experimental Descriptive Complexity
- The dynamic complexity of formal languages
- Dynamic Complexity under Definable Changes
- Powers of tensors and fast matrix multiplication
- Dynamic word problems
- If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
- Reachability Is in DynFO
- Dynamic algorithms for the Dyck languages
- Fully-dynamic planarity testing in polylogarithmic time
- Multiplying matrices faster than coppersmith-winograd
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
This page was built for publication: Work-sensitive dynamic complexity of formal languages
