On the quantifier-free dynamic complexity of reachability
type: Item
instance of: scholarly article
title: On the quantifier-free dynamic complexity of reachability
zbMATH Open document ID: 1312.68085
author: Thomas Zeume
author: Thomas Schwentick
published in: Information and Computation
publication date: 2015-01-30T00:00:00Z
Mathematics Subject Classification ID: 68P15
Mathematics Subject Classification ID: 03B70
zbMATH DE Number: 6393283
MaRDI profile type: Publication
full work available at URL: j.ic.2014.09.011
OpenAlex ID: W2093618122
cites work: Incremental recomputation in local languages.
cites work: Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
cites work: SEPARATING AUXILIARY ARITY HIERARCHY OF FIRST-ORDER INCREMENTAL EVALUATION SYSTEMS USING (3K+1)-ary INPUT RELATIONS
cites work: The dynamic complexity of formal languages
cites work: Q3997075
cites work: Q4473274
cites work: The dynamic complexity of transitive closure is in DynTC\(^{0}\).
cites work: Dyn-FO: A parallel, dynamic complexity class
cites work: Lower bounds for dynamic connectivity
cites work: Multiply-Recursive Upper Bounds with Higman’s Lemma
cites work: Dynamic complexity theory revisited
cites work: On the Quantifier-Free Dynamic Complexity of Reachability
cites work: Dynamic conjunctive queries
DOI: 10.1016/J.IC.2014.09.011
description: scientific article