The invariant problem for binary string structures and the parallel complexity theory of queries
type: Item
instance of: scholarly article
title: The invariant problem for binary string structures and the parallel complexity theory of queries
zbMATH Open document ID: 0766.68043
DOI: 10.1016/0022-0000(92)90010-G
author: Steven Lindell
published in: Journal of Computer and System Sciences
publication date: 1992-09-27T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P15
zbMATH DE Number: 58908
zbMATH Keywords: structure and complexity of database queries
zbMATH Keywords: parallel complexity theory of queries
zbMATH Keywords: constant parallel time reducibility
MaRDI profile type: Publication
cites work: On uniformity within \(NC^ 1\)
cites work: Structure and complexity of relational queries
cites work: Constant Depth Reducibility
cites work: Definability by constant-depth polynomial-size circuits
cites work: An application of games to the completeness problem for formalized theories
cites work: Q4058132
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Q4198056
cites work: Q5592246
cites work: Expressibility and Parallel Complexity
cites work: Q3830533
cites work: Relational queries computable in polynomial time
cites work: Languages that Capture Complexity Classes
cites work: Nondeterministic Space is Closed under Complementation
cites work: The complexity of iterated multiplication
cites work: Q3865476
cites work: The graph isomorphism disease
cites work: The polynomial-time hierarchy
cites work: Simulation of Parallel Random Access Machines by Circuits
Recommended article: Q2963897
Recommended article: On the parameterised complexity of string morphism problems
Recommended article: On the Kernelization Complexity of String Problems
Recommended article: On the kernelization complexity of string problems
Recommended article: Q4736845
Recommended article: Computational and Proof Complexity of Partial String Avoidability
Recommended article: Q4608614
Recommended article: Q4234122
Recommended article: Q4258669
Recommended article: Bit-parallel witnesses and their applications to approximate string matching
description: scientific article; zbMATH DE number 58908