On uniformity within \(NC^ 1\)

DOI10.1016/0022-0000(90)90022-DzbMath0719.68023OpenAlexW2045583484MaRDI QIDQ2640342

Howard Straubing, David A. Mix Barrington, Neil Immerman

Publication date: 1990

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(90)90022-d

zbMATH Keywords

regular languages uniform complexity low-level circuit complexity classes

Mathematics Subject Classification ID

Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).

Related Items (only showing first 100 items - show all)

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ On the complexity of inducing categorical and quantitative association rules ⋮ Arithmetical definability and computational complexity ⋮ The equivalence of theories that characterize ALogTime ⋮ Generating some classes of recursive functions by superpositions of simple arithmetic functions ⋮ On the language of primitive words ⋮ A logical characterization of constant-depth circuits over the reals ⋮ The Complexity of Counting Quantifiers on Equality Languages ⋮ Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\) ⋮ Iterated multiplication in \(VTC^0\) ⋮ Maintenance goals of agents in a dynamic environment: formulation and policy construction ⋮ Some results on uniform arithmetic circuit complexity ⋮ Expressing uniformity via oracles ⋮ Counting quantifiers, successor relations, and logarithmic space ⋮ The complexity of intersecting finite automata having few final states ⋮ The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\) ⋮ A query language for NC ⋮ The complexity of the evaluation of complex algebra expressions ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ Descriptive complexity of deterministic polylogarithmic time and space ⋮ Linear circuits, two-variable logic and weakly blocked monoids ⋮ Gap-languages and log-time complexity classes ⋮ Some lower bounds in parameterized \(\mathrm{AC}^{0}\) ⋮ Extensions of MSO and the monadic counting hierarchy ⋮ The isomorphism conjecture for constant depth reductions ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Indistinguishability and First-Order Logic ⋮ A Characterization of NC k by First Order Functional Programs ⋮ Expressive power of SQL. ⋮ The dynamic complexity of transitive closure is in DynTC\(^{0}\). ⋮ Model-checking hierarchical structures ⋮ Completeness results for graph isomorphism. ⋮ Adaptive logspace reducibility and parallel time ⋮ On Second-Order Monadic Groupoidal Quantifiers ⋮ A second-order system for polytime reasoning based on Grädel's theorem. ⋮ On the locality of arb-invariant first-order formulas with modulo counting quantifiers ⋮ Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\) ⋮ A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups ⋮ Descriptive complexity of \#P functions: a new perspective ⋮ Dynamic Complexity of the Dyck Reachability ⋮ Extensional Uniformity for Boolean Circuits ⋮ A Characterisation of NL Using Membrane Systems without Charges and Dissolution ⋮ A characterization of definability of second-order generalized quantifiers with applications to non-definability ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ On uniformity and circuit lower bounds ⋮ Rudimentary reductions revisited ⋮ The expressiveness of a family of finite set languages ⋮ On adaptive DLOGTIME and POLYLOGTIME reductions ⋮ Computing with infinitary logic ⋮ On input read-modes of alternating Turing machines ⋮ Bounding the space in P systems with active membranes ⋮ The graph of multiplication is equivalent to counting ⋮ The invariant problem for binary string structures and the parallel complexity theory of queries ⋮ Regular languages in \(NC\) ⋮ Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages ⋮ The complexity of counting quantifiers on equality languages ⋮ Methods for proving completeness via logical reductions ⋮ \(NC^ 1\): The automata-theoretic viewpoint ⋮ Root finding with threshold circuits ⋮ Deciding bisimilarity is P-complete ⋮ An optimal lower bound on the number of variables for graph identification ⋮ Number of variables is equivalent to space ⋮ The computational power of membrane systems under tight uniformity conditions ⋮ Extensions to Barrington's M-program model ⋮ Division in logspace-uniformNC¹ ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ First-order expressibility of languages with neutral letters or: The Crane Beach conjecture ⋮ A model-theoretic characterization of constant-depth arithmetic circuits ⋮ First-order logics: some characterizations and closure properties ⋮ Reductions to graph isomorphism ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG] ⋮ Theories of arithmetics in finite models ⋮ The exact complexity of projective image matching ⋮ On the complexity of the clone membership problem ⋮ A Language-Theoretical Approach to Descriptive Complexity ⋮ A constant-space sequential model of computation for first-order logic ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Expressive Completeness for LTL With Modulo Counting and Group Quantifiers ⋮ The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\) ⋮ Relating polynomial time to constant depth ⋮ The complexity of the comparator circuit value problem ⋮ Reductions in circuit complexity: An isomorphism theorem and a gap theorem ⋮ Nondeterministic \(NC^1\) computation ⋮ On the power of built-in relations in certain classes of program schemes ⋮ Circuits and expressions with nonassociative gates ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ The complexity of solitaire ⋮ Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\) ⋮ Lower bounds for invariant queries in logics with counting. ⋮ Counting modulo quantifiers on finite structures ⋮ On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology ⋮ Context-sensitive transitive closure operators ⋮ The parallel complexity of two problems on concurrency ⋮ The complexity of computing maximal word functions ⋮ Multi-head finite automata: Data-independent versus data-dependent computations ⋮ Dynamic complexity of expansion ⋮ Relativizing small complexity classes and their theories

Cites Work

This page was built for publication: On uniformity within \(NC^ 1\)