- journal article metadata
European Mathematical Society Publishing House
2016-09-19 17:05:23
Portugaliae Mathematica
Port. Math.
PM
0032-5155
1662-2758
General
10.4171/PM
http://www.ems-ph.org/doi/10.4171/PM
subscribers
European Mathematical Society Publishing House
Zuerich, Switzerland
© European Mathematical Society (from 2008)
66
2009
1
The counting hierarchy in binary notation
Gilda
Ferreira
Universidade Lusófona de Humanidades e Tecnologias, LISBOA, PORTUGAL
Counting hierarchy, bounded arithmetic, complexity theory
We present a new recursion-theoretic characterization of FCH, the hierarchy of counting functions, in binary notation. Afterwards we introduce a theory of bounded arithmetic, TCA, that can be seen as a reformulation, in the binary setting, of Jan Johannsen and Chris Pollett's system D02. Using the previous inductive characterization of FCH, we show that a strategy similar to the one applied to D02 can be used in order to characterize FCH as the class of functions provably total in TCA.
Computer science
Mathematical logic and foundations
General
81
94
10.4171/PM/1832
http://www.ems-ph.org/doi/10.4171/PM/1832