Counting modulo finite semigroups

Rudimentary relations are those relations over natural integers that are defined by a first-order arithmetical formula, in which all quantifications are bounded by some variable. Paris and Wilkie conjectured that the class R of rudimentary relations is not closed under modular counting or constant-b...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2001, Vol.257 (1), p.107-114
Main Author: Esbelin, Henri-Alex
Format: Article
Language:English
Subjects:
Algebra
Complexity
Counting relations
Exact sciences and technology
Group theory
Group theory and generalizations
Mathematical logic, foundations, set theory
Mathematics
Number theory
Rudimentary relations
Sciences and techniques of general use
Semigroup
Set theory
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Rudimentary relations are those relations over natural integers that are defined by a first-order arithmetical formula, in which all quantifications are bounded by some variable. Paris and Wilkie conjectured that the class R of rudimentary relations is not closed under modular counting or constant-bounded recursion. A consequence would be the proper containment of R in LINSPACE. It is now known that the closure of R under counting modulo an unsolvable non-abelian finite group, or modulo the semigroup of all binary relations on a finite set, contains ALINTIME. We characterize here the semigroups for which the counting is reducible to modular counting, or contains counting modulo an unsolvable non-abelian finite group.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(00)00112-2