Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
type: Item
instance of: scholarly article
title: Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
zbMATH Open document ID: 0936.68029
author: Guozhu Dong
author: Jianwen Su
published in: Journal of Computer and System Sciences
publication date: 1999-02-21T00:00:00Z
Mathematics Subject Classification ID: 68P15
zbMATH DE Number: 1252381
MaRDI profile type: Publication
OpenAlex ID: W1980634162
cites work: Reachability is harder for directed than for undirected finite graphs
cites work: Q4864249
cites work: Determining uni-connectivity in directed graphs
cites work: Lower bounds for constant-depth circuits in the presence of help bits
cites work: Structure and complexity of relational queries
cites work: Maintaining transitive closure in first order after node-set and edge-set deletions
cites work: Incremental and decremental evaluation of transitive closure by first- order queries
cites work: Deterministic FOIES are strictly weaker
cites work: Nonrecursive incremental evaluation of Datalog queries
cites work: An application of games to the completeness problem for formalized theories
cites work: Monadic generalized spectra
cites work: On monadic NP vs monadic co-NP
cites work: Finitely representable databases
cites work: Relative Information Capacity of Simple Relational Database Schemata
cites work: Complexity models for incremental computation
DOI: 10.1006/JCSS.1998.1565
description: scientific article; zbMATH DE number 1252381