|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Upper semi-lattice of binary strings with the relation "x is simple conditional to y"статья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 31 октября 2014 г.
- Авторы: Chernov A., Muchnik An, Romashchenko A., Shen A., Vereshchagin N.
- Журнал: Theoretical Computer Science
- Том: 271
- Год издания: 2002
- Издательство: Elsevier BV
- Местоположение издательства: Netherlands
- Первая страница: 69
- Последняя страница: 95
- DOI: 10.1016/S0304-3975(01)00032-9
- Аннотация: In this paper we construct a structure R that is a “finite version” of the semi-lattice of Turing degrees. Its elements are strings (technically, sequences of strings) and x⩽y means that relative to y) is small. We construct two elements in R that do not have greatest lower bound. We give a series of examples that show how natural algebraic constructions give two elements that have lower bound 0 (minimal element) but significant mutual information. (A first example of that kind was constructed by Gács–Körner (Problems Control Inform. Theory 2 (1973) 149) using a completely different technique.) We define a notion of “complexity profile” of the pair of elements of R and give (exact) upper and lower bounds for it in a particular case.
- Добавил в систему: Верещагин Николай Константинович