Name
Abstract | ||
|---|---|---|
We consider an extension of first-order logic by modular quantifiers of a fixed modulus q. Drawing on collapse results from finite model theory and techniques of finite semigroup theory, we show that if the only available numerical predicate is addition, then sentences in this logic cannot define the set of bit strings in which the number of 1's is divisible by a prime p that does not divide q. More generally, we completely characterize the regular languages definable in this logic. The corresponding statement, with addition replaced by arbitrary numerical predicates, is equivalent to the conjectured separation of the circuit complexity class ACC from NC1. Thus our theorem can be viewed as proving a highly uniform version of the conjecture. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11672142_40 | SIAM J. Comput. |
Keywords | Field | DocType |
available numerical predicate,circuit complexity class acc,collapse result,bit string,generalized first-order formula,fixed modulus q,arbitrary numerical predicate,conjectured separation,finite semigroup theory,first-order logic,finite model theory,regular language,first order logic,first order,circuit complexity,model theory | Prime (order theory),Complexity class,Discrete mathematics,Combinatorics,Predicate variable,Finite model theory,First-order logic,Regular language,Semigroup,Conjecture,Mathematics | Conference |
Volume | Issue | ISSN |
37 | 2 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-32301-5 | 5 | 0.44 |
References | Authors | |
15 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amitabha Roy | 1 | 5 | 0.44 |
| Howard Straubing | 2 | 528 | 60.92 |