ECCC-Report TR03-024https://eccc.weizmann.ac.il/report/2003/024Comments and Revisions published for TR03-024en-usTue, 15 Apr 2003 19:13:58 +0300
Paper TR03-024
| Weak Cardinality Theorems for First-Order Logic |
Till Tantau
https://eccc.weizmann.ac.il/report/2003/024Kummer's cardinality theorem states that a language is recursive
if a Turing machine can exclude for any n words one of the
n + 1 possibilities for the number of words in the language. It
is known that this theorem does not hold for polynomial-time
computations, but there is evidence that it holds for finite
automata: at least weak cardinality theorems hold for finite
automata. This paper shows that some of the recursion-theoretic
and automata-theoretic weak cardinality theorems are
instantiations of purely logical theorems. Apart from unifying
previous results in a single framework, the logical approach
allows us to prove new theorems for other computational models.
For example, weak cardinality theorems hold for Presburger
arithmetic.
Tue, 15 Apr 2003 19:13:58 +0300https://eccc.weizmann.ac.il/report/2003/024