A note on degrees of presentation of games as relational structures (Q912772): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lower bounds on degrees of game-theoretic structures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Degrees of Structures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5573961 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Polynomial Time Enumeration Reducibility / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Reductions on NP and p-selective sets / rank | |||
Normal rank |
Latest revision as of 15:34, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on degrees of presentation of games as relational structures |
scientific article |
Statements
A note on degrees of presentation of games as relational structures (English)
0 references
1990
0 references
This paper considers concepts of recursion-theoretic complexity in terms of the structure of Turing degrees of unsolvability for abstract games of the form \(\Gamma =<A,\prec >\), where A is a space of outcomes for a von Neumann cooperative game with arbitrary cardinality of players, and \(\succ\) is a dominance relation defined on pairs of outcomes in the space A. Weak versus strong concepts of recursive presentation are defined using the R.E. degrees and it is proved that no structure of the form \(\Gamma =<A,\prec >\) which is isomorphic to the space of primitive recursive reals when the dominance relation defined by the ordering on the positive part of A can be recursively presented in the strong sense, despite the fact that the dominance relation in this case is recursive. The notion of weak presentation coincides with R.E. presented, and in the special case when the dominance relation is extended to a linear ordering we show that a countable abstract game \(\Gamma =<A,\prec >\) possesses a degree of its isomorphic class only if that degree is \(\underset \tilde{} O\) and thus the game \(\Gamma =<A,\prec >\) is isomorphic to some game \(\Gamma_ 0=<A,\prec_ 0>\) whose degree of presentation is strongly recursive.
0 references
relational structures
0 references
recursion-theoretic complexity
0 references
Turing degrees of unsolvability
0 references
abstract games
0 references