vol 19 no. 4, FCT '15

1. Depth, Highness and DNR degrees

Moser, Philippe ; Stephan, Frank.
We study Bennett deep sequences in the context of recursion theory; in particular we investigate the notions of O(1)-deepK, O(1)-deepC , order-deep K and order-deep C sequences. Our main results are that Martin-Loef random sets are not order-deepC , that every many-one degree contains a set which is […]
Section: special issue FCT'15

2. Longest Gapped Repeats and Palindromes

Dumitran, Marius ; Gawrychowski, Paweł ; Manea, Florin.
A gapped repeat (respectively, palindrome) occurring in a word $w$ is a factor $uvu$ (respectively, $u^Rvu$) of $w$. In such a repeat (palindrome) $u$ is called the arm of the repeat (respectively, palindrome), while $v$ is called the gap. We show how to compute efficiently, for every position $i$ […]
Section: special issue FCT'15