| Autor: |
Harrison-Trainor, Matthew, Melnikov, Alexander, Miller, Russell, Montalbán, Antonio |
| Předmět: |
|
| Zdroj: |
Journal of Symbolic Logic; Mar2017, Vol. 82 Issue 1, p77-97, 21p |
| Abstrakt: |
Our main result is the equivalence of two notions of reducibility between structures. One is a syntactical notion which is an effective version of interpretability as in model theory, and the other one is a computational notion which is a strengthening of the well-known Medvedev reducibility. We extend our result to effective bi-interpretability and also to effective reductions between classes of structures. [ABSTRACT FROM PUBLISHER] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
