Paper Info
Title
Languages Defined With Modular Counting Quantifiers (Extended Abstract)
Abstract
We prove that a regular language defined by a boolean combination of generalized Σ 1 -sentences built from modular counting quantifiers is defined by a booleean combination of generalized Σ 1 -sentences in which only regular numerical predicates appear. We will give the precise definitions of all of these terms shortly. This is a special case of an outstanding conjecture in circuit complexity (that the class ACC is properly contained in NC 1 ) about the power of contant-depth circuits built with modular gates. The techniques used in the present paper may shed some light on the general case.
Year
DOI
Venue
1998
10.1007/BFb0028572
STACS
Keywords
Field
DocType
extended abstract
Programming language,Computer science,Modular design
Conference
Volume
ISSN
ISBN
1373
0302-9743
3-540-64230-7
Citations 
PageRank 
References 
0
0.34
10
Authors
1
Name
Order
Citations
PageRank
Howard Straubing152860.92