✦ LIBER ✦

A note on first-order projections and games

✍ Scribed by Argimiro A. Arratia; Iain A. Stewart

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 114 KB
Volume: 290
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(02)00491-7

No coin nor oath required. For personal study only.

✦ Synopsis

We show how the fact that there is a ÿrst-order projection from the problem transitive closure (TC) to some other problem enables us to automatically deduce that a natural game problem, LG( ), whose instances are labelled instances of , is complete for PSPACE (via log-space reductions). Our analysis is strongly dependent upon the reduction from TC to being a logical projection in that it fails should the reduction be, for example, a log-space reduction or a quantiÿer-free ÿrst-order translation.

📜 SIMILAR VOLUMES

A Note on Metric Projections

✍ F. Mazzone; H. Cuenya 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 147 KB

In this note we give an example of a strictly convex, reflexive, smooth Banach space which has a Chebyshev subspace \(M\), such that the projection onto \(M\) is linear and has norm equal to 2 . Moreover, we give necessary and sufficient conditions on a space so that every projection has norm less t

A note on groups with projections

✍ Richard Steiner 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 140 KB

A note on k-generalized projections

✍ Leila Lebtahi; Néstor Thome 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 97 KB

A Note on Cut Elimination and Completene

A Note on Cut Elimination and Completeness in First Order Theories

✍ Kenneth A. Bowen 📂 Article 📅 1972 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 1 views

A note on Steiner tree games

✍ Darko Skorin-Kapov; Jadranka Skorin-Kapov 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

A Note on the Compactness Theorem in Fir

A Note on the Compactness Theorem in First Order Logic

✍ George Weaver 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 223 KB 👁 1 views