vol 19 no. 4, FCT '15

1. 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 = \emptyset$. In this work, we assume some mild closure properties for $\mathcal{C}$ and study for which such classes separability by a piecewise testable language (PTL) is decidable. We characterize these classes in terms of decidability of (two variants of) an unboundedness problem. From this, we deduce that separability by PTL is decidable for a number of language classes, such as the context-free languages and languages of labeled vector addition systems. Furthermore, it follows that separability by PTL is decidable if and only if one can compute for any language of the class its downward closure wrt. the scattered substring ordering (i.e., if the set of scattered substrings of any […]
Section: special issue FCT'15

2. 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 not O(1)-deepC , that O(1)-deepC sets and order-deepK sets have high or DNR Turing degree and that no K-trival set is O(1)-deepK.
Section: special issue FCT'15

3. 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$ of the word $w$, the longest gapped repeat and palindrome occurring at that position, provided that the length of the gap is subject to various types of restrictions. That is, that for each position $i$ we compute the longest prefix $u$ of $w[i..n]$ such that $uv$ (respectively, $u^Rv$) is a suffix of $w[1..i-1]$ (defining thus a gapped repeat $uvu$ -- respectively, palindrome $u^Rvu$), and the length of $v$ is subject to the aforementioned restrictions.
Section: special issue FCT'15