Nondeterministic \(NC^1\) computation
type: Item
instance of: scholarly article
title: Nondeterministic \(NC^1\) computation
zbMATH Open document ID: 0921.68029
author: Hervé Caussinus
author: Pierre McKenzie
author: Denis Thérien
author: Heribert Vollmer
published in: Journal of Computer and System Sciences
publication date: 1998-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 1240650
zbMATH Keywords: counting classes
MaRDI profile type: Publication
full work available at URL: jcss.1998.1588
OpenAlex ID: W4212838967
cites work: Q4266552
cites work: A Uniform Circuit Lower Bound for the Permanent
cites work: A very hard log-space counting class
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: On uniformity within \(NC^ 1\)
cites work: Finite monoids and the fine structure of NC 1
cites work: Extensions to Barrington's M-program model
cites work: Computing Algebraic Formulas Using a Constant Number of Registers
cites work: On Relating Time and Space to Size and Depth
cites work: A uniform approach to define complexity classes
cites work: Comparing counting classes for logspace, one-way logspace, and first-order
cites work: An Optimal Parallel Algorithm for Formula Evaluation
cites work: Bits and relative order from residues, space efficiently
cites work: Gap-definable counting classes
cites work: Q4942644
cites work: On balanced versus unbalanced computation trees
cites work: Logspace and logtime leaf languages
cites work: Q3691587
cites work: On counting and approximation
cites work: Unambiguity of circuits
cites work: On iterated integer product
cites work: Word Problems Solvable in Logspace
cites work: \(NC^ 1\): The automata-theoretic viewpoint
cites work: On uniform circuit complexity
cites work: The complexity of computing the permanent
cites work: Recursion theoretic characterizations of complexity classes of counting functions
cites work: Some observations on the connection between counting and recursion
DOI: 10.1006/JCSS.1998.1588
description: scientific article; zbMATH DE number 1240650