The invariant problem for binary string structures and the parallel complexity theory of queries
- 1 June 1992
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 44 (3) , 385-410
- https://doi.org/10.1016/0022-0000(92)90010-g
Abstract
No abstract availableKeywords
This publication has 14 references indexed in Scilit:
- The complexity of iterated multiplicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Expressibility and Parallel ComplexitySIAM Journal on Computing, 1989
- Nondeterministic Space is Closed under ComplementationSIAM Journal on Computing, 1988
- Languages that Capture Complexity ClassesSIAM Journal on Computing, 1987
- Definability by constant-depth polynomial-size circuitsInformation and Control, 1986
- Relational queries computable in polynomial timeInformation and Control, 1986
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- Constant Depth ReducibilitySIAM Journal on Computing, 1984
- Structure and complexity of relational queriesJournal of Computer and System Sciences, 1982
- An application of games to the completeness problem for formalized theoriesFundamenta Mathematicae, 1960