A game on partial orderings
✍ Scribed by Sakaé Fuchino; Sabine Koppelberg; Saharon Shelah
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 412 KB
- Volume
- 74
- Category
- Article
- ISSN
- 0166-8641
No coin nor oath required. For personal study only.
✦ Synopsis
We study the determinacy of the game G~(A) introduced in Fuchino, Koppelberg and Shelah (to appear) for uncountable regular n and several classes of partial orderings A. Among trees or Boolean algebras, we can always find an A such that G~(A) is undetermined. For the class of linear orders, the existence of such A depends on the size of ~<'~. In particular we obtain a characterization of ~<'~ = ~ in terms of determinacy of the game G~(L) for linear orders L.
📜 SIMILAR VOLUMES
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