Paper Info
Title
Circuit Complexity and the Expressive Power of Generalized First-Order Formulas
Abstract
. The circuit complexity classes AC0; ACC; and CC (also calledpure-ACC) can be characterized as the classes of languages definable incertain extensions of first-order logic. All of the known and conjecturedinclusions among these classes have been shown to be equivalent to a singleconjecture concerning the form of the formulas required to define the regularlanguages they contain. (The conjecture states, roughly, that when a formuladefines a regular language, predicates representing...
Year
DOI
Venue
1992
10.1007/3-540-55719-9_60
ICALP
Keywords
Field
DocType
expressive power,generalized first-order formulas,circuit complexity,first order,first order logic,regular language
Discrete mathematics,Combinatorics,Circuit complexity,Unary operation,Finite-state machine,Predicate (grammar),Regular language,Conjecture,Expressive power,Mathematics,Special case
Conference
ISBN
Citations 
PageRank 
3-540-55719-9
4
0.43
References 
Authors
9
1
Name
Order
Citations
PageRank
Howard Straubing152860.92