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

A Characterization for Decidable Separability by Piecewise Testable Languages

Czerwiński, Wojciech ; Martens, Wim ; van Rooijen, Lorijn ; Zeitoun, Marc ; Zetzsche, Georg.
The separability problem for word languages of a class $\mathcal{C}$ by languages of a class $\mathcal{S}$ asks, for two given languages $I$ and $E$ from $\mathcal{C}$, whether there exists a language $S$ from $\mathcal{S}$ that includes $I$ and excludes $E$, that is, $I \subseteq S$ and $S\cap E […]

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