Wojciech Czerwiński ; Wim Martens ; Lorijn van Rooijen ; Marc Zeitoun ; Georg Zetzsche.
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 language of the class is effectively regular).
The obtained decidability results contrast some undecidability results. In
fact, for all (non-regular) language classes that we present as examples with
decidable separability, it is undecidable whether a given language is a PTL
itself.
Our characterization involves a result of independent interest, which states
that for any kind of languages $I$ and $E$, non-separability by PTL is
equivalent to the existence of common patterns in $I$ and $E$.
Section:
special issue FCT'15
Philippe Moser ; Frank Stephan.
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
Marin Bougeret ; Guillerme Duvillié ; Rodolphe Giroudeau ; Rémi Watrigant.
In this article we focus on the parameterized complexity of the
Multidimensional Binary Vector Assignment problem (called \BVA). An input of
this problem is defined by $m$ disjoint sets $V^1, V^2, \dots, V^m$, each
composed 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 vector
from each set $V^i$. To each $m$-tuple we associate a $p$ dimensional vector by
applying the bit-wise AND operation on the $m$ vectors of the tuple. The
objective is to minimize the total number of zeros in these $n$ vectors. mBVA
can be seen as a variant of multidimensional matching where hyperedges are
implicitly locally encoded via labels attached to vertices, but was originally
introduced in the context of integrated circuit manufacturing.
We provide for this problem FPT algorithms and negative results ($ETH$-based
results, $W$[2]-hardness and a kernel lower bound) according to several
parameters: the standard parameter $k$ i.e. the total number of zeros), as well
as two parameters above some guaranteed values.
Section:
special issue FCT'15
Marius Dumitran ; Paweł Gawrychowski ; Florin Manea.
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