special issue FCT'15

This is a special issue for the 20th International Symposium on Fundamentals of Computation Theory, Gdansk, Poland

guest editors Igor Walukiewicz and Adrian Kosowski


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 […]

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$ […]