
arXiv: 1804.02939
Fixed-point logic with rank (FPR) is an extension of fixed-point logic with counting (FPC) with operators for computing the rank of a matrix over a finit field. The expressive power of FPR properly extends that of FPC and is contained in P, but it is not known if that containment is proper. We give a circuit characterization for FPR in terms of families of symmetric circuits with rank gates, along the lines of that for FPC given by Anderson and Dawar in 2017. This requires the development of a broad framework of circuits in which the individual gates compute functions that are not symmetric (i.e., invariant under all permutations of their inputs). This framework also necessitates the development of novel techniques to prove the equivalence of circuits and logic. Both the framework and the techniques are of greater generality than the main result.
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Computational Complexity (cs.CC), 004, Logic in Computer Science (cs.LO), descriptive complexity, Computer Science - Computational Complexity, 4613 Theory Of Computation, finite model theory, F.1.3; F.4.1; F.1.1, 46 Information and Computing Sciences, 4602 Artificial Intelligence, circuit framework, circuits, uniform families of circuits, F.4.1, symmetric circuits, circuit characterization, F.1.3, F.1.1, 4612 Software Engineering, fixed-point logic with rank
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Computational Complexity (cs.CC), 004, Logic in Computer Science (cs.LO), descriptive complexity, Computer Science - Computational Complexity, 4613 Theory Of Computation, finite model theory, F.1.3; F.4.1; F.1.1, 46 Information and Computing Sciences, 4602 Artificial Intelligence, circuit framework, circuits, uniform families of circuits, F.4.1, symmetric circuits, circuit characterization, F.1.3, F.1.1, 4612 Software Engineering, fixed-point logic with rank
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
