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


Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations

Marin Bougeret ; Guillerme Duvillié ; Rodolphe Giroudeau ; Rémi Watrigant.
In this article we focus on the parameterized complexity of theMultidimensional Binary Vector Assignment problem (called \BVA). An input ofthis problem is defined by $m$ disjoint sets $V^1, V^2, \dots, V^m$, eachcomposed of $n$ binary vectors of size $p$. An output is a set of $n$ disjoint$m$-tuples of vectors, where each $m$-tuple is obtained by picking one vectorfrom each set $V^i$. To each $m$-tuple we associate a $p$ dimensional vector byapplying the bit-wise AND operation on the $m$ vectors of the tuple. Theobjective is to minimize the total number of zeros in these $n$ vectors. mBVAcan be seen as a variant of multidimensional matching where hyperedges areimplicitly locally encoded via labels attached to vertices, but was originallyintroduced in the context of integrated circuit manufacturing. We provide for this problem FPT algorithms and negative results ($ETH$-basedresults, $W$[2]-hardness and a kernel lower bound) according to severalparameters: the standard parameter $k$ i.e. the total number of zeros), as wellas two parameters above some guaranteed values.

A Characterization for Decidable Separability by Piecewise Testable Languages

Wojciech Czerwiński ; Wim Martens ; Lorijn van Rooijen ; Marc Zeitoun ; Georg Zetzsche.
The separability problem for word languages of a class $\mathcal{C}$ bylanguages 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}$ thatincludes $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 piecewisetestable language (PTL) is decidable. We characterize these classes in terms ofdecidability of (two variants of) an unboundedness problem. From this, wededuce that separability by PTL is decidable for a number of language classes,such as the context-free languages and languages of labeled vector additionsystems. Furthermore, it follows that separability by PTL is decidable if andonly 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 ofany language of the class is effectively regular). The obtained decidability results contrast some undecidability results. Infact, for all (non-regular) language classes that we present as examples withdecidable separability, it is undecidable whether a given language is a PTLitself. Our characterization involves a result of independent interest, which statesthat for any kind of languages $I$ and $E$, non-separability by PTL isequivalent to the existence of common patterns in $I$ and $E$.

Depth, Highness and DNR degrees

Philippe Moser ; Frank Stephan.
We study Bennett deep sequences in the context of recursion theory; inparticular we investigate the notions of O(1)-deepK, O(1)-deepC , order-deep Kand order-deep C sequences. Our main results are that Martin-Loef random setsare not order-deepC , that every many-one degree contains a set which is notO(1)-deepC , that O(1)-deepC sets and order-deepK sets have high or DNR Turingdegree and that no K-trival set is O(1)-deepK.

Longest Gapped Repeats and Palindromes

Marius Dumitran ; Paweł Gawrychowski ; Florin Manea.
A gapped repeat (respectively, palindrome) occurring in a word $w$ is afactor $uvu$ (respectively, $u^Rvu$) of $w$. In such a repeat (palindrome) $u$is called the arm of the repeat (respectively, palindrome), while $v$ is calledthe 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 ofrestrictions. 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.