Work-sensitive dynamic complexity of formal languages

DOI10.1007/978-3-030-71995-1_25OpenAlexW3142840804MaRDI QIDQ2233429FDOQ2233429

Authors: Thomas Schwentick, Till Tantau, Nils Vortmeier, Thomas Zeume, Jonas Schmidt 

Publication date: 18 October 2021

Full work available at URL: https://arxiv.org/abs/2101.08735

zbMATH Keywords

workdynamic complexityparallel constant time

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites Work

• Powers of tensors and fast matrix multiplication
• Title not available (Why is that?)
• Multiplying matrices faster than coppersmith-winograd
• Elements of finite model theory.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Complexity models for incremental computation
• Abstract state machines: a unifying view of models of computation and of system design frameworks
• If the current clique algorithms are optimal, so is Valiant's parser
• Dynamic word problems
• Dyn-FO: A parallel, dynamic complexity class
• Dynamic nested brackets
• Dynamic algorithms for the Dyck languages
• Fully-dynamic planarity testing in polylogarithmic time
• Dynamic Complexity under Definable Changes
• Reachability is in DynFO
• Work-sensitive dynamic complexity of formal languages
• Experimental descriptive complexity
• The dynamic complexity of formal languages
• Title not available (Why is that?)

Cited In (1)

• Work-sensitive dynamic complexity of formal languages

This page was built for publication: Work-sensitive dynamic complexity of formal languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2233429)