summaryrefslogtreecommitdiff
path: root/support/w2latex/EXEMPLES/DOleivant-2.rtf
blob: 0b22ac58daceb6a71a88619ceb1899a30b9cc6bc (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
{\rtf1\mac\deff2 {\fonttbl{\f0\fswiss Chicago;}{\f2\froman New York;}{\f3\fswiss Geneva;}{\f4\fmodern Monaco;}{\f6\fdecor London;}{\f8\fdecor San Francisco;}{\f11\fnil Cairo;}{\f12\fnil Los Angeles;}{\f13\fnil Zapf Dingbats;}{\f14\fnil Bookman;}
{\f16\fnil Palatino;}{\f18\fnil Zapf Chancery;}{\f20\froman Times;}{\f21\fswiss Helvetica;}{\f22\fmodern Courier;}{\f23\ftech Symbol;}{\f24\fnil Mobile;}{\f33\fnil Avant Garde;}{\f34\fnil New Century Schlbk;}{\f101\fnil Wartburg;}{\f118\fnil Warwick S;}
{\f128\fnil Moscow;}{\f129\fnil Russian;}{\f135\fnil MATH-BES;}{\f140\fnil Lovell;}{\f149\fnil Detroit;}{\f171\fnil XB Futura ExtraBold;}{\f176\fnil H Futura Heavy;}{\f201\fnil ¡Math;}{\f512\fnil Alexandrie;}{\f2500\fnil Konstanz;}}
{\colortbl\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;\red0\green255\blue0;\red255\green0\blue255;\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;}{\stylesheet{\sbasedon222\snext0 Normal;}}{\info{\title 
DOleivant-2.rtf}{\author Centre International de Rencontres Mathematiques}}\paperw11880\paperh16820\margl1701\margr1701\margt1417\margb1417\deftab709\widowctrl\ftnbj\makebackup \sectd \linemod0\linex0\headery1077\footery1077\cols1\colsx709\endnhere 
\pard\plain \qc\sl360 {\b\f16 Transfer principles between logic-based approaches to computational complexity \par 
}\pard \qc\sl360 {\b\f16 \par 
Daniel Leivant\par 
}\pard \sl360 {\f16 \par 
}\pard \sl360 {\f16 Transfer principles are useful in organizing and unifying the many logic-based approaches to computational complexity. They also suggest new results and elucidate difficulties and anomalies.\par 
}\pard \sl360 {\f16 We consider approaches to computational complexity based on provability in second and first order formalism, on definability in applicative languages, and on finite model theory. We show how conservation is a principle leading
 from second to first order provability, and how variants  in the Schoenfinkel.-Curry-Howard homomorphism lead from the latter to applicative programs. We exhibit a general boundedness principle that leads from predicative provability to bounded arithmet
ic and from predicative recurrence to bounded recurrence \'88 la Cobham and Ritchie.\par 
}\pard \sl360 {\f16 Finally, we show that simple labeling leads from the latter to characterizations in finite model theory.\par 
}\pard \par 
}