# Extremal Separation Problems for Temporal Instance Queries

Jean Christoph Jung1 Vladislav Ryzhikov2 Frank Wolter3&Michael Zakharyaschev2
1Department of Computer Science, TU Dortmund University, Germany
2School of Computing and Mathematical Sciences, Birkbeck, University of
London, UK
3Department of Computer Science, University of Liverpool, UK
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The separation problem for a class $\mathcal{Q}$ of database queries is to
find a query in $\mathcal{Q}$ that distinguishes between a given set of
‘positive’ and ‘negative’ data examples. Separation provides explanations of
examples and underpins the query-by-example paradigm to support database users
in constructing and refining queries. As the space of all separating queries
can be large, it is helpful to succinctly represent this space by means of its
most specific (logically strongest) and general (weakest) members. We
investigate this extremal separation problem for classes of instance queries
formulated in linear temporal logic LTL with the operators conjunction,
‘next’, and ‘eventually’. Our results range from tight complexity bounds for
verifying and counting extremal separators to algorithms computing them.

##  1 Introduction

The separation (aka fitting or consistency) problem for a class $\mathcal{Q}$
of queries is to find some $\boldsymbol{q}\in\mathcal{Q}$ that separates a
given set $E=(E^{+},E^{-})$ of positive and negative data examples in the
sense that $\mathcal{D}\models\boldsymbol{q}$ for all $\mathcal{D}\in E^{+}$,
and $\mathcal{D}\not\models\boldsymbol{q}$ for all $\mathcal{D}\in E^{-}$.
Separation underpins the query-by-example approach, which aims to support
database users in constructing queries and schema mappings with the help of
data examples Alexe et al. (2011); Martins (2019), inductive logic programming
Cropper et al. (2022), and, more recently, automated feature extraction, where
separating queries are proposed as features in classifier engineering
Kimelfeld and Ré (2018); Barceló et al. (2021). Separating queries (and, more
generally, formulas) also underpin recent logic-based approaches aiming to
explain positive and negative data examples given by applications Sarker et
al. (2017); Camacho and McIlraith (2019); Raha et al. (2022).

The space of all separating queries, denoted $\mathsf{s}(E,\mathcal{Q})$,
forms a convex subset of $\mathcal{Q}$ under the containment (or logical
entailment) relation $\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ between
queries $\boldsymbol{q}$, $\boldsymbol{q}^{\prime}$, and is an instance of the
more general version spaces Mitchell (1982). If finite,
$\mathsf{s}(E,\mathcal{Q})$ can be represented by its extremal elements: the
most specific (logically strongest) and most general (logically weakest)
separators in $\mathcal{Q}$. In fact, many known algorithms check the
existence of separators by looking for a most specific one ten Cate and Dalmau
(2015); Barceló and Romero (2017); Gutiérrez-Basulto et al. (2018); Funk et
al. (2019). This is not surprising as query classes are often closed under
$\land$, and so the conjunction of all separators gives the unique most
specific one. Dually, the unique most general separator is given by the
disjunction of all separators if the query class is closed under $\lor$, which
is a less common assumption. For the case of first-order queries constructed
using $\land$ and existential quantifiers (conjunctive queries or CQs), a
systematic study of extremal separation has recently been conducted in the
award winning ten Cate et al. (2023).

Here, we study extremal separation for temporal instance queries. Data
instances take the form $(\delta_{0},\dots,\delta_{n})$ describing temporal
evolutions, where the $\delta_{i}$ are the sets of atomic propositions that
are true at time $i$. Queries are formulated in the fragment of linear
temporal logic LTL with the operators $\land$, $\bigcirc$ (next), and
$\Diamond$ (eventually). These
_${\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond$ -queries_ and
its subclass of _$\Diamond$ -queries_ without $\bigcirc$, are obtained by
restricting CQs to propositional temporal data and form the core of most
temporal query languages proposed in the database and knowledge representation
literature Chomicki and Toman (2018); Baader et al. (2015); Borgwardt et al.
(2015); Artale et al. (2021). We are particularly interested in subclasses of
the classes of
${\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond$-and
$\Diamond$-queries that are not closed under $\land$ and take the form of path
queries:

$\boldsymbol{q}=\rho_{0}\land{\boldsymbol{o}}_{1}(\rho_{1}\land{\boldsymbol{o}}_{2}(\rho_{2}\land\dots\land{\boldsymbol{o}}_{n}\rho_{n}))$
(1)

with
${\boldsymbol{o}}_{i}\in\\{{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}},\Diamond\\}$
and conjunctions $\rho_{i}$ of atoms. The temporal patterns expressed by path
queries correspond to common subsequences, subwords, and combinations thereof,
which have been investigated in the string pattern matching literature for
more than 50 years. Their applications range from computational linguistics to
bioinformatics and revision control systems Bergroth et al. (2000); Chowdhury
et al. (2010); Abboud et al. (2015); Blum et al. (2021). In fact, our results
can also be interpreted and applied in that research tradition and our
techniques combine both logic and automata-based methods with pattern
matching. We note that not admitting $\lor$ in our query languages is crucial
for finding this type of patterns and adding it would often trivialise
separation.

######  Example 1.

Suppose the first two sequences of events shown below are ‘positive’, the
third one is ‘negative’, and our task is to explain this phenomenon using
path queries. The space of

$0$$A$$1$$B$$2$$C$$3$ $0$$1$$A$$2$$B$$3$$C$$4$ $0$$A$$1$$B$$2$$3$$C$$4$

possible explanations includes
$\boldsymbol{q}_{1}=\Diamond(A\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(B\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}C))$,
$\boldsymbol{q}_{2}=\Diamond(A\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}C)$
and
$\boldsymbol{q}_{3}=\Diamond(B\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}C)$,
all of which are true at $0$ in the positive examples and false in the
negative one. In fact, $\boldsymbol{q}_{1}$ is the unique most specific
explanation, while $\boldsymbol{q}_{2}$ and $\boldsymbol{q}_{3}$ are the non-
equivalent most general ones. On the other hand, there exists no explanation
in terms of $\Diamond$ only.

The (bounded-size) separator existence problem for various classes
$\mathcal{Q}$ of LTL-queries has recently been studied in Fijalkow and Lagarde
(2021); Raha et al. (2022); Fortin et al. (2023). Our aim here is to
investigate systematically the separator spaces $\mathsf{s}(E,\mathcal{Q})$ by
determining the complexity of verifying and counting most specific and general
separators and giving algorithms computing them. On our way, we determine the
complexity of entailment (aka containment in database theory) between queries
and computing weakening and strengthening frontiers, which are the key to
understanding $\mathsf{s}(E,\mathcal{Q})$. Intuitively, a
weakening/strengthening frontier of $\boldsymbol{q}\in\mathcal{Q}$ is a set of
queries properly weaker/stronger than $\boldsymbol{q}$ that form a boundary
between $\boldsymbol{q}$ and all of its weakenings/strengthenings in
$\mathcal{Q}$.

In detail, we first prove that query containment is in P for the class of
$\Diamond$-queries and all of our classes of path queries. Based on this
result, we show that strengthening and weakening frontiers can be computed in
polytime for path queries. This is also the case for $\Diamond$-queries and
weakening frontiers but not for strengthening ones. It follows that checking
whether a path query is a most specific/general separator and whether a
$\Diamond$-query is a most general one are both in P. In contrast, we
establish coNP-completeness of checking whether a $\Diamond$-query is a most
specific separator and whether a path query is the unique most
specific/general one. Using frontiers, we show for path queries that the
existence of unique most specific/general separators is in the complexity
class US (for which unique SAT is complete) and that counting the number of
most general/specific separators is in $\sharp$P. We show that these upper
bounds are tight, sometimes using the rich literature on algorithms for
sequences (e.g., longest common subsequences). Our lower bounds mostly require
only a bounded number of atomic propositions and an unbounded number of either
negative or positive examples.

These complexity results are complemented with algorithms for computing
extremal separators in the majority of our query classes. The algorithms use a
graph encoding of the input example set, associating (extremal) separators
with certain paths in the graph. Complexity-wise, they are optimal, running in
polytime if the number of examples is bounded and exponential time otherwise.

###  1.1 Related Work

Being inspired by the investigation of extremal separation for first-order
conjunctive queries (CQs) ten Cate et al. (2023), our results turn out to be
very different. For instance, while separability by CQs is NExpTime-complete
and separating queries are exponential in the size of the examples (the
extremal ones even larger), the extremal separation problems for LTL-queries
are often complete for SAT-related complexity classes, with separating queries
being of polynomial size. For work on separation in the query-by-example
paradigm we refer the reader to Zhang et al. (2013); Weiss and Cohen (2017);
Kalashnikov et al. (2018); Deutch and Gilad (2019); Staworko and Wieczorek
(2012); Barceló and Romero (2017); Cohen and Weiss (2016); Arenas et al.
(2016) in the database context and to Gutiérrez-Basulto et al. (2018); Ortiz
(2019); Cima et al. (2021); Jung et al. (2022) in the context of KR.

Our contribution is also closely related to work on synthesising LTL-formulas
that explain the positive and negative data examples coming from an
application Lemieux et al. (2015); Neider and Gavran (2018); Camacho and
McIlraith (2019); Raha et al. (2022); Fortin et al. (2022, 2023). While
concerned with separability of temporal data instances and, in particular,
separability by LTL-formulas of small size, the separator spaces
$\mathsf{s}(E,\mathcal{Q})$ themselves have not yet been investigated in this
context.

##  2 Data and Queries in LTL

Fix some countably-infinite set of unary predicate symbols, called _atoms_. A
_signature_ , $\sigma$, is any finite set of atoms. A (_temporal_) _data
instance_ is any finite set $\mathcal{D}\neq\emptyset$ of _facts_ $A(\ell)$
with an atom $A$ and a _timestamp_ $\ell\in\mathbb{N}$, saying that $A$
happened at $\ell$. The _size_ $|\mathcal{D}|$ of $\mathcal{D}$ is the number
of symbols in it, with the timestamps given in _unary_. Let $\max\mathcal{D}$
be the maximal timestamp in $\mathcal{D}$. Where convenient, we also write
$\mathcal{D}$ as the word $\delta_{0}\dots\delta_{\max\mathcal{D}}$ with
$\delta_{i}=\\{A\mid A(i)\in\mathcal{D}\\}$. The _signature_
$\mathsf{sig}(\mathcal{D})$ of $\mathcal{D}$ is the set of atoms occurring in
it.

We query data instances by means of LTL-formulas, called _queries_ , that are
built from atoms (treated as propositional variables) and the logical constant
$\top$ (truth) using $\land$ and the temporal operators $\bigcirc$ (next time)
and $\Diamond$ (sometime in the future). We consider the following classes of
queries:

$\mathcal{Q}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$:

all ${\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond$-_queries_ ;

$\mathcal{Q}[\Diamond]$:

all $\Diamond$-_queries_ (not containing $\bigcirc$);

$\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$:

_path ${\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond$-queries_
of the form (1), where the conjunctions of atoms $\rho_{i}$ are often treated
as sets and the empty conjunction as $\top$;

$\mathcal{Q}_{p}[\Diamond]$:

all _path $\Diamond$-queries_ (not containing $\bigcirc$);

$\mathcal{Q}_{\textit{in}}$:

_interval-queries_ of the form (1) with $\rho_{0}=\top$, $\rho_{1}\neq\top$,
${\boldsymbol{o}}_{1}=\Diamond$, and
${\boldsymbol{o}}_{i}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$,
for $i>1$.

Queries in $\mathcal{Q}_{\textit{in}}$ single out an interval of a fixed
length starting at some time-point $\geq 1$;
$\boldsymbol{q}_{1}$–$\boldsymbol{q}_{3}$ from Example 1 are in
$\mathcal{Q}_{\textit{in}}$. $\mathcal{Q}^{\sigma}$ is the restriction of a
class $\mathcal{Q}$ to a signature $\sigma$. The _temporal depth_
$\mathit{tdp}(\boldsymbol{q})$ of $\boldsymbol{q}$ is the maximum number of
nested temporal operators in $\boldsymbol{q}$. The _signature_
$\mathsf{sig}(\boldsymbol{q})$ of $\boldsymbol{q}$ is the set of atoms in
$\boldsymbol{q}$; the _size_ $|\boldsymbol{q}|$ of $\boldsymbol{q}$ is the
number of symbols in it.

The _truth-relation_ $\mathcal{D},n\models\boldsymbol{q}$—saying that
$\boldsymbol{q}$ is true in $\mathcal{D}$ at moment $n\in\mathbb{N}$—is
defined as usual in temporal logic under the _strict semantics_ :
$\mathcal{D},n\models\top$ for all $n\in\mathbb{N}$; $\mathcal{D},n\models
A_{i}$ iff $A_{i}(n)\in\mathcal{D}$;
$\mathcal{D},n\models{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\boldsymbol{q}^{\prime}$
iff $\mathcal{D},n+1\models\boldsymbol{q}^{\prime}$; and
$\mathcal{D},n\models\Diamond\boldsymbol{q}^{\prime}$ iff
$\mathcal{D},m\models\boldsymbol{q}^{\prime}$, for some $m>n$. A data instance
$\mathcal{D}$ is called a _positive example_ for a query $\boldsymbol{q}$ if
$\mathcal{D},0\models\boldsymbol{q}$; otherwise, $\mathcal{D}$ is a _negative
example_ for $\boldsymbol{q}$. Checking whether $\mathcal{D}$ is a positive
(negative) example for our queries $\boldsymbol{q}$ can obviously be done in
polytime in $|\mathcal{D}|$ and $|\boldsymbol{q}|$.

We write $\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ if
$\mathcal{D},0\models\boldsymbol{q}$ implies
$\mathcal{D},0\models\boldsymbol{q}^{\prime}$ for all instances $\mathcal{D}$,
and $\boldsymbol{q}\equiv\boldsymbol{q}^{\prime}$ if
$\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ and
$\boldsymbol{q}^{\prime}\models\boldsymbol{q}$, in which case $\boldsymbol{q}$
and $\boldsymbol{q}^{\prime}$ are _equivalent_. For example, for any query
$\boldsymbol{q}$, we have
$\Diamond{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\boldsymbol{q}\equiv{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond\boldsymbol{q}\equiv\Diamond\Diamond\boldsymbol{q}$.
It follows that every path query in
$\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
is equivalent to a query of the form (1), in which $\rho_{n}\neq\top$ and
whenever $\rho_{i}=\top$, $0<i<n$, then
${\boldsymbol{o}}_{i}={\boldsymbol{o}}_{i+1}$; in this case we say that
$\boldsymbol{q}$ is in _normal form_. Unless indicated otherwise, we assume
all path queries to be in normal form.

Sequences. There is a close link between evaluating path queries and
algorithms for finding patterns in strings Crochemore et al. (2007). A
_sequence_ is a data instance $\mathcal{D}=\delta_{0}\dots\delta_{n}$ with
$\delta_{0}=\emptyset$ and $|\delta_{i}|=1$, for $i>0$; a _sequence query_ is
a path query of the form (1) with $|\rho_{0}|=0$ and $|\rho_{i}|=1$, for
$i>0$. Querying sequences using sequence queries corresponds to the following
matching problems:

  * –

for any sequence query $\boldsymbol{q}\in\mathcal{Q}_{p}[\Diamond]$ of the
form (1), we have $\mathcal{D},0\models\boldsymbol{q}$ iff
$\rho_{1}\dots\rho_{m}$ is a _subsequence_ of $\mathcal{D}$;

  * –

for any sequence query $\boldsymbol{q}\in\mathcal{Q}_{\textit{in}}$ of the
form (1), we have $\mathcal{D},0\models\boldsymbol{q}$ iff
$\rho_{1}\dots\rho_{m}$ is a _subword_ of $\mathcal{D}$.

##  3 Query Containment

The _query containment problem_ for a class $\mathcal{Q}$ of queries is to
decide whether $\boldsymbol{q}\models\boldsymbol{q}^{\prime}$, for any given
$\boldsymbol{q},\boldsymbol{q}^{\prime}\in\mathcal{Q}$. In contrast to
conjunctive queries, where query containment is NP-complete Chandra and Merlin
(1977), query containment is tractable for the majority of query classes
defined above:

######  Theorem 2.

The query containment problems for
$\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$,
$\mathcal{Q}[\Diamond]$ (and their subclasses) are all in P.

To prove Theorem 2, suppose first that we are given two queries
$\boldsymbol{q},\boldsymbol{q}^{\prime}\in\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$,
where $\boldsymbol{q}$ takes of the form (1) and
$\boldsymbol{q}^{\prime}=\rho_{0}^{\prime}\wedge{\boldsymbol{o}}_{1}^{\prime}(\rho_{1}^{\prime}\wedge\cdots\wedge{\boldsymbol{o}}_{m}^{\prime}\rho_{m}^{\prime})$.
Denote by $[m]$ the closed interval $[0,m]\subseteq\mathbb{N}$. A function
$h\colon[m]\rightarrow[n]$ is _monotone_ if $h(i)<h(j)$ whenever $i<j$. Then
tractability of containment for path queries follows from the criterion below,
which is proved in the appendix by induction on
$\mathit{tdp}(\boldsymbol{q}^{\prime})$:

######  Lemma 3.

Let
$\boldsymbol{q},\boldsymbol{q}^{\prime}\in\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$.
Then $\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ iff there is a monotone
function $h\colon[m]\rightarrow[n]$ such that $h(0)=0$ and, for all $i\in[m]$,
we have $\rho_{i}^{\prime}\subseteq\rho_{h(i)}$ and if
${\boldsymbol{o}}_{i+1}^{\prime}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$,
then
${\boldsymbol{o}}_{h(i+1)}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$
and $h(i+1)=h(i)+1$.

We refer to any function $h$ defined in Lemma 3 as a _containment witness_ for
the pair
$\boldsymbol{q},\boldsymbol{q}^{\prime}\in\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$.

Suppose now $\boldsymbol{q}\in\mathcal{Q}[\Diamond]$. As shown in Fortin et
al. (2022), we can convert $\boldsymbol{q}$ in polytime to an equivalent query
in the _normal form_
$\rho\wedge\boldsymbol{q}_{1}\wedge\cdots\wedge\boldsymbol{q}_{n}$, where
$\rho$ is a conjunction of atoms and each $\boldsymbol{q}_{i}$ is in
$\mathcal{Q}_{p}[\Diamond]$ and starts with $\Diamond$. Tractability of
containment for $\mathcal{Q}[\Diamond]$-queries follows from:

######  Lemma 4.

If
$\boldsymbol{q}=\rho\wedge\boldsymbol{q}_{1}\wedge\cdots\wedge\boldsymbol{q}_{n}\in\mathcal{Q}[\Diamond]$
is in normal form, $\boldsymbol{q}^{\prime}\in\mathcal{Q}_{p}[\Diamond]$ and
$\boldsymbol{q}\models\boldsymbol{q}^{\prime}$, then there is
$\boldsymbol{q}_{i}$, $1\leq i\leq n$, with
$\rho\wedge\boldsymbol{q}_{i}\models\boldsymbol{q}^{\prime}$.

###### Proof.

In the detailed proof given in the appendix, we show that, assuming
$\rho\wedge\boldsymbol{q}_{i}\not\models\boldsymbol{q}^{\prime}$ for all $i$,
we can convert the $\boldsymbol{q}_{i}$ into a data instance $\mathcal{D}$
with $\mathcal{D},0\models\boldsymbol{q}$ and
$\mathcal{D},0\not\models\boldsymbol{q}^{\prime}$. ∎

For queries
$\boldsymbol{q}\in\mathcal{Q}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$,
Lemma 4 does not hold:

######  Example 5.

Let
$\boldsymbol{q}=\boldsymbol{q}_{1}\land\boldsymbol{q}_{2}\land\boldsymbol{q}_{3}\land\boldsymbol{q}_{4}$,
where

$\displaystyle\boldsymbol{q}_{1}=\Diamond(a\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}((a\wedge
b)\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}a)),$
$\displaystyle\boldsymbol{q}_{2}=\Diamond(b\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}((a\wedge
b)\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}b)),$
$\displaystyle\boldsymbol{q}_{3}=\Diamond(a\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}((a\wedge
b)\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}b)),$
$\displaystyle\boldsymbol{q}_{4}=\Diamond(a\land\Diamond(b\land\Diamond(a\land\Diamond(b\land\Diamond(a\land\Diamond
b))))),$

and $\boldsymbol{q}^{\prime}=\Diamond(b\wedge\Diamond((a\wedge
b)\wedge\Diamond a))$. Then $\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ but
$\boldsymbol{q}_{i}\not\models\boldsymbol{q}^{\prime}$, for any $i$, $1\leq
i\leq 4$.

At the moment, the question whether containment of
$\mathcal{Q}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$-queries
is tractable remains open.

##  4 Example Sets and Separating Queries

An _example set_ $E$ is a pair $(E^{+},E^{-})$ of finite sets
$E^{+}\neq\emptyset$ and $E^{-}$ of data instances. We say that a query
$\boldsymbol{q}$ _separates_ $E$ if all $\mathcal{D}\in E^{+}$ are positive
examples and all $\mathcal{D}\in E^{-}$ are negative examples for
$\boldsymbol{q}$. Denote by $\mathsf{s}(E,\mathcal{Q})$ the set of queries in
a class $\mathcal{Q}$ separating $E$ and call $E$ $\mathcal{Q}$-_separable_ if
$\mathsf{s}(E,\mathcal{Q})\neq\emptyset$. Our general aim is to understand the
structure of $\mathsf{s}(E,\mathcal{Q})$ for various important query classes
$\mathcal{Q}$.

We consider queries in $\mathcal{Q}$ _modulo equivalence_ , not distinguishing
between $\boldsymbol{q}\equiv\boldsymbol{q}^{\prime}$. In this case, the
relation $\models$ is a partial order on $\mathcal{Q}$. For any
$\boldsymbol{q}\in\mathsf{s}(E,\mathcal{Q})$, we clearly have

  * –

$\mathit{tdp}(\boldsymbol{q})\leq\min\\{\max\mathcal{D}\mid\mathcal{D}\in
E^{+}\\}$,

  * –

$\mathsf{sig}(\boldsymbol{q})\subseteq\bigcap\\{\mathsf{sig}(\mathcal{D})\mid\mathcal{D}\in
E^{+}\\}$,

so $\mathsf{s}(E,\mathcal{Q})$ is finite. We refer to the $\models$-minimal
elements of $\mathsf{s}(E,\mathcal{Q})\neq\emptyset$ as _most specific
$\mathcal{Q}$-separators of_ $E$ and to the $\models$-maximal elements as
_most general $\mathcal{Q}$-separators of_ $E$ (modulo $\equiv$); they
comprise the sets $\mathsf{mss}(E,\mathcal{Q})$ and
$\mathsf{mgs}(E,\mathcal{Q})$, respectively. If these sets are singletons, we
call their only element the _unique most specific_ and, respectively, _unique
most general $\mathcal{Q}$-separator of_ $E$. Note that the former always
exists if $\mathsf{s}(E,\mathcal{Q})\neq\emptyset$ and $\mathcal{Q}$ is closed
under $\land$.

######  Example 6.

$(i)$ Suppose $\mathcal{D}^{+}=\\{A(0),B(0),A(1),B(1)\\}$,
$\mathcal{D}^{-}=\\{A(0)\\}$ and
$E=(\\{\mathcal{D}^{+}\\},\\{\mathcal{D}^{-}\\})$. The separator space
$\mathsf{s}(E,\mathcal{Q}_{p}[\Diamond])$ is shown below as a Hasse diagram
with arrows indicating the partial order $\models$ (and
$\top,A\notin\mathsf{s}(E,\mathcal{Q}_{p}[\Diamond])$), so

$A\land B\land\Diamond(A\land B)$$A\land B\land\Diamond A$$A\land
B\land\Diamond B$$A\land\Diamond(A\land B)$$B\land\Diamond(A\land B)$$A\land
B$$A\land\Diamond A$$A\land\Diamond B$$B\land\Diamond A$$B\land\Diamond
B$$\Diamond(A\land B)$$A$$B$$\Diamond A$$\Diamond B$$\top$

the most general $\mathcal{Q}_{p}[\Diamond]$-separators of $E$ comprise the
set $\mathsf{mgs}(E,\mathcal{Q}_{p}[\Diamond])=\\{B,\Diamond A,\Diamond B\\}$
and the unique most specific one is $A\land B\land\Diamond(A\land B)$.

$(ii)$ For the example set
$E=(\\{\mathcal{D}^{+}_{1},\mathcal{D}^{+}_{2}\\},\\{\mathcal{D}^{-}_{1}\\})$
with

$\mathcal{D}^{+}_{1}=\\{A(1),B(2)\\},\mathcal{D}^{+}_{2}=\\{B(1),A(2)\\},\mathcal{D}^{-}_{1}=\\{C(0)\\},$

$\mathsf{s}(E,\mathcal{Q}_{p}[\Diamond])=\\{\Diamond A,\Diamond
B\\}=\mathsf{mss}/\mathsf{mgs}(E,\mathcal{Q}_{p}[\Diamond])$ but there is no
unique most specific/general separator. In contrast,
$\mathsf{s}(E,\mathcal{Q}[\Diamond])=\\{\Diamond A,\Diamond B,\Diamond
A\land\Diamond B\\}$ has the unique most specific separator $\Diamond
A\land\Diamond B$ but no unique most general one.

$(iii)$ One can show that $\mathsf{mss}/\mathsf{mgs}(E,\mathcal{Q})$ always
contains a _longest/shortest separator_ of $E$ in $\mathcal{Q}$ (of
largest/smallest temporal depth). To illustrate, let
$E=(\\{\mathcal{D}^{+}_{1}\\},\\{\mathcal{D}^{-}_{1},\mathcal{D}^{-}_{2},\mathcal{D}^{-}_{3}\\})$,

$\displaystyle\mathcal{D}^{+}_{1}=\\{B(0),C(0),A(1)\\},$ $\displaystyle\hskip
28.45274pt\mathcal{D}^{-}_{1}=\\{B(0)\\},\ \mathcal{D}^{-}_{2}=\\{C(0)\\},\
\mathcal{D}^{-}_{3}=\\{A(1)\\}.$

Then $\mathsf{mgs}(E,\mathcal{Q}_{p}[\Diamond])=\\{B\land C,B\land\Diamond
A,C\land\Diamond A\\}$, where $B\land C$ of depth 0 is the shortest separator
of $E$ in $\mathcal{Q}_{p}[\Diamond]$.

Our main concern is the following three algorithmic problems for query classes
$\mathcal{Q}\subseteq\mathcal{Q}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
with input $E$ and $\boldsymbol{q}\in\mathcal{Q}$:

(most specific/general separator verification):

decide whether $\boldsymbol{q}$ is an element of $\mathsf{mss}(E,\mathcal{Q})$
/ $\mathsf{mgs}(E,\mathcal{Q})$;

(counting most specific/general separators):

count the elements of $\mathsf{mss}(E,\mathcal{Q})$ /
$\mathsf{mgs}(E,\mathcal{Q})$;

(computing a most specific/general separator):

construct some query in $\mathsf{mss}(E,\mathcal{Q})$ /
$\mathsf{mgs}(E,\mathcal{Q})$.

We are particularly interested in deciding whether there is a unique most
specific/general separator and computing it. To achieve our aims, we obviously
should be able to decide whether $\boldsymbol{q}\in\mathsf{s}(E,\mathcal{Q})$
(_separator verification_) and whether
$\mathsf{s}(E,\mathcal{Q})\neq\emptyset$ (_separator existence_). As mentioned
in Section 2, separator verification is in P. We are also interested in the
case when the number of positive or negative examples in $E$ is bounded. The
table below summarises the complexities of separator existence for our query
classes, where $\mathsf{b}^{+}$ / $\mathsf{b}^{-}$

separator existence $\mathsf{b}^{+}\\!\\!,\,\mathsf{b}^{-}$ $\mathsf{b}^{+}$
$\mathsf{b}^{-}$ or unbounded
$\mathcal{Q}_{p}[\Diamond]\,/\,\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
in P NP-c. NP-c.
$\mathcal{Q}[\Diamond]\,/\,\mathcal{Q}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]\,/\,\mathcal{Q}_{\textit{in}}$
in P in P NP-c.

means that $|E^{+}|$ / $|E^{-}|$ is bounded, and one can assume a bounded
signature. Except for $\mathcal{Q}_{\textit{in}}$, these results are shown in
Fortin et al. (2023). The proofs use techniques developed for the _longest
common subsequence problem_ (given $k>0$ and a set $E^{+}$ of sequences, is
there a sequence query in $\mathcal{Q}_{p}[\Diamond]$ of depth $\geq k$ that
is a subsequence of all $\mathcal{D}\in E^{+}$; see Section 2) and separator
existence for sequence queries in $\mathcal{Q}_{p}[\Diamond]$ Maier (1978);
Fraser (1996). The NP-upper bound for $\mathcal{Q}_{\textit{in}}$ is trivial;
the lower one follows from the proof of Theorem 21, and tractability for
$\mathsf{b}^{+}$ is ensured by the observation that there are polynomially-
many relevant intervals in the $E^{+}$-examples.

This NP-lower bound shows that great care is needed when transferring
techniques from the literature on algorithms for sequences to our framework as
separability of example sets of sequences using sequence queries in
$\mathcal{Q}_{\textit{in}}$ is easily seen to be in P even for unbounded
example sets and signatures.

A key to the extremal separator problems above is the following notions of
strengthening and weakening frontiers.

##  5 Strengthening and Weakening Frontiers

Let $\mathcal{Q}$ be a class of queries and $\boldsymbol{q}\in\mathcal{Q}$. A
set $\mathcal{F}\subseteq\mathcal{Q}$ is called a _strengthening frontier_ for
$\boldsymbol{q}$ in $\mathcal{Q}$ if

  * –

for any $\boldsymbol{q}^{\prime}\in\mathcal{F}$, we have
$\boldsymbol{q}^{\prime}\models\boldsymbol{q}$ and
$\boldsymbol{q}^{\prime}\not\equiv\boldsymbol{q}$;

  * –

for any $\boldsymbol{q}^{\prime\prime}\in\mathcal{Q}$, if
$\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}$ and
$\boldsymbol{q}^{\prime\prime}\not\equiv\boldsymbol{q}$, then there is
$\boldsymbol{q}^{\prime}\in\mathcal{F}$ such that
$\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}^{\prime}$.

A set $\mathcal{F}\subseteq\mathcal{Q}$ is called a _weakening frontier_ for
$\boldsymbol{q}$ in $\mathcal{Q}$ if

  * –

for any $\boldsymbol{q}^{\prime}\in\mathcal{F}$, we have
$\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ and
$\boldsymbol{q}^{\prime}\not\equiv\boldsymbol{q}$;

  * –

for any $\boldsymbol{q}^{\prime\prime}\in\mathcal{Q}$, if
$\boldsymbol{q}\models\boldsymbol{q}^{\prime\prime}$ and
$\boldsymbol{q}^{\prime\prime}\not\equiv\boldsymbol{q}$, then there is
$\boldsymbol{q}^{\prime}\in\mathcal{F}$ with
$\boldsymbol{q}^{\prime}\models\boldsymbol{q}^{\prime\prime}$.

Trivial strengthening/weakening frontiers for $\boldsymbol{q}$ comprise all
queries that are properly stronger/weaker than $\boldsymbol{q}$ in
$\mathcal{Q}$; our concern, however, is finding small frontiers. We show now
that, for $\mathcal{Q}^{\sigma}_{p}[\Diamond]$ and
$\mathcal{Q}^{\sigma}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$,
one can compute a strengthening/weakening frontier for any given
$\boldsymbol{q}$ in polytime.

######  Theorem 7.

Let
$\boldsymbol{q}\in\mathcal{Q}^{\sigma}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
be in normal form (1). A strengthening frontier for $\boldsymbol{q}$ in
$\mathcal{Q}^{\sigma}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
can be computed in polytime by applying once to $\boldsymbol{q}$ one of the
following operations, for $i\in[n]$ and
$\boldsymbol{q}_{i}=\rho_{i}\land{\boldsymbol{o}}_{i+1}(\rho_{i+1}\land\dots\land{\boldsymbol{o}}_{n}\rho_{n})$:

  1. 1.

extend some $\rho_{i}$ in $\boldsymbol{q}$ by some
$A\in\sigma\setminus\rho_{i}$;

  2. 2.

replace some $\Diamond\boldsymbol{q}_{i}$ in $\boldsymbol{q}$ by
$\Diamond(\top\land\Diamond\boldsymbol{q}_{i})$;

  3. 3.

replace some ${\boldsymbol{o}}_{i}=\Diamond$ in $\boldsymbol{q}$ by $\bigcirc$
provided that the resulting query is in normal form;

  4. 4.

add ${\boldsymbol{o}}_{n+1}\rho_{n+1}$ at the end of $\boldsymbol{q}$, where
${\boldsymbol{o}}_{n+1}=\Diamond$ and $\rho_{n+1}=A$, for some $A\in\sigma$.

If $\boldsymbol{q}\in\mathcal{Q}^{\sigma}_{p}[\Diamond]$, a strengthening
frontier for $\boldsymbol{q}$ in $\mathcal{Q}^{\sigma}_{p}[\Diamond]$ can be
computed in polytime using operations 1, 2, and 4.

###### Proof.

Let $\mathcal{F}$ be the set of queries obtained by a single application of
one of these operations to $\boldsymbol{q}$. By Lemma 3,
$\boldsymbol{q}^{\prime}\models\boldsymbol{q}$ and
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$ for all
$\boldsymbol{q}^{\prime}\in\mathcal{F}$. Let
$\boldsymbol{q}^{\prime}\models\boldsymbol{q}$ and
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$, for some
$\boldsymbol{q}^{\prime}\in\mathcal{Q}^{\sigma}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
of the form
$\boldsymbol{q}^{\prime}=\rho_{0}^{\prime}\wedge{\boldsymbol{o}}_{1}^{\prime}(\rho_{1}^{\prime}\wedge\cdots\wedge{\boldsymbol{o}}_{m}^{\prime}(\rho_{m}^{\prime}))$.
Take a containment witness $h\colon[n]\rightarrow[m]$ for
$\boldsymbol{q}^{\prime},\boldsymbol{q}$. If $h$ is surjective, then $n=m$ and
$h(i)=i$ for all $i\in[n]$, and so $\rho_{i}\subseteq\rho_{i}^{\prime}$. As
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$, either
${\boldsymbol{o}}_{i}^{\prime}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$
and ${\boldsymbol{o}}_{i}=\Diamond$, for some $i\in[n]$, or
$\rho_{i}\subsetneq\rho_{i}^{\prime}$, for some $i\in[n]$. In the former case,
operation 3 gives $\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ with
$\boldsymbol{q}^{\prime}\models\boldsymbol{q}^{\prime\prime}$; in the latter
one, operation 1 gives such a $\boldsymbol{q}^{\prime\prime}$.

Suppose $h$ is not surjective. If there is $i<n$ such that $h(i+1)-h(i)\geq
2$, then $\boldsymbol{q}^{\prime}\models\boldsymbol{q}^{\prime\prime}$ for a
$\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ given by operation 2. Otherwise
$m$ is not in the range of $h$, and we get such a
$\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ by operation 4. ∎

######  Example 8.

For $\sigma=\\{A,B\\}$ and
$\boldsymbol{q}=\Diamond(A\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}B)$,
operations 1–4 give the following strengthening frontier for $\boldsymbol{q}$:

$\displaystyle\Diamond(A\land
B\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}B),\Diamond(A\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(A\land
B)),\Diamond(\top\land\Diamond(A\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}B)),$
$\displaystyle{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(A\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}B),\Diamond(A\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(B\land\Diamond
A)),\Diamond(A\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(B\land\Diamond
B)).$

A weakening frontier can be constructed by reversing operations 1–3 from
Theorem 7 and using a similar argument:

######  Theorem 9.

Let
$\boldsymbol{q}\in\mathcal{Q}^{\sigma}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
be in normal form (1). A weakening frontier for $\boldsymbol{q}$ in
$\mathcal{Q}^{\sigma}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
can be computed in polytime by applying once to $\boldsymbol{q}$ one of the
following operations, for $i\in[n]$ and
$\boldsymbol{q}_{i}=\rho_{i}\land{\boldsymbol{o}}_{i+1}(\rho_{i+1}\land\dots\land{\boldsymbol{o}}_{n}\rho_{n})$:

  1. 1.

drop some atom from $\rho_{i}$;

  2. 2.

replace some $\Diamond(\top\wedge\Diamond\boldsymbol{q}_{i})$ in
$\boldsymbol{q}$ by $\Diamond\boldsymbol{q}_{i}$;

  3. 3.

replace some
${\boldsymbol{o}}_{i}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$ by
$\Diamond$.

If $\boldsymbol{q}\in\mathcal{Q}^{\sigma}_{p}[\Diamond]$, a weakening frontier
for $\boldsymbol{q}$ in $\mathcal{Q}^{\sigma}_{p}[\Diamond]$ can be computed
in polytime using operations 1 and 2.

######  Example 10.

For $\sigma=\\{A,B\\}$ and
$\boldsymbol{q}=\Diamond(A\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}B)$,
operations 1-3 give the following weakening frontier for $\boldsymbol{q}$:

$\displaystyle\Diamond(\top\land\Diamond B),\quad\Diamond
A,\quad\Diamond(A\land\Diamond B).$

Note that the computed weakening frontier can be made smaller by omitting
$\Diamond A$, which is weaker than $\Diamond(A\land\Diamond B)$.

We next consider frontiers for queries in $\mathcal{Q}^{\sigma}[\Diamond]$. We
say that
$\boldsymbol{q}=\rho\wedge\boldsymbol{q}_{1}\wedge\cdots\wedge\boldsymbol{q}_{n}\in\mathcal{Q}^{\sigma}[\Diamond]$
in normal form is _redundancy-free_ if it does not contain
$\boldsymbol{q}_{i},\boldsymbol{q}_{j}$ with $i\neq j$ and
$\boldsymbol{q}_{i}\models\boldsymbol{q}_{j}$. Clearly, for any
$\boldsymbol{q}\in\mathcal{Q}^{\sigma}[\Diamond]$, we can compute an
equivalent redundancy-free
$\boldsymbol{q}^{\prime}\in\mathcal{Q}^{\sigma}[\Diamond]$ in polytime.

######  Theorem 11.

Let
$\boldsymbol{q}=\rho\wedge\boldsymbol{q}_{1}\wedge\cdots\wedge\boldsymbol{q}_{n}\in\mathcal{Q}^{\sigma}[\Diamond]$
be redundancy-free. A weakening frontier for $\boldsymbol{q}$ in
$\mathcal{Q}^{\sigma}[\Diamond]$ can be computed in polytime by a single
application of one of the following operations to $\boldsymbol{q}$:

  1. 1.

drop some atom from $\rho$;

  2. 2.

replace some $\boldsymbol{q}_{i}$ by $\bigwedge\mathcal{F}_{i}$, where
$\mathcal{F}_{i}$ is the weakening frontier for $\boldsymbol{q}_{i}$ in
$\mathcal{Q}^{\sigma}_{p}[\Diamond]$ provided by Theorem 9.

###### Proof.

Let $\mathcal{F}$ be the set of queries defined above. Clearly,
$\boldsymbol{q}\models\boldsymbol{q}^{\prime}$; as $\boldsymbol{q}$ is
redundancy-free and in view of Lemma 4,
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$ for all
$\boldsymbol{q}^{\prime}\in\mathcal{F}$. Suppose
$\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ and
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$, for some
$\boldsymbol{q}^{\prime}=\rho^{\prime}\wedge\boldsymbol{q}_{1}^{\prime}\wedge\cdots\land\boldsymbol{q}_{m}^{\prime}$
in $\mathcal{Q}^{\sigma}[\Diamond]$. By Lemma 4, $\rho^{\prime}\subseteq\rho$
and, for each $j$, $1\leq j\leq m$, there exists $f(j)$, $1\leq f(j)\leq n$,
with $\boldsymbol{q}_{f(j)}\models\boldsymbol{q}_{j}^{\prime}$. If
$\rho^{\prime}\subsetneq\rho$, then operation 1 gives a
$\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ with
$\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}^{\prime}$. Otherwise, as
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$, there is
$\boldsymbol{q}_{i}$ such that
$\boldsymbol{q}_{j}^{\prime}\not\models\boldsymbol{q}_{i}$ for all
$\boldsymbol{q}_{j}^{\prime}$, $1\leq j\leq m$. Let
$\boldsymbol{q}^{\prime\prime}$ be the query obtained from $\boldsymbol{q}$ by
replacing $\boldsymbol{q}_{i}$ with $\bigwedge\mathcal{F}_{i}$ by operation 2.
To establish $\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}^{\prime}$, it
suffices to show that $f(j)=i$ implies
$\bigwedge\mathcal{F}_{i}\models\boldsymbol{q}_{j}$. So suppose $f(j)=i$. Then
$\boldsymbol{q}_{j}^{\prime}\not\models\boldsymbol{q}_{i}$, and so, by the
definition of $\mathcal{F}_{i}$, there is
$\boldsymbol{q}_{i}^{\prime\prime}\in\mathcal{F}_{i}$ with
$\boldsymbol{q}_{i}^{\prime\prime}\models\boldsymbol{q}_{j}$. ∎

However, strengthening frontiers for queries in
$\mathcal{Q}^{\sigma}[\Diamond]$ are not necessarily of polynomial size as
shown by the following:

######  Example 12.

We represent queries in $\mathcal{Q}^{\sigma}[\Diamond]$ of the form (1) as
$\rho_{0}\dots\rho_{n}$. For $\sigma=\\{A_{1},A_{2},B_{1},B_{2}\\}$, let
$\boldsymbol{q}_{1}=\emptyset(\boldsymbol{q}\sigma)^{n}\boldsymbol{q}$,
$\boldsymbol{q}_{2}=\emptyset\sigma^{2n+1}$, and
$\boldsymbol{q}=\\{A_{1},A_{2}\\}\\{B_{1},B_{2}\\}$. Using (Fortin et al.,
2022, Example 18), one can show that any strengthening frontier for the query
$\boldsymbol{q}_{1}\land\boldsymbol{q}_{2}$ in
$\mathcal{Q}^{\sigma}[\Diamond]$ is of size $O(2^{n})$.

Note also that weakening frontiers for
$\boldsymbol{q}\in\mathcal{Q}_{\textit{in}}^{\sigma}$ can be computed in
polytime using operation 1 in Theorem 9 (if $i=1$ and $|\rho_{i}|=1$, we drop
$\top$ and take
$\Diamond(\rho_{2}\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(\rho_{3}\land\dots\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\rho_{n})$).
On the other hand, strengthening frontiers can be infinite:

######  Example 13.

All
$\Diamond(A\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}^{n}A)$,
$n>0$, are in any strengthening frontier for $\boldsymbol{q}=\Diamond A$ in
$\mathcal{Q}_{\textit{in}}^{\sigma}$, where $\sigma=\\{A\\}$.

As shown by Theorem 17, the lack of polytime computable strengthening
frontiers in $\mathcal{Q}[\Diamond]$ affects the complexity of verifying most
specific separators. In contrast, the lack of polytime computable
strengthening frontiers in $\mathcal{Q}_{\textit{in}}$ turns out to be
harmless. For $n\geq\mathit{tdp}(\boldsymbol{q})$, call
$\mathcal{F}\subseteq\mathcal{Q}$ an _$n$ -bounded weakening/strengthening
frontier_ for $\boldsymbol{q}$ in $\mathcal{Q}$ if $\mathcal{F}$ is a
weakening/strengthening frontier for $\boldsymbol{q}$ in the class
$\\{\boldsymbol{q}^{\prime}\in\mathcal{Q}\mid\mathit{tdp}(\boldsymbol{q}^{\prime})\leq
n\\}$ (we assume $n$ to be given in unary).

######  Theorem 14.

Weakening frontiers and $n$-bounded strengthening frontiers in
$\mathcal{Q}_{\textit{in}}^{\sigma}$ can be computed in polytime.

Theorems 7, 9 give an alternative way of polytime computing unique
characterisations of
$\mathcal{Q}^{\sigma}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$-queries
by examples Fortin et al. (2022), opening another route to studying unique
characterisations and exact learning of temporal queries.

##  6 Complexity

Now we show complexity bounds for the decision and counting problems from
Section 4, starting with verification and observing that polytime computable
$n$-bounded frontiers imply tractable verification of most specific/general
separators:

######  Lemma 15.

If an $n$-bounded strengthening/weakening frontier for
$\boldsymbol{q}\in\mathcal{Q}$ is polytime computable in $|\boldsymbol{q}|$
and $n$, then most specific/general separator verification for $\mathcal{Q}$
is in P.

###### Proof.

Let $n=\min\\{\max\mathcal{D}\mid\mathcal{D}\in E^{+}\\}$. We compute an
$n$-bounded strengthening frontier $\mathcal{F}$ for $\boldsymbol{q}$ in
$\mathcal{Q}$ and use that $\boldsymbol{q}\in\mathsf{mss}(E,\mathcal{Q})$ iff
$\boldsymbol{q}\in\mathsf{s}(E,\mathcal{Q})$ and
$\boldsymbol{q}^{\prime}\notin\mathsf{s}(E,\mathcal{Q})$ for all
$\boldsymbol{q}^{\prime}\in\mathcal{F}$. The case of
$\mathsf{mgs}(E,\mathcal{Q})$ is similar. ∎

######  Corollary 16.

Most specific/general separator verification is in P for
$\mathcal{Q}_{p}[\Diamond]$,
$\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$,
and $\mathcal{Q}_{\textit{in}}$. Most general separator verification is in P
for $\mathcal{Q}[\Diamond]$.

###### Proof.

It follows from Lemma 15 and Theorems 7, 9, 14 that most specific/general
separator verification is in P for $\mathcal{Q}_{p}[\Diamond]$,
$\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$,
and $\mathcal{Q}_{\textit{in}}$. By Theorem 11, most general separation
verification is also in P for $\mathcal{Q}[\Diamond]$. ∎

Most specific separator verification is harder for $\mathcal{Q}[\Diamond]$:

######  Theorem 17.

For $\mathcal{Q}[\Diamond]$, the most specific separator verification problem
coincides with the unique most specific separator verification problem and is
coNP-complete.

###### Proof.

As we know, $E$ has a unique most specific separator in
$\mathcal{Q}[\Diamond]$ iff
$\mathsf{s}(E,\mathcal{Q}[\Diamond])\neq\emptyset$. Hence most specific
separator verification coincides with unique most specific separator
verification. Given $\boldsymbol{q}$ and $E$, we can check in NP that either
$\boldsymbol{q}\notin\mathsf{s}(E,\mathcal{Q}[\Diamond])$ (which is in P) or
that there is $\boldsymbol{q}^{\prime}\in\mathsf{s}(E,\mathcal{Q}[\Diamond])$
with $\boldsymbol{q}^{\prime}\models\boldsymbol{q}$ and
$\boldsymbol{q}^{\prime}\not\equiv\boldsymbol{q}$ (which is in NP). This gives
the coNP upper bound. The more involved proof of the lower one (in the
appendix) is based on ideas similar to those in the proof of Theorem 21 below.
∎

In the cases when most specific/general separators are not necessarily unique,
we obtain the following:

######  Theorem 18.

Unique most specific/general separator verification in
$\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$,
$\mathcal{Q}_{p}[\Diamond]$, $\mathcal{Q}_{\textit{in}}$ as well as unique
most general separator verification in $\mathcal{Q}[\Diamond]$ are coNP-
complete.

###### Proof.

The upper bounds follow from Corollary 16. The lower ones are by reduction of
the problem to decide whether, for a Boolean formula $\varphi$ and a
satisfying assignment $\mathfrak{a}$, there is a satisfying assignment for
$\varphi$ different from $\mathfrak{a}$. We use ideas similar to those in the
proof of Theorem 21. ∎

We now turn to the existence and counting problems. Recall that Unique SAT is
the problem to decide whether there is exactly one satisfying assignment for a
propositional formula Blass and Gurevich (1982). It is in $\Delta_{2}^{p}$,
coNP-hard, and complete for the class US of problems solvable by a non-
deterministic polynomial-time Turing machine $M$ that accepts iff $M$ has
exactly one accepting path. A counting problem is in the class
$\sharp\textsc{P}$ if there is such $M$ whose number of accepting paths
coincides with the number of solutions to the problem Arora and Barak (2009).

######  Theorem 19.

For
$\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$,
$\mathcal{Q}_{p}[\Diamond]$, $\mathcal{Q}_{\textit{in}}$, counting most
specific/general separators is $\sharp P$-complete; the existence of a unique
most specific/general separator is US-complete. The same holds for most
general separators in $\mathcal{Q}[\Diamond]$.

Theorem 19 follows from the very general and fine-grained complexity results
provided by Theorems 20 and 21 below.

######  Theorem 20.

Let
$\mathcal{Q}\subseteq\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
be a class with polytime decidable membership and polytime computable
$n$-bounded strengthening/weakening frontiers for queries in $\mathcal{Q}$.
Then

  * –

counting most specific/general $\mathcal{Q}$-separators is in $\sharp P$;

  * –

the existence of a unique most specific/general $\mathcal{Q}$-separator is in
US.

This also holds for most general separators in classes of conjunctions of
${\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond$-path queries
closed under dropping conjuncts and having polytime computable weakening
frontiers.

###### Proof.

Given $E$, construct a TM $M$ that guesses a $\boldsymbol{q}\in\mathcal{Q}$
with $\mathit{tdp}(\boldsymbol{q})\leq
n=\min\\{\max\mathcal{D}\mid\mathcal{D}\in E^{+}\\}$ and accepts if
$\boldsymbol{q}$ separates $E$ and no $\boldsymbol{q}^{\prime}$ in the
$n$-bounded frontier for $\boldsymbol{q}$ in $\mathcal{Q}$ separates $E$. As
we know, the required checks are in P. In the second claim, $M$ guesses a
query
$\boldsymbol{q}=\rho\wedge\Diamond\boldsymbol{q}_{1}\wedge\dots\land\Diamond\boldsymbol{q}_{l}$
with
$\boldsymbol{q}_{i}\in\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
and $l\leq|E^{-}|$. ∎

For the lower bounds, we take into account the boundedness of
$\mathsf{sig}(E)$ and the cardinalities $|E^{+}|$ and $|E^{-}|$ of positive
and negative examples in $E$. The next result provides matching lower bounds
for Theorem 19 even if the signature is bounded and only one of $|E^{+}|$ and
$|E^{-}|$ is unbounded, except for $\mathcal{Q}_{\textit{in}}$ and
$\mathcal{Q}[\Diamond]$, where $|E^{+}|$ has to be unbounded.

######  Theorem 21.

Let
$\mathcal{Q}\subseteq\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
be any class of queries containing all $\Diamond\rho$ with a conjunction of
atoms $\rho$. Then

  * –

counting most specific/general $\mathcal{Q}$-separators is
$\sharp\textsc{P}$-hard;

  * –

the existence of unique most specific/general separator is US-hard

even for $E=(E^{+},E^{-})$ and $\sigma=\mathsf{sig}(E)$ with $(a)$
$|E^{-}|\leq 1$ or $(b)$ $|E^{-}|\leq 1$, $|\sigma|=2$ and
$\mathcal{Q}=\mathcal{Q}_{\textit{in}}$ or
$\mathcal{Q}\supseteq\mathcal{Q}_{p}[\Diamond]$, or $(c)$ $|E^{+}|\leq 4$,
$|\sigma|=3$, $\mathcal{Q}\supseteq\mathcal{Q}_{p}[\Diamond]$. This result
also holds for most general separators in $\mathcal{Q}[\Diamond]$ and
$|E^{-}|=1$, $|\sigma|=2$.

###### Proof.

We sketch the proof of the first claim by a parsimonious reduction from SAT
for an unbounded number of negative examples (which can be easily merged into
one). Take a CNF $\varphi=\psi_{1}\wedge\dots\wedge\psi_{k}$ with clauses
$\psi_{i}$ over variables $x_{1},\dots,x_{n}$. We construct $E=(E^{+},E^{-})$
such that there is a bijection between the satisfying assignments for
$\varphi$ and the separators for $E$ in
$\mathcal{Q}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
(even queries of the form $\Diamond\rho$). The claim follows from the fact
that the separating queries are mutually $\models$-incomparable. Define the
positive examples
$E^{+}=\\{\mathcal{D}_{0},\mathcal{D}_{0}^{\prime},\mathcal{D}_{1},\dots,\mathcal{D}_{n}\\}$
with $2n$ atoms $A_{1},\bar{A}_{1},\dots,A_{n},\bar{A}_{n}$ by taking

$\displaystyle\mathcal{D}_{0}=\\{A_{i}(1),\bar{A}_{i}(1)\mid 1\leq i\leq
n\\},$ $\displaystyle\mathcal{D}_{0}^{\prime}=\\{A_{i}(2),\bar{A}_{i}(2)\mid
1\leq i\leq n\\},$
$\displaystyle\mathcal{D}_{i}=\\{A_{i}(1),\bar{A}_{i}(2),A_{j}(1),\bar{A}_{j}(1),A_{j}(2),\bar{A}_{j}(2)\mid
i\neq j\\},$

for $1\leq i\leq n$. Let
$E^{-}=\\{\mathcal{D}_{1}^{1},\dots,\mathcal{D}_{k}^{1},\mathcal{D}^{2}_{1},\dots,\mathcal{D}^{2}_{n}\\}$,
where $\mathcal{D}_{i}^{1}$, $1\leq i\leq k$, comprises $\bar{A}_{j}(1)$ if
$x_{j}$ does not occur negatively in $\psi_{i}$, and $A_{j}(1)$ if $x_{j}$
does not occur positively in $\psi_{i}$, and
$\mathcal{D}_{i}^{2}=\\{A_{j}(1),\bar{A}_{j}(1)\mid j\neq i\\}$. For an
assignment $\mathfrak{a}$ for $x_{1},\dots,x_{n}$, let $\rho_{\mathfrak{a}}$
contain $A_{i}$ if $\mathfrak{a}(x_{i})=1$ and $\bar{A}_{i}$, otherwise. Now
our claim follows from the following: $(i)$ if $\mathfrak{a}$ satisfies
$\varphi$, then $\Diamond\rho_{\mathfrak{a}}$ separates $E$; $(ii)$ if
$\boldsymbol{q}\in\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
separates $E$, then $\boldsymbol{q}\equiv\Diamond\rho_{\mathfrak{a}}$, for
some $\mathfrak{a}$ satisfying $\varphi$.

To bound $\sigma$ and/or $E^{+}$, we give parsimonious reductions from SAT and
employ techniques for the longest common subsequence problem and separator
existence for sequence queries in $\mathcal{Q}_{p}[\Diamond]$ Blin et al.
(2012); Fraser (1996). ∎

Again, re-using techniques from the literature on algorithms for sequences
needs some care. Similar to separability, for example sets of sequences,
counting most general/specific sequence $\mathcal{Q}_{\textit{in}}$-separators
is easily seen to be in P even for unbounded signatures and example sets, but
Theorem 21 shows that this is not so for $\mathcal{Q}_{\textit{in}}$ on non-
sequence data instances.

Surprisingly, the complexities of counting most general separators and
deciding the existence of a unique one diverge if we bound the number of
examples, cf. Theorems 23 and 27.

######  Theorem 22.

Let $\mathcal{Q}=\mathcal{Q}[\Diamond]$ or
$\mathcal{Q}\subseteq\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
be any class containing all $\Diamond\rho$ with a conjunction of atoms $\rho$.
Then counting most general $\mathcal{Q}$-separators is $\sharp\textsc{P}$-hard
even for example sets $E=(E^{+},E^{-})$ with $|E^{+}|=2$ and $|E^{-}|=1$.

###### Proof.

The proof is by reduction from counting satisfying assignments for monotone
formulas: $E^{-}$ is as in the proof of Theorem 21 and the positive examples
are $\mathcal{D}_{0}$, $\mathcal{D}_{0}^{\prime}$. ∎

Theorem 22 does not hold for counting most specific separators in
$\mathcal{Q}_{\textit{in}}$, which is easily seen to be in P if $|E^{+}|$ is
bounded. It remains open whether some version of this theorem holds for most
specific separators in
$\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
or $\mathcal{Q}_{p}[\Diamond]$.

##  7 Algorithms

The frontiers defined in Section 5 give a polytime algorithm for computing a
most specific/general separator starting from _any_ given separator. Suppose
$\mathcal{Q}\in\\{\mathcal{Q}_{p}[\Diamond],\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond],\mathcal{Q}_{\textit{in}}\\}$,
we are given $\boldsymbol{q}\in\mathsf{s}(E,\mathcal{Q})$ and need a most
specific separator. By Theorems 7, 9, the length of the longest
$\models$-chain in
$\mathsf{s}(E,\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond])$
is polynomial in $|E|$.111In contrast, the proof of Theorem 21 shows the size
of the maximal antichain in $\mathsf{s}(E,\mathcal{Q}_{p}[\Diamond])$ is in
general exponential in $|E|$. We take, if possible, some
$\boldsymbol{q}^{\prime}\in\mathsf{s}(E,\mathcal{Q})$ in the strengthening
frontier for $\boldsymbol{q}$, then
$\boldsymbol{q}^{\prime\prime}\in\mathsf{s}(E,\mathcal{Q})$ in the
strengthening frontier for $\boldsymbol{q}^{\prime}$, etc. This process
terminates after polynomially-many steps, returning a most specific
$\mathcal{Q}$-separator (and so the unique one, if any).

Thus, we can focus on algorithms deciding the existence of a (unique most
specific/general) separator and constructing it. In the next theorem, we
compute not just a random input separator, but a longest/shortest one. As
strengthening/weakening frontiers contain queries that are not shorter/longer
than the input, the procedure above will compute a longest most
specific/shortest most general separator.

######  Theorem 23.

Let $E=(E^{+},E^{-})$, $\sigma=\mathsf{sig}(E)$, $t_{+}$/$t_{-}$ be the
maximum timestamp in $E^{+}$/$E^{-}$, $c_{+}=|E^{+}|$, $c_{-}=|E^{-}|$, and
$\mathcal{Q}\in\\{\mathcal{Q}_{p}[\Diamond],\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]\\}$.
The following can be done in time $O(t_{+}^{c_{+}}t_{-}^{c_{-}})$:

  * $(a)$

deciding whether $\mathsf{s}(E,\mathcal{Q})\neq\emptyset$;

  * $(b)$

computing a longest/shortest separator in $\mathsf{s}(E,\mathcal{Q})$;

  * $(c)$

deciding the existence of a unique most specific $\mathcal{Q}$-separator and a
unique most general $\mathcal{Q}_{p}[\Diamond]$-separator, and constructing
such a separator.

For bounded $c_{+}$ and $c_{-}$, problem $(a)$ is in NL.

###### Proof.

We only sketch the construction for $\mathcal{Q}=\mathcal{Q}_{p}[\Diamond]$.

$(a)$ First, we define a directed labelled rooted graph $\mathfrak{P}$ whose
paths from the root represent $\mathcal{Q}_{p}[\Diamond]$-queries with
positive examples $E^{+}=\\{\mathcal{D}_{1},\dots,\mathcal{D}_{c_{+}}\\}$. Its
nodes are vectors $(n_{1},\dots,n_{c_{+}})$ with $0\leq
n_{i}\leq\max\mathcal{D}_{i}$, which are labelled by the sets
$\\{A\in\sigma\mid A(n_{i})\in\mathcal{D}_{i}\text{ for all $i$}\\}$, and the
edges are
$(n_{1},\dots,n_{c_{+}})\to(n_{1}^{\prime},\dots,n^{\prime}_{c_{+}})$ with
$n_{i}<n_{i}^{\prime}$ for all $i$. The _root_ of $\mathfrak{P}$ is
$\bar{0}=(0,\dots,0)$. To illustrate, let $E=(E^{+},E^{-})$, where
$E^{+}=\\{\mathcal{D}_{1}^{+},\mathcal{D}_{2}^{+}\\}$,
$E^{-}=\\{\mathcal{D}_{1}^{-},\mathcal{D}_{2}^{-},\mathcal{D}_{3}^{-}\\}$,

$\displaystyle\mathcal{D}_{1}^{+}=\\{A(0),C(1),D(1),B(2)\\},$
$\displaystyle\hskip 105.2751pt\mathcal{D}_{2}^{+}=\\{A(0),C(1),B(2),D(2)\\},$
$\displaystyle\mathcal{D}_{1}^{-}=\\{A(0),C(1)\\},\
\mathcal{D}_{2}^{-}=\\{A(0),D(1)\\},\ \mathcal{D}_{3}^{-}=\\{B(0)\\}.$

Graph $\mathfrak{P}$ is shown on the left-hand side of the picture below:

$(0,0)$$\\{A\\}$$(1,1)$$\\{C\\}$$(2,1)$$\emptyset$$(1,2)$$\\{D\\}$$(2,2)$$\\{B\\}$$\mathfrak{P}$
$(0,0,\infty)$$\\{A\\}$$(1,1,\infty)$$\emptyset$$(1,\infty,\infty)$$\\{C\\}$$(\infty,1,\infty)$$\\{D\\}$$(\infty,\infty,\infty)$$\\{A,B,C,D\\}$$\mathfrak{N}$

Each path starting at $\bar{0}$ gives rise to a
$\mathcal{Q}^{\sigma}_{p}[\Diamond]$-query with positive examples in $E^{+}$:
e.g., $(0,0)\to(1,1)\to(2,2)$ gives rise to the query
$A\land\Diamond(C\land\Diamond B)$.

Next, define another graph $\mathfrak{N}$ for
$E^{-}=\\{\mathcal{D}_{1},\dots,\mathcal{D}_{c_{-}}\\}$. Its nodes are
$(n_{1},\dots,n_{c_{-}})$, where
$n_{i}\in[0,\max\mathcal{D}_{i}]\cup\\{\infty\\}$, including
$\bar{\infty}=(\infty,\dots,\infty)$, which is labelled by $\sigma$. The label
of $(n_{1},\dots,n_{c_{-}})$ is $\\{A\mid A(n_{i})\in\mathcal{D}_{i},\text{
for all }n_{i}\neq\infty\\}$. The edges are defined in the same way as for
$\mathfrak{P}$, with $n_{i}<\infty$, for any $n_{i}$. The root of
$\mathfrak{N}$ is $(n_{1},\dots,n_{l})$, where $n_{i}=0$ if $\\{A(0)\mid
A(0)\in\mathcal{D},\text{ for all }\mathcal{D}\in
E^{+}\\}\subseteq\mathcal{D}_{i}$ and $n_{i}=\infty$ otherwise (see the
picture above). Let $\boldsymbol{q}$ be a
$\mathcal{Q}^{\sigma}_{p}[\Diamond]$-query of the form (1) with $\rho_{0}$
contained in the root’s label. Then all $\mathcal{D}_{i}\in E^{-}$ are
negative examples for $\boldsymbol{q}$ iff every path starting at the root and
having labels $\rho^{\prime}_{0},\dots,\rho^{\prime}_{n}$ with
$\rho^{\prime}_{i}\supseteq\rho_{i}$, for all $i\leq n$, comes through node
$\bar{\infty}$. In our example, every such path for
$\boldsymbol{q}=A\land\Diamond B$ and
$\boldsymbol{q}=A\land\Diamond(C\land\Diamond B)$ involves $\bar{\infty}$.
However, this is not the case for $\boldsymbol{q}=A\land\Diamond C$.

Consider now a graph $\mathfrak{P}\otimes\mathfrak{N}$ with nodes
$(\boldsymbol{n},\boldsymbol{m})$, where $\boldsymbol{n}$ is a node in
$\mathfrak{P}$ and $\boldsymbol{m}$ a node in $\mathfrak{N}$ with
$\boldsymbol{l}(\boldsymbol{n})\subseteq\boldsymbol{l}(\boldsymbol{m})$, for
the labels $\boldsymbol{l}(\boldsymbol{n})$ and
$\boldsymbol{l}(\boldsymbol{m})$ of $\boldsymbol{n}$ and $\boldsymbol{m}$. We
have an edge
$(\boldsymbol{n},\boldsymbol{m})\to(\boldsymbol{n}^{\prime},\boldsymbol{m}^{\prime})$
in $\mathfrak{P}\otimes\mathfrak{N}$ iff
$\boldsymbol{n}\to\boldsymbol{n}^{\prime}$ in $\mathfrak{P}$,
$\boldsymbol{m}\to\boldsymbol{m}^{\prime}$ in $\mathfrak{N}$, and
$\mathfrak{P}\otimes\mathfrak{N}$ has no
$(\boldsymbol{n}^{\prime},\boldsymbol{m}^{\prime\prime})$ with
$\boldsymbol{m}\to\boldsymbol{m}^{\prime\prime}$,
$\boldsymbol{m}^{\prime\prime}_{i}<\boldsymbol{m}^{\prime}_{i}$ and
$\boldsymbol{m}_{i}^{\prime\prime}\neq\infty$, for some $i$,
$\boldsymbol{m}_{i}$ being the $i$th coordinate of $\boldsymbol{m}$. One can
see that, for any $(\boldsymbol{n},\boldsymbol{m})$ in
$\mathfrak{P}\times\mathfrak{N}$ and $\boldsymbol{n}^{\prime}$ in
$\mathfrak{P}$, there exists at most one edge
$(\boldsymbol{n},\boldsymbol{m})\to(\boldsymbol{n}^{\prime},\boldsymbol{m}^{\prime})$.
The root of $\mathfrak{P}\times\mathfrak{N}$ comprises the roots of
$\mathfrak{P}$ and $\mathfrak{N}$. In our example, the edges from the root
$(\bar{0},(0,0,\infty))$ of $\mathfrak{P}\otimes\mathfrak{N}$ lead to
$((1,2),(\infty,1,\infty))$, $((2,1),(1,1,\infty))$,
$((1,1),(1,\infty,\infty))$ and $((2,2),\bar{\infty})$. Given a path

$\pi=(\bar{0}=\boldsymbol{n}_{0},\boldsymbol{m}_{0}),\dots,(\boldsymbol{n}_{n},\boldsymbol{m}_{n})$
(2)

let $\boldsymbol{q}_{\pi}$ be the $\mathcal{Q}_{p}[\Diamond]$-query of the
form (1) with $\rho_{i}=\boldsymbol{l}(\boldsymbol{n}_{i})$ (note that
$\boldsymbol{q}_{\pi}$ is not necessarily in normal form). We call $\pi$ a
_separating path_ for $E$ if $\boldsymbol{l}(\boldsymbol{n}_{n})\neq\emptyset$
and $\boldsymbol{m}_{n}=\infty$.

######  Lemma 24.

$\mathsf{s}(E,\mathcal{Q})\neq\emptyset$ iff $\mathfrak{P}\otimes\mathfrak{N}$
contains a separating path $\pi$, with $\boldsymbol{q}_{\pi}$ separating $E$.

In our running example, $\mathfrak{P}\otimes\mathfrak{N}$ has two _separating
paths_ : $\pi_{1}=(\bar{0},(0,0,\infty)),\,((2,2),\bar{\infty})$ and
$\pi_{2}=(\bar{0},(0,0,\infty)),$
$((1,1),(1,\infty,\infty)),\,((2,2),\bar{\infty})$, which give rise to the
separators $\boldsymbol{q}_{\pi_{1}}=A\land\Diamond B$ and
$\boldsymbol{q}_{\pi_{2}}=A\land\Diamond(C\land\Diamond B)$.

The existence of a separating path in $\mathfrak{P}\otimes\mathfrak{N}$ can be
checked in time $O(t_{+}^{c_{+}}t_{-}^{c_{-}})$. If $c_{+}$ and $c_{-}$ are
bounded, given $(\boldsymbol{n},\boldsymbol{m})$ and
$(\boldsymbol{n}^{\prime},\boldsymbol{m}^{\prime})$, we can check in logspace
whether $(\boldsymbol{n},\boldsymbol{m})$ is the root of
$\mathfrak{P}\otimes\mathfrak{N}$ and
$(\boldsymbol{n},\boldsymbol{m})\to(\boldsymbol{n}^{\prime},\boldsymbol{m}^{\prime})$,
and so the existence of a separating path can be decided in NL.

The proof of point $(b)$ relies on the following observation:

######  Lemma 25.

If $\boldsymbol{q}$ of the form (1) separates $E$, then there is a separating
path of the form (2) with
$\rho_{i}\subseteq\boldsymbol{l}(\boldsymbol{n}_{i})$, for all $i\leq n$.

It follows that the length of a longest/shortest separator for $E$ coincides
with the length of a longest/shortest separating path in
$\mathfrak{P}\otimes\mathfrak{N}$, which can be found in polytime.

The proof of point $(c)$ is based on the following criterion:

######  Lemma 26.

A $\mathcal{Q}_{p}[\Diamond]$-query $\boldsymbol{q}$ is a unique most specific
$\mathcal{Q}_{p}[\Diamond]$-separator for $E$ iff there is a separating path
$\pi$ such that $\boldsymbol{q}=\boldsymbol{q}_{\pi}$ and
$\boldsymbol{q}_{\pi}\models\boldsymbol{q}_{\nu}$, for every separating path
$\nu$.

In our example, $\boldsymbol{q}_{\pi_{2}}$ is a unique most specific
separator. We show that the criterion of Lemma 26 can be checked in polytime
in $\mathfrak{P}\times\mathfrak{N}$. For unique most general separators, the
seemingly obvious inversion of
$\boldsymbol{q}_{\pi}\models\boldsymbol{q}_{\nu}$ does not give a criterion,
and a different type of graph is required. ∎

Finally, we show how Theorem 23 can be used to check the existence of and
construct unique most general separators in $\mathcal{Q}[\Diamond]$ (the case
of unique most specific ones is trivial).

######  Theorem 27.

An example set $E=(E^{+},E^{-})$ has a unique most general separator in
$\mathcal{Q}[\Diamond]$ iff $\boldsymbol{q}=\bigwedge_{\mathcal{D}\in
S}\boldsymbol{q}_{\mathcal{D}}$ separates $E$, where $S$ is the set of
$\mathcal{D}\in E^{-}$ such that $(E^{+},\\{\mathcal{D}\\})$ has a unique most
general separator, $\boldsymbol{q}_{\mathcal{D}}$, in
$\mathcal{Q}_{p}[\Diamond]$. In this case, $\boldsymbol{q}$ is a unique most
general separator of $E$ in $\mathcal{Q}[\Diamond]$.

##  8 Conclusions

We have conducted a comprehensive complexity analysis of extremal separators
in the spaces $\mathsf{s}(E,\mathcal{Q})$ with $\mathcal{Q}$ ranging from
various classes of temporal path
${\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond$-queries to
arbitrary $\Diamond$-queries. For arbitrary
${\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond$-queries, we
only know more or less straightforward upper bounds such as $\Pi_{2}^{p}$ for
(unique) most general separator verification and $\Sigma_{3}^{p}$ for unique
most general separator existence. Establishing tight bounds remains a
challenging open problem, which requires a deeper understanding of query
containment for these queries.

We also plan to analyse the shortest and longest separators. For instance, we
show in the appendix that verifying such separators in
$\mathsf{s}(E,\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond])$
is coNP-complete—harder than verifying most specific/general ones. An
empirical evaluation of our algorithms and more expressive query languages
(say, with non-strict $\Diamond$ and ‘until’) are left for future work.

## References

  * Abboud et al. [2015] A. Abboud, A. Backurs, and V. V. Williams.  Tight hardness results for LCS and other sequence similarity measures.  In FOCS, pages 59–78. IEEE Computer Society, 2015.
  * Alexe et al. [2011] B. Alexe, B. ten Cate, Ph. Kolaitis, and W. Ch. Tan.  Characterizing schema mappings via data examples.  ACM Trans. Database Syst., 36(4):23, 2011.
  * Arenas et al. [2016] M. Arenas, G. I. Diaz, and E. Kostylev.  Reverse engineering SPARQL queries.  In Proc. of WWW, pages 239–249, 2016.
  * Arora and Barak [2009] S. Arora and B. Barak.  Computational Complexity - A Modern Approach.  Cambridge University Press, 2009.
  * Artale et al. [2021] A. Artale, R. Kontchakov, A. Kovtunova, V. Ryzhikov, F. Wolter, and M. Zakharyaschev.  First-order rewritability of ontology-mediated queries in linear temporal logic.  Artif. Intell., 299:103536, 2021.
  * Baader et al. [2015] F. Baader, S. Borgwardt, and M. Lippmann.  Temporal query entailment in the description logic $\mathcal{SHQ}$.  J. Web Semant., 33:71–93, 2015.
  * Barceló and Romero [2017] P. Barceló and M. Romero.  The complexity of reverse engineering problems for conjunctive queries.  In Proc. of ICDT, pages 7:1–7:17, 2017.
  * Barceló et al. [2021] P. Barceló, A. Baumgartner, V. Dalmau, and B. Kimelfeld.  Regularizing conjunctive features for classification.  J. Comput. Syst. Sci., 119:97–124, 2021.
  * Bergroth et al. [2000] L. Bergroth, H. Hakonen, and T. Raita.  A survey of longest common subsequence algorithms.  In Proc. of SPIRE, pages 39–48, 2000.
  * Blass and Gurevich [1982] A. Blass and Y. Gurevich.  On the unique satisfiability problem.  Inf. Control., 55(1-3):80–88, 1982.
  * Blin et al. [2012] G. Blin, L. Bulteau, M. Jiang, P. Tejada, and S. Vialette.  Hardness of longest common subsequence for sequences with bounded run-lengths.  In Proc. of CPM, volume 7354 of Lecture Notes in Computer Science, pages 138–148. Springer, 2012.
  * Blum et al. [2021] Ch. Blum, M. Djukanovic, A. Santini, H. Jiang, Chu-Min Li, F. Manyà, and G. Raidl.  Solving longest common subsequence problems via a transformation to the maximum clique problem.  Comput. Oper. Res., 125:105089, 2021.
  * Borgwardt et al. [2015] S. Borgwardt, M. Lippmann, and V. Thost.  Temporalizing rewritable query languages over knowledge bases.  J. Web Semant., 33:50–70, 2015.
  * Camacho and McIlraith [2019] A. Camacho and Sh. McIlraith.  Learning interpretable models expressed in linear temporal logic.  In Proc. of ICAPS 2018, pages 621–630. AAAI Press, 2019.
  * Chandra and Merlin [1977] A. Chandra and P. Merlin.  Optimal implementation of conjunctive queries in relational data bases.  In Conference Record of the Ninth Annual ACM Symposium on Theory of Computing, pages 77–90. ACM, 1977.
  * Chomicki and Toman [2018] J. Chomicki and D. Toman.  Temporal logic in database query languages.  In Ling Liu and M. Tamer Özsu, editors, Encyclopedia of Database Systems, Second Edition. Springer, 2018.
  * Chowdhury et al. [2010] R. A. Chowdhury, Hai-Son Le, and V. Ramachandran.  Cache-oblivious dynamic programming for bioinformatics.  IEEE/ACM Trans. on Computational Biology and Bioinformatics, 7(3):495–510, 2010.
  * Cima et al. [2021] G. Cima, F. Croce, and M. Lenzerini.  Query definability and its approximations in ontology-based data management.  In Proc. of CIKM’21, pages 271–280. ACM, 2021.
  * Cohen and Weiss [2016] S. Cohen and Y. Y. Weiss.  The complexity of learning tree patterns from example graphs.  ACM Trans. Database Syst., 41(2):14:1–14:44, 2016.
  * Crochemore et al. [2007] M. Crochemore, Ch. Hancart, and T. Lecroq.  Algorithms on strings.  Cambridge University Press, 2007.
  * Cropper et al. [2022] A. Cropper, S. Dumancic, R. Evans, and S. H. Muggleton.  Inductive logic programming at 30.  Mach. Learn., 111(1):147–172, 2022.
  * Deutch and Gilad [2019] D. Deutch and A. Gilad.  Reverse-engineering conjunctive queries from provenance examples.  In Proc. of EDBT, pages 277–288, 2019.
  * Fijalkow and Lagarde [2021] N. Fijalkow and G. Lagarde.  The complexity of learning linear temporal formulas from examples.  In Proc. of the 15th Int. Conf. on Grammatical Inference, volume 153 of Proc. of Machine Learning Research, pages 237–250. PMLR, 2021.
  * Fortin et al. [2022] M. Fortin, B. Konev, V. Ryzhikov, Y. Savateev, F. Wolter, and M. Zakharyaschev.  Unique characterisability and learnability of temporal instance queries.  In Proc. of KR, 2022.
  * Fortin et al. [2023] M. Fortin, B. Konev, V. Ryzhikov, Y. Savateev, F. Wolter, and M. Zakharyaschev.  Reverse engineering of temporal queries mediated by LTL ontologies.  In Proc. of IJCAI, pages 3230–3238. ijcai.org, 2023.
  * Fraser [1996] C. Fraser.  Consistent subsequences and supersequences.  Theor. Comput. Sci., 165(2):233–246, 1996.
  * Funk et al. [2019] M. Funk, J.-Ch. Jung, C. Lutz, H. Pulcini, and F. Wolter.  Learning description logic concepts: When can positive and negative examples be separated?  In Proc. of IJCAI, pages 1682–1688, 2019.
  * Gutiérrez-Basulto et al. [2018] V. Gutiérrez-Basulto, J. Ch. Jung, and L. Sabellek.  Reverse engineering queries in ontology-enriched systems: The case of expressive Horn description logic ontologies.  In Proc. of IJCAI-ECAI, 2018.
  * Jung et al. [2022] J. Ch. Jung, C. Lutz, H. Pulcini, and F. Wolter.  Logical separability of labeled data examples under ontologies.  Artif. Intell., 313:103785, 2022.
  * Kalashnikov et al. [2018] D. Kalashnikov, L. Lakshmanan, and D. Srivastava.  Fastqre: Fast query reverse engineering.  In Proc. of SIGMOD, pages 337–350, 2018.
  * Kimelfeld and Ré [2018] B. Kimelfeld and Ch. Ré.  A relational framework for classifier engineering.  ACM Trans. Database Syst., 43(3):11:1–11:36, 2018.
  * Lemieux et al. [2015] C. Lemieux, D. Park, and I. Beschastnikh.  General LTL specification mining (T).  In Proc. of ASE, pages 81–92. IEEE, 2015.
  * Maier [1978] D. Maier.  The complexity of some problems on subsequences and supersequences.  J. ACM, 25(2):322–336, 1978.
  * Martins [2019] D. Martins.  Reverse engineering database queries from examples: State-of-the-art, challenges, and research opportunities.  Inf. Syst., 83:89–100, 2019.
  * Mitchell [1982] T. Mitchell.  Generalization as search.  Artif. Intell., 18(2):203–226, 1982.
  * Neider and Gavran [2018] D. Neider and I. Gavran.  Learning linear temporal properties.  In Proc. of FMCAD 2018, pages 1–10. IEEE, 2018.
  * Ortiz [2019] M. Ortiz.  Ontology-mediated queries from examples: a glimpse at the DL-Lite case.  In Proc. of GCAI, pages 1–14, 2019.
  * Raha et al. [2022] R. Raha, R. Roy, N. Fijalkow, and D. Neider.  Scalable anytime algorithms for learning fragments of linear temporal logic.  In Proc. of TACAS, volume 13243 of Lecture Notes in Computer Science, pages 263–280. Springer, 2022.
  * Sarker et al. [2017] Md. K. Sarker, Ning Xie, D. Doran, M. Raymer, and P. Hitzler.  Explaining trained neural networks with semantic web technologies: First steps.  In Proc. of NeSy, 2017.
  * Staworko and Wieczorek [2012] S. Staworko and P. Wieczorek.  Learning twig and path queries.  In Proc. of ICDT, pages 140–154, 2012.
  * ten Cate and Dalmau [2015] B. ten Cate and V. Dalmau.  The product homomorphism problem and applications.  In Proc. of ICDT, pages 161–176, 2015.
  * ten Cate et al. [2023] B. ten Cate, V. Dalmau, M. Funk, and C. Lutz.  Extremal fitting problems for conjunctive queries.  In Proc. of PODS, pages 89–98. ACM, 2023.
  * Weiss and Cohen [2017] Y. Y. Weiss and S. Cohen.  Reverse engineering SPJ-queries from examples.  In Proc. of PODS, pages 151–166, 2017.
  * Zhang et al. [2013] M. Zhang, H. Elmeleegy, C. M. Procopiuc, and D. Srivastava.  Reverse engineering complex join queries.  In Proc. of SIGMOD, pages 809–820, 2013.

Appendix: Proofs

##  Appendix A Proofs for Section 3

We assume that queries $\boldsymbol{q}$ are in normal form. Recall that
$[n]=\\{0,\ldots,n\\}$. We start by introducing a helpful tool for checking
whether $\mathcal{D},0\models\boldsymbol{q}$. Let $\boldsymbol{q}$ be a path
${\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond$-query of the
form (1), that is,

$\boldsymbol{q}=\rho_{0}\land{\boldsymbol{o}}_{1}(\rho_{1}\land{\boldsymbol{o}}_{2}(\rho_{2}\land\dots\land{\boldsymbol{o}}_{n}\rho_{n})),$

where
${\boldsymbol{o}}_{i}\in\\{{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}},\Diamond\\}$
and $\rho_{i}$ is a conjunction of atoms. A _satisfying function_ $f$ for
$\boldsymbol{q}$ into a data instance $\mathcal{D}$ maps $[n]$ to
$[\max\mathcal{D}]$ such that

  * •

$f(0)=0$;

  * •

$\rho_{i}\subseteq\mathcal{D}_{f(i)}:=\\{A\mid A(f(i))\in\mathcal{D}\\}$;

  * •

$f(i)<f(i+1)$;

  * •

$f(i+1)=f(i)+1$ if
${\boldsymbol{o}}_{i+1}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$.

It is easy to show that $\mathcal{D},0\models\boldsymbol{q}$ iff there exists
a satisfying function for $\boldsymbol{q}$ into $\mathcal{D}$.

$\displaystyle\boldsymbol{q}^{\prime}=\rho_{0}^{\prime}\wedge{\boldsymbol{o}}_{1}^{\prime}(\rho_{1}^{\prime}\wedge\cdots\wedge{\boldsymbol{o}}_{m}^{\prime}(\rho_{m}^{\prime})).$
(3)

A function $g:[m]\rightarrow[n]$ is a _containment witness_ for
$\boldsymbol{q},\boldsymbol{q}^{\prime}$ if the following conditions holds:

  * •

$\rho_{i}^{\prime}\subseteq\rho_{g(i)}$;

  * •

$g(0)=0$;

  * •

$g(i)<g(i+1)$;

  * •

if
${\boldsymbol{o}}_{i+1}^{\prime}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$,
then
${\boldsymbol{o}}_{g(i+1)}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$
and $g(i+1)=g(i)+1$.

We can now state Lemma 3 as follows.

######  Lemma 28.

$\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ iff there is a containment
witness for $\boldsymbol{q},\boldsymbol{q}^{\prime}$.

###### Proof.

It is easy to see that if there is a containment witness for
$\boldsymbol{q},\boldsymbol{q}^{\prime}$ then
$\boldsymbol{q}\models\boldsymbol{q}^{\prime}$. We prove the converse
direction.

Let $\sigma=\mathsf{sig}(\boldsymbol{q})$. The proof is by induction on the
temporal depth of $\boldsymbol{q}^{\prime}$. If
$\mathit{tdp}(\boldsymbol{q}^{\prime})=0$, the claim is trivial.

Assume $\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ are given and the
statement has been shown for all $\boldsymbol{q}^{\prime\prime}$ with
$\mathit{tdp}(\boldsymbol{q}^{\prime\prime})<\mathit{tdp}(\boldsymbol{q}^{\prime})$.

Assume first that $\boldsymbol{q}^{\prime}$ starts with a nonempty sequence of
$\bigcirc$. Then let $k>0$ be maximal such that
${\boldsymbol{o}}_{1}^{\prime}=\cdots={\boldsymbol{o}}_{k}^{\prime}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$.
Then $\rho_{k}^{\prime}\not=\top$ (by normal form) and if $m>k$, then
${\boldsymbol{o}}_{k+1}^{\prime}=\Diamond$.

Let $r$ be minimal such that

$\rho_{0}\wedge{\boldsymbol{o}}_{1}(\rho_{1}\wedge\cdots\wedge{\boldsymbol{o}}_{r}\rho_{r}))\models\rho_{0}^{\prime}\wedge{\boldsymbol{o}}_{1}^{\prime}(\rho_{1}^{\prime}\wedge\cdots\wedge{\boldsymbol{o}}_{k}^{\prime}\rho_{k}^{\prime}))$

_Claim 1._ For all $i\leq k$,
${\boldsymbol{o}}_{i}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$
and $\rho_{i}\supseteq\rho_{i}^{\prime}$. Hence $r=k$.

To prove Claim 1 observe that if there is $i\leq k$ with
${\boldsymbol{o}}_{i}=\Diamond$, then we have for

$\mathcal{D}=\rho_{0}\ldots\rho_{i-1}\emptyset^{m}\rho_{i}\ldots\rho_{n}$

$\mathcal{D},0\models\boldsymbol{q}$ and
$\mathcal{D},0\not\models\boldsymbol{q}^{\prime}$, a contradiction. If there
is $i\leq k$ with $\rho_{i}\not\supseteq\rho_{i}^{\prime}$, then we have for

$\mathcal{D}=\rho_{0}\ldots\rho_{n}$

$\mathcal{D},0\models\boldsymbol{q}$ and
$\mathcal{D},0\not\models\boldsymbol{q}^{\prime}$, again a contradiction. This
finishes the proof of Claim 1.

Next observe that if follows from
$\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ that

$\delta\models\delta^{\prime}$

for
$\delta={\boldsymbol{o}}_{k+1}(\rho_{k+1}\wedge\cdots\wedge{\boldsymbol{o}}_{n}\rho_{n}))$
and
$\delta^{\prime}={\boldsymbol{o}}_{k+1}^{\prime}(\rho_{k+1}^{\prime}\wedge\cdots{\boldsymbol{o}}_{m}^{\prime}\rho_{m}^{\prime}))$.
As

$\mathit{tdp}(\delta^{\prime})<\mathit{tdp}(\boldsymbol{q}^{\prime})$

we can apply the IH to $\delta,\delta^{\prime}$ and have a containment witness
$g^{\prime}$ for $\delta,\delta^{\prime}$. Define $g$ by setting $g(i)=i$ for
all $i\leq k$ and $g(k+j)=g^{\prime}(j)+k$ for all $j$ with $1\leq j\leq m-k$.
Then $g$ is a containment witness for
$\boldsymbol{q},\boldsymbol{q}^{\prime}$.

Assume now that $\boldsymbol{q}^{\prime}$ does not start with $\bigcirc$.
Assume first there is a minimal initial subquery

$\delta^{\prime}=\rho_{0}^{\prime}\wedge{\boldsymbol{o}}_{1}^{\prime}(\rho_{1}^{\prime}\wedge\cdots\wedge{\boldsymbol{o}}_{k}^{\prime}\rho_{k}^{\prime}))$

of $\boldsymbol{q}^{\prime}$ ending with $\rho_{k}^{\prime}\not=\top$ and,
moreover, ${\boldsymbol{o}}_{k+1}^{\prime}=\Diamond$ and $k>0$. Let

$\delta=\rho_{0}\wedge{\boldsymbol{o}}_{1}(\rho_{1}\wedge\cdots\wedge\rho_{r}))$

be the minimal initial subquery of $\boldsymbol{q}$ such that
$\delta\models\delta^{\prime}$. As
$\mathit{tdp}(\delta^{\prime})<\mathit{tdp}(\boldsymbol{q}^{\prime})$, by IH
we have a containment witness $g_{0}$ for $\delta,\delta^{\prime}$. As
$\rho_{k}^{\prime}\not=\top$ and $r$ is minimal we have $g_{0}(k)=r$. By IH
the claim also holds for
$\gamma^{\prime}={\boldsymbol{o}}_{k+1}^{\prime}(\rho_{k+1}^{\prime}\wedge\cdots\wedge{\boldsymbol{o}}_{m}^{\prime}\rho_{m}^{\prime}))$
and
$\gamma={\boldsymbol{o}}_{r+1}(\rho_{r+1}\wedge\cdots\wedge{\boldsymbol{o}}_{n}\rho_{n}))$.
Hence we obtain a containment witness $g_{1}$ for $\gamma,\gamma^{\prime}$.
Then we obtain a containment witness for
$\boldsymbol{q},\boldsymbol{q}^{\prime}$ by concatenating $g_{0}$ and $g_{1}$.

Finally assume there is no $\rho_{k}^{\prime}\not=\top$ with
$op_{k+1}^{\prime}=\Diamond$ and $k>0$. Then, by normal form,
$\boldsymbol{q}^{\prime}$ takes the form

$\rho_{0}^{\prime}\wedge\Diamond^{k}(\rho_{k}^{\prime}\wedge{\boldsymbol{o}}_{k+1}^{\prime}\rho_{k+1}^{\prime}\cdots\wedge{\boldsymbol{o}}_{m}^{\prime}\rho_{m}^{\prime}))$

with $k>0$, $\rho_{k}^{\prime}\not=\top$, and
${\boldsymbol{o}}_{k+1}^{\prime}=\cdots={\boldsymbol{o}}_{m}^{\prime}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$.

We show there exists $j\geq k$ such that
${\boldsymbol{o}}_{j+1}=\cdots={\boldsymbol{o}}_{j+m-k}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$
and $\rho_{j+\ell}\supseteq\rho_{k+\ell}^{\prime}$ for all $\ell$ with
$0\leq\ell\leq m-k$. Clearly then there is a containment witness $g$ for
$\boldsymbol{q},\boldsymbol{q}^{\prime}$.

To show our claim, suppose no such $j$ exists. Then take the data instance

$\mathcal{D}=\rho_{0}w_{1}\rho_{1}\cdots w_{n}\rho_{n}$

where $w_{i}$ is the empty word if
${\boldsymbol{o}}_{i}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$
and $w_{i}=\emptyset^{m}$ if ${\boldsymbol{o}}_{i}=\Diamond$. Then we have
$\mathcal{D},0\models\boldsymbol{q}$ but
$\mathcal{D},0\not\models\boldsymbol{q}^{\prime}$, a contradiction. ∎

We consider $\mathcal{Q}[\Diamond]$. We assume that
$\boldsymbol{q}\in\mathcal{Q}[\Diamond]$ takes the from

$\rho\wedge\boldsymbol{q}_{1}\wedge\cdots\wedge\boldsymbol{q}_{n}$

where $\rho$ is a conjunction of atoms and each $\boldsymbol{q}_{i}$ is in
$\mathcal{Q}_{p}[\Diamond]$ and starts with $\Diamond$.

Lemma 4. _If
$\boldsymbol{q}=\rho\wedge\boldsymbol{q}_{1}\wedge\cdots\wedge\boldsymbol{q}_{n}\in\mathcal{Q}[\Diamond]$
is in normal form, $\boldsymbol{q}^{\prime}\in\mathcal{Q}_{p}[\Diamond]$ and
$\boldsymbol{q}\models\boldsymbol{q}^{\prime}$, then there is
$\boldsymbol{q}_{i}$, $1\leq i\leq n$, with
$\rho\wedge\boldsymbol{q}_{i}\models\boldsymbol{q}^{\prime}$._

###### Proof.

Assume

$\boldsymbol{q}_{i}=\Diamond(\rho^{1}_{i}\wedge\cdots\rho^{n_{i}}_{i}))$

for $1\leq i\leq n$,

$\boldsymbol{q}^{\prime}=\rho^{0}\wedge\Diamond(\rho^{1}\wedge\cdots\wedge\Diamond\rho^{m})),$

and $\boldsymbol{q}\models\boldsymbol{q}^{\prime}$. Note that
$\rho\supseteq\rho^{0}$ as otherwise
$\boldsymbol{q}\not\models\boldsymbol{q}^{\prime}$. We define functions

$f_{i}:\\{1,\ldots,m\\}\rightarrow\\{1,\ldots,n_{i}\\}\cup\\{\infty\\}$

for $1\leq i\leq n$. The definition is by induction starting from $1$.

Set $f_{i}(1)=j$ if $j$ is minimal such that $\rho_{i}^{j}\supseteq\rho^{1}$
and $f_{i}(1)=\infty$ if no $j$ with $\rho_{i}^{j}\supseteq\rho^{1}$ exists.

Inductively, if $f_{i}(\ell)=\infty$, then $f_{i}(\ell+1)=\infty$. If
$f_{i}(\ell)<\infty$, then set $f_{i}(\ell+1)=j$ if $j$ is minimal such that

  * •

$j>f_{i}(\ell)$;

  * •

$\rho_{i}^{j}\supseteq\rho^{\ell+1}$

and $f_{i}(\ell+1)=\infty$ if no $j>f_{i}(\ell)$ such that
$\rho_{i}^{j}\supseteq\rho^{\ell+1}$ exists.

Observe that if there exists $i\leq n$ such that $f_{i}(m)<\infty$, then
$\rho\wedge\boldsymbol{q}_{i}\models\boldsymbol{q}^{\prime}$, as required.
Hence it remains to show that there exists such an $i\leq n$. For a proof by
contradiction, assume there is no such $i\leq n$. We derive a contraction by
proving that $\boldsymbol{q}\not\models\boldsymbol{q}^{\prime}$. Let
$m^{\prime}\leq m$ be minimal such that $f_{i}(m^{\prime})=\infty$ for all
$i\leq n$. Define a data instance $\mathcal{D}_{1}$ as

$\mathcal{D}_{1}=\rho\rho_{1}^{1}\cdots\rho_{1}^{k_{1}}\cdots\rho_{n}^{1}\cdots\rho_{n}^{k_{n}},$

where $k_{i}=\min\\{n_{i},f_{i}(1)-1\\}$ for $1\leq i\leq n$ (we set
$\infty-1=\infty$). If $m^{\prime}=1$, then
$\mathcal{D}_{1},0\models\boldsymbol{q}$ and
$\mathcal{D}_{1},0\not\models\boldsymbol{q}^{\prime}$ since
$\mathcal{D}_{1},0\not\models\Diamond\rho^{1}$, and we are done. Otherwise let

$\delta_{1}=\bigcup_{1\leq i\leq n,f_{i}(1)<\infty}\rho_{i}^{f_{i}(1)}$

We continue in this way for $\ell=2,3,\ldots,m^{\prime}$ as follows. First
define for $2\leq\ell\leq m^{\prime}$:

$\mathcal{D}_{\ell}=\rho_{1}^{f_{1}(\ell)+1}\cdots\rho_{1}^{k_{\ell,1}}\cdots\rho_{n}^{f_{n}(\ell)+1}\cdots\rho_{n}^{k_{\ell,n}},$

where $k_{\ell,i}=\min\\{n_{i},f_{i}(\ell+1)-1\\}$ for $1\leq i\leq n$ (note
that $\rho_{i}^{f_{i}(\ell)+1}\cdots\rho_{i}^{k_{\ell,i}}$ is empty if
$f_{i}(\ell)+1>n_{i}$). Then let for $2\leq\ell<m^{\prime}$:

$\delta_{\ell}=\bigcup_{1\leq i\leq
n,f_{i}(\ell)<\infty}\rho_{i}^{f_{i}(\ell)}$

and set

$\mathcal{D}=\mathcal{D}_{1}\delta_{1}\mathcal{D}_{2}\delta_{2}\cdots\delta_{m^{\prime}-1}\mathcal{D}_{m^{\prime}}$

It is straightforward to show that $\mathcal{D},0\models\boldsymbol{q}$ and
$\mathcal{D},0\not\models\boldsymbol{q}^{\prime}$. Hence
$\boldsymbol{q}\not\models\boldsymbol{q}^{\prime}$ and we have derived a
contradiction. ∎

##  Appendix B Proofs for Section 4

We prove the complexity results for separability that are stated in this
section for $\mathcal{Q}_{\textit{in}}$.

######  Theorem 29.

(1) For $\mathcal{Q}_{\textit{in}}$, separator existence is NP-complete. This
also holds if $|E^{-}|$ and $\mathsf{sig}(E)$ are bounded.

(2) If $|E^{+}|$ is bounded then $\mathcal{Q}_{\textit{in}}$-separator
existence is in P.

(3) For example data instances $E=(E^{+},E^{-})$ that are sequences, the
existence of a separator that is a sequence query in
$\mathcal{Q}_{\textit{in}}$ is in P.

###### Proof.

(1) The NP-upper bound follows from the fact that given $E$ one can guess a
separator of polynomial size in $\mathcal{Q}_{\textit{in}}$ and check in
polytime that is separates. The lower bound follows directly from the proof of
Theorem 21 (b) given later in this appendix.

(2) Assume $E^{+}=\\{\mathcal{D}_{1},\ldots,\mathcal{D}_{n}\\}$. Let
$m_{i}=\max\mathcal{D}_{i}$ and $m=\max\\{m_{i}\mid 1\leq i\leq n\\}$.
Consider for every $0\leq k<m$ and vector $\vec{k}=k_{1},\ldots,k_{n}$ with
$0<k_{i}\leq m_{i}$ the query

$\boldsymbol{q}_{k,\vec{k}}=\Diamond(\rho_{k,\vec{k}}^{0}\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(\cdots\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\rho_{k,\vec{k}}^{k}))$

where

$\rho_{k,\vec{k}}^{j}=\bigcap_{1\leq i\leq
n}\\{A|A(k_{i}+j)\in\mathcal{D}_{i}\\}$

Let $\Xi$ denote the set of queries of the form $\boldsymbol{q}_{k,\vec{k}}$
that are in $\mathcal{Q}_{\textit{in}}$. Then it is easy to see that there
exists a query in $\mathcal{Q}_{\textit{in}}$ that separates $E$ iff some
query in $\Xi$ separates $E$. The latter can be checked in polynomial time if
$n$ is fixed.

(3) Let $E^{+}=\\{\mathcal{D}_{1},\ldots,\mathcal{D}_{n}\\}$ be a set of
sequences. Assume

$\mathcal{D}_{1}=\\{A_{0}\\}\\{A_{1}\\}\cdots\\{A_{m}\\}$

Then any possible separating sequence query in $\mathcal{Q}_{\textit{in}}$
takes the form

$\Diamond(A_{k_{1}}\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(\cdots{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}A_{k_{2}}))$

with $0<k_{1}\leq k_{2}\leq m$. Clearly it can be checked in polynomial time
whether any such query separates $E$. ∎

##  Appendix C Proofs for Section 5

Theorem 9. Let
$\boldsymbol{q}\in\mathcal{Q}^{\sigma}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
be in normal form (1). A weakening frontier for $\boldsymbol{q}$ in
$\mathcal{Q}^{\sigma}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
can be computed in polytime by applying once to $\boldsymbol{q}$ one of the
following operations, for $i\in[n]$ and
$\boldsymbol{q}_{i}=\rho_{i}\land{\boldsymbol{o}}_{i+1}(\rho_{i+1}\land\dots\land{\boldsymbol{o}}_{n}\rho_{n})$:

  1. 1.

drop some atom from $\rho_{i}$;

  2. 2.

replace some $\Diamond(\top\wedge\Diamond\boldsymbol{q}_{i})$ in
$\boldsymbol{q}$ by $\Diamond\boldsymbol{q}_{i}$;

  3. 3.

replace some
${\boldsymbol{o}}_{i}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$ by
$\Diamond$.

If $\boldsymbol{q}\in\mathcal{Q}^{\sigma}_{p}[\Diamond]$, a weakening frontier
for $\boldsymbol{q}$ in $\mathcal{Q}^{\sigma}_{p}[\Diamond]$ can be
constructed in polynomial time using operations 1 and 2.

###### Proof.

Let $\mathcal{F}$ denote the set of queries defined in Theorem 9. It is easy
to see using Lemma 3 that $\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ and
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$ for all
$\boldsymbol{q}^{\prime}\in\mathcal{F}$.

Assume now $\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ and
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$ for some
$\boldsymbol{q}^{\prime}\in\mathcal{Q}^{\sigma}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$.
We show that there exists a query
$\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ such that
$\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}^{\prime}$. Assume

$\boldsymbol{q}^{\prime}=\rho_{0}^{\prime}\wedge{\boldsymbol{o}}_{1}^{\prime}(\rho_{1}^{\prime}\wedge\cdots\wedge{\boldsymbol{o}}_{m}^{\prime}(\rho_{m}^{\prime})).$

and assume that $g:[m]\rightarrow[n]$ is a containment witness for
$\boldsymbol{q},\boldsymbol{q}^{\prime}$.

We distinguish the following cases.

Case 1. $g$ is a surjective mapping onto $[n]$. Then $n=m$ and $g(i)=i$ for
all $i\in[m]$. Hence $\rho_{i}^{\prime}\subseteq\rho_{i}$ for all $i\in[m]$.
Then, as $\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$, either
${\boldsymbol{o}}_{i}={\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}$
and ${\boldsymbol{o}}_{i}^{\prime}=\Diamond$ for some $i\in[m]$ or
$\rho_{i}^{\prime}\subsetneq\rho_{i}$ for some $i\in[m]$. In the first case
$\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}^{\prime}$ for a
$\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ obtained in Point 3 and in the
second case $\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}^{\prime}$ for
a $\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ obtained in Point 1.

Case 2. $g$ is not onto $[n]$. Take any $i\leq n$ that is not in the range of
$g$. If there is $i<m$ with $f(i+1)-f(i)\geq 2$, then
$\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}^{\prime}$ for a
$\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ obtained in Point 2. Otherwise
$n$ is not in the range of $g$ and
$\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}^{\prime}$ for a
$\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ obtained in Point 1. ∎

Example 12 We represent queries in $\mathcal{Q}^{\sigma}[\Diamond]$ of the
form (1) as $\rho_{0}\dots\rho_{n}$. For
$\sigma=\\{A_{1},A_{2},B_{1},B_{2}\\}$, let
$\boldsymbol{q}_{1}=\emptyset(\boldsymbol{q}\sigma)^{n}\boldsymbol{q}$,
$\boldsymbol{q}_{2}=\emptyset\sigma^{2n+1}$, and
$\boldsymbol{q}=\\{A_{1},A_{2}\\}\\{B_{1},B_{2}\\}$. We show using [Fortin et
al., 2022, Example 18] that any strengthening frontier for the query
$\boldsymbol{q}_{1}\land\boldsymbol{q}_{2}$ in
$\mathcal{Q}^{\sigma}[\Diamond]$ is of size $O(2^{n})$. Indeed, let $P$ be the
set of queries of the form
$\emptyset\boldsymbol{q}_{1}\dots\boldsymbol{q}_{n+1}$, where
$\boldsymbol{q}_{i}$ is either $\\{A_{1}\\}\\{A_{2}\\}$ or
$\\{B_{1}\\}\\{B_{2}\\}$. Clearly, $|P|=2^{n+1}$. As shown in Fortin et al.
[2022], $\boldsymbol{q}_{1}\wedge\boldsymbol{q}_{2}\not\models\boldsymbol{q}$
for all $\boldsymbol{q}\in P$ and, for any data instance $\mathcal{D}$ with
$\mathcal{D}\models\boldsymbol{q}_{1}\wedge\boldsymbol{q}_{2}$, there is at
most one $\boldsymbol{q}\in P$ with $\mathcal{D}\not\models\boldsymbol{q}$. It
follows that $|\mathcal{F}|\geq 2^{n+1}$, for otherwise the pigeonhole
principle would give distinct $\boldsymbol{q}^{1},\boldsymbol{q}^{2}\in P$ and
some $\boldsymbol{q}\in\mathcal{F}$ such that
$\boldsymbol{q}_{1}\land\boldsymbol{q}_{2}\land\boldsymbol{q}^{i}\models\boldsymbol{q}$,
$i=1,2$. As
$\boldsymbol{q}_{1}\land\boldsymbol{q}_{2}\not\models\boldsymbol{q}$, there is
a data instance $\mathcal{D}\models\boldsymbol{q}_{1}\land\boldsymbol{q}_{2}$
with $\mathcal{D}\not\models\boldsymbol{q}$, and so
$\mathcal{D}\not\models\boldsymbol{q}^{i}$, for $i=1,2$, contrary to
$\boldsymbol{q}^{1}\neq\boldsymbol{q}^{2}$.

Theorem 14 is a consequence of the following two results.

######  Theorem 30.

Let
$\boldsymbol{q}=\Diamond(\rho_{1}\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(\rho_{2}\land\dots\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\rho_{n})\in\mathcal{Q}_{\textit{in}}^{\sigma}$.
A weakening frontier for $\boldsymbol{q}$ in
$\mathcal{Q}_{\textit{in}}^{\sigma}$ can be computed in polytime by dropping
some atom from $\rho_{i}$ for some $i\in[n]$; here, if $i=1$ and $\rho_{i}$ is
a singleton, then also drop $\top$ and take
$\Diamond(\rho_{2}\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(\rho_{3}\land\dots\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\rho_{n})$.

###### Proof.

Let $\mathcal{F}$ denote the set of queries defined in Theorem 30. It is easy
to see using Lemma 3 that $\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ and
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$ for all
$\boldsymbol{q}^{\prime}\in\mathcal{F}$.

Assume now $\boldsymbol{q}\models\boldsymbol{q}^{\prime}$ and
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$ for some
$\boldsymbol{q}^{\prime}\in\mathcal{Q}_{\textit{in}}^{\sigma}$. We show that
there exists a query $\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ such that
$\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}^{\prime}$. Assume

$\boldsymbol{q}^{\prime}=\Diamond(\rho_{1}^{\prime}\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(\rho_{2}^{\prime}\wedge\cdots\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\rho_{m}^{\prime})).$

and assume that $g:[m]\rightarrow[n]$ is a containment witness for
$\boldsymbol{q},\boldsymbol{q}^{\prime}$.

We distinguish the following cases.

Case 1. $g$ is a surjective mapping onto $[n]$. Then $n=m$ and $g(i)=i$ for
all $i\in[m]$. Hence $\rho_{i}^{\prime}\subseteq\rho_{i}$ for all $i\in[m]$.
Then, as $\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$,
$\rho_{i}^{\prime}\subsetneq\rho_{i}$ for some $i\in[m]$. Then
$\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}^{\prime}$ for a
$\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ obtained by dropping an atom
from $\rho_{i}$ (observe that $\rho_{i}^{\prime}\not=\top$ by the definition
of interval queries, so $\rho_{i}$ is not a singleton).

Case 2. $g$ is not onto $[n]$. Then either $i=1$ or $i=n$ are not in the range
of $g$. If $i=1$, then we obtain $\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$
with $\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}^{\prime}$ by dropping
an atom from $\rho_{1}$ (if $\rho_{1}$ is a singleton we also drop $\top$). If
$i=n>1$, then we obtain $\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ with
$\boldsymbol{q}^{\prime\prime}\models\boldsymbol{q}^{\prime}$ by dropping an
atom from $\rho_{n}$. ∎

######  Theorem 31.

Let
$\boldsymbol{q}=\Diamond(\rho_{1}\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(\rho_{2}\land\dots\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\rho_{n})\in\mathcal{Q}_{\textit{in}}^{\sigma}$.
A strengthening frontier for $\boldsymbol{q}$ in
$\mathcal{Q}_{\textit{in}}^{\sigma}$ can be computed by applying once to
$\boldsymbol{q}$ one of the following operations:

  1. 1.

extend some $\rho_{i}$ in $\boldsymbol{q}$ by some
$A\in\sigma\setminus\rho_{i}$;

  2. 2.

insert $A\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}^{n}$ before
$\rho_{1}$, that is, form
$\Diamond(A\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}^{n}(\rho_{1}\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(\rho_{2}\land\dots\land{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\rho_{n})$
for some $A\in\sigma$ and $n\geq 1$;

  3. 3.

add ${\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}^{n}A$ at the end of
$\boldsymbol{q}$, for some $A\in\sigma$ and $n\geq 1$.

###### Proof.

Let $\mathcal{F}$ be the set of queries obtained by a single application of
one of these operations to $\boldsymbol{q}$. By Lemma 3,
$\boldsymbol{q}^{\prime}\models\boldsymbol{q}$ and
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$ for all
$\boldsymbol{q}^{\prime}\in\mathcal{F}$. Let
$\boldsymbol{q}^{\prime}\models\boldsymbol{q}$ and
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$, for some
$\boldsymbol{q}^{\prime}\in\mathcal{Q}_{\textit{in}}^{\sigma}$ of the form

$\boldsymbol{q}^{\prime}=\Diamond(\rho_{1}^{\prime}\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(\rho_{2}^{\prime}\wedge\cdots\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\rho_{m}^{\prime})).$

Take a containment witness $h\colon[n]\rightarrow[m]$ for
$\boldsymbol{q}^{\prime},\boldsymbol{q}$. If $h$ is surjective, then $n=m$ and
$h(i)=i$ for all $i\in[n]$, and so $\rho_{i}\subseteq\rho_{i}^{\prime}$. As
$\boldsymbol{q}\not\equiv\boldsymbol{q}^{\prime}$,
$\rho_{i}\subsetneq\rho_{i}^{\prime}$, for some $i\in[n]$. Then operation 1
gives a $\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ with
$\boldsymbol{q}^{\prime}\models\boldsymbol{q}^{\prime\prime}$.

Suppose $h$ is not surjective. Then either $i=1$ is not in the range of $h$ or
$i=m$ is not in the range of $h$. In the first case
$\boldsymbol{q}^{\prime}\models\boldsymbol{q}^{\prime\prime}$ for a
$\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ given by operation 2. In the
second case, $\boldsymbol{q}^{\prime}\models\boldsymbol{q}^{\prime\prime}$ for
a $\boldsymbol{q}^{\prime\prime}\in\mathcal{F}$ given by operation 3. ∎

##  Appendix D Proofs for Section 6

Theorem 17. For $\mathcal{Q}[\Diamond]$, the most specific separator
verification problem coincides with the unique most specific separator
verification problem and is coNP-complete.

###### Proof.

It remains to show the lower bound. We reduce SAT to the complement of most
specific separator verification. Let
$\varphi=\psi_{1}\wedge\ldots\wedge\psi_{k}$ be a propositional formula with
$k$ clauses over $n$ variables $x_{1},\ldots,x_{n}$. We assume without loss of
generality that no variable occurs both positively and negatively in a clause.
We use $2n$ atoms $A_{1},\bar{A}_{1},\ldots,A_{n},\bar{A}_{n}$. Define the
positive examples
$E^{+}=\\{\mathcal{D}_{0},\mathcal{D}_{0}^{\prime},\mathcal{D}_{1},\ldots,\mathcal{D}_{n}\\}$
by setting

  * •

$\mathcal{D}_{0}=\\{A_{i}(1),\bar{A}_{i}(1)\mid 1\leq i\leq n\\}$,

  * •

$\mathcal{D}_{0}^{\prime}=\\{A_{i}(2),\bar{A}_{i}(2)\mid 1\leq i\leq n\\}$,

and including in $\mathcal{D}_{i}$, for $1\leq i\leq n$, the assertions:

  * •

$A_{i}(1)$ and $\bar{A}_{i}(2)$, and

  * •

$A_{j}(1),\bar{A}_{j}(1),A_{j}(2),\bar{A}_{j}(2)$ for all $j\neq i$.

We also add to each $\mathcal{D}_{i}$ the following, for $1\leq\ell\leq k$:

  * •

$\bar{A}_{j}(2+\ell)$, if $x_{j}$ does not occur negatively in $\psi_{\ell}$,
and

  * •

$A_{j}(2+\ell)$, if $x_{j}$ does not occur positively in $\psi_{\ell}$.

Now consider the query

$\boldsymbol{q}=\bigwedge_{1\leq\ell\leq k}\Diamond\rho_{\ell}$

with $\rho_{\ell}$ containing:

  * •

$\bar{A}_{j}$, if $x_{j}$ does not occur negatively in $\psi_{\ell}$, and

  * •

$A_{j}$, if $x_{j}$ does not occur positively in $\psi_{\ell}$.

The negative examples are not relevant, we simply take
$E^{-}=\\{\mathcal{D}^{-}\\}$ with $\mathcal{D}^{-}=\\{A_{1}(0)\\}$.

Then clearly $\mathcal{D},0\models\boldsymbol{q}$ for all $\mathcal{D}\in
E^{+}$ and $\mathcal{D}^{-},0\not\models\boldsymbol{q}$. We show that
$\boldsymbol{q}$ is equivalent to the unique most specific separator if and
only if $\varphi$ is not satisfiable. For a variable assignment $\mathfrak{a}$
for $x_{1},\ldots,x_{n}$, we denote with $\rho_{\mathfrak{a}}$ the set that
contains, for all $i$, $A_{i}$, if $\mathfrak{a}(x_{i})=1$ and $\bar{A}_{i}$,
otherwise.

Assume first that $\varphi$ is satisfiable. Take a variable assignment
$\mathfrak{a}$ witnessing this. Then $\Diamond\rho_{\mathfrak{a}}$ separates
$E$ but $\boldsymbol{q}\not\models\Diamond\rho_{\mathfrak{a}}$ and so
$\boldsymbol{q}$ is not a most specific separating query for $E$. To show that
$\boldsymbol{q}\not\models\Diamond\rho_{\mathfrak{a}}$ take the data instance
$\mathcal{D}$ containing for $1\leq\ell\leq k$:

  * •

$\bar{A}_{j}(2+\ell)$, if $x_{j}$ does not occur negatively in $\psi_{\ell}$,
and

  * •

$A_{j}(2+\ell)$, if $x_{j}$ does not occur positively in $\psi_{\ell}$.

Then, by definition, $\mathcal{D},0\models\boldsymbol{q}$. But
$\mathcal{D},0\not\models\Diamond\rho_{\mathfrak{a}}$ since $\mathfrak{a}$ is
a satisfying variable assignment for $\varphi$.

For the converse direction, assume that $\boldsymbol{q}^{\prime}$ is a query
in $\mathcal{Q}[\Diamond]$ that separates $E$ but that
$\boldsymbol{q}\not\models\boldsymbol{q}^{\prime}$. We show that $\varphi$ is
satisfiable. By the positive examples $\mathcal{D}_{0}$ and
$\mathcal{D}_{0}^{\prime}$ we may assume that $\boldsymbol{q}^{\prime}$ is a
conjunction

$\boldsymbol{q}^{\prime}=\Diamond\rho^{\prime}_{1}\wedge\ldots\wedge\Diamond\rho^{\prime}_{\ell}$

with each $\rho^{\prime}_{j}$ a set of atoms. It should be clear that each
$\Diamond\rho^{\prime}_{j}$ separates $E$ and there is at least one $j$ with
$\boldsymbol{q}\not\models\Diamond\rho^{\prime}_{j}$. Thus, we can assume that
$\boldsymbol{q}^{\prime}$ actually takes the form $\Diamond\rho$ for some set
of atoms $\rho$.

By construction of the positive examples $\mathcal{D}_{i}$, $1\leq i\leq n$,
either $\rho\subseteq\rho_{\ell}$ for some $1\leq\ell\leq k$, or for every $i$
at most one of $A_{i},\bar{A}_{i}$ is contained in $\rho$. As
$\boldsymbol{q}\not\models\boldsymbol{q}^{\prime}$, the first condition does
not hold and the latter holds. Thus, $\rho\subseteq\rho_{\mathfrak{a}}$ for
some variable assignment $\mathfrak{a}$. It remains to show that
$\mathfrak{a}$ is a model for $\varphi$. But this follows directly from
$\rho_{\mathfrak{a}}\not\subseteq\rho_{\ell}$ for any $\rho_{\ell}$,
$1\leq\ell\leq k$. ∎

We do not know whether Theorem 17 still holds if the number of positive
examples is bounded.

Theorem 18. Unique most specific/general separator verification in
$\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$,
$\mathcal{Q}_{p}[\Diamond]$, $\mathcal{Q}_{\textit{in}}$ as well as unique
most general separator verification in $\mathcal{Q}[\Diamond]$ are coNP-
complete.

###### Proof.

For the upper bound we show an NP upper bound for the complement. For given
$\boldsymbol{q}$ and $E$, check that either $\mathcal{Q}$ is not a most
general/specific separator (this is in P by Corollary 16) or there exists
$\boldsymbol{q}^{\prime}$ with
$\boldsymbol{q}^{\prime}\not\equiv\boldsymbol{q}$ which separates $E$ (which
can be done in NP by guessing $\boldsymbol{q}^{\prime}$ and then doing the
checks in P).

For the lower bounds we show an NP lower bound for the complement. We use that
given a propositional formula $\varphi$ and a satisfying assignment
$\mathfrak{a}$ it is NP-hard to decide whether there is satisfying assignment
for $\varphi$ different from $\mathfrak{a}$.

Let $\varphi=\psi_{1}\wedge\ldots\wedge\psi_{k}$ a propositional formula with
$k$ clauses over $n$ variables $x_{1},\ldots,x_{n}$. Let $\mathfrak{a}_{0}$ be
a satisfying assignment. We assume without loss of generality that no variable
occurs both positively and negatively in a clause. We use $2n$ atoms
$A_{1},\bar{A}_{1},\ldots,A_{n},\bar{A}_{n}$. Define the positive examples
$E^{+}=\\{\mathcal{D}_{0},\mathcal{D}_{0}^{\prime},\mathcal{D}_{1},\ldots,\mathcal{D}_{n}\\}$
by setting

  * •

$\mathcal{D}_{0}=\\{A_{i}(1),\bar{A}_{i}(1)\mid 1\leq i\leq n\\}$,

  * •

$\mathcal{D}_{0}^{\prime}=\\{A_{i}(2),\bar{A}_{i}(2)\mid 1\leq i\leq n\\}$,

and including in $\mathcal{D}_{i}$, for $1\leq i\leq n$, the assertions:

  * •

$A_{i}(1)$ and $\bar{A}_{i}(2)$, and

  * •

$A_{j}(1),\bar{A}_{j}(1),A_{j}(2),\bar{A}_{j}(2)$ for all $j\neq i$.

We next define
$E^{-}=\\{\mathcal{D}_{1}^{1},\ldots,\mathcal{D}_{k}^{1},\mathcal{D}^{2}_{1},\ldots,\mathcal{D}^{2}_{n}\\}$.
In $\mathcal{D}_{i}^{1}$, $1\leq i\leq k$, we include

  * •

$\bar{A}_{j}(1)$, if $x_{j}$ does not occur negatively in $\psi_{i}$, and

  * •

$A_{j}(1)$, if $x_{j}$ does not occur positively in $\psi_{i}$.

In $\mathcal{D}_{i}^{2}$, $1\leq i\leq n$, we include

  * •

$A_{j}(1),\bar{A}_{j}(1)$, for all $j\neq i$.

Set $E=(E^{+},E^{-})$. For a variable assignment $\mathfrak{a}$ for
$x_{1},\ldots,x_{n}$, we denote with $\rho_{\mathfrak{a}}$ the set that
contains, for all $i$, $A_{i}$, if $\mathfrak{a}(x_{i})=1$ and $\bar{A}_{i}$,
otherwise.

######  Lemma 32.

  1. (i)

For every model $\mathfrak{a}$ of $\varphi$, $\Diamond\rho_{\mathfrak{a}}$
separates $E$.

  2. (ii)

If
$\boldsymbol{q}\in\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
separates $E$, then $\boldsymbol{q}\equiv\Diamond\rho_{\mathfrak{a}}$ for some
model $\mathfrak{a}$ of $\varphi$.

###### Proof.

Point (i) is straightforward.

For Point (ii), take any separator $\boldsymbol{q}$ for $E$. Since the
positive example $\mathcal{D}_{0}$ satisfies $\max\mathcal{D}_{0}=1$, we can
assume that $\boldsymbol{q}$ has temporal depth at most 1. It cannot be of
temporal depth 0 as then it would not separate. Thus, $\boldsymbol{q}$ has
temporal depth $1$ and is of shape $\boldsymbol{q}={\boldsymbol{o}}\rho$ for
some $\rho\subseteq\\{A_{1},\bar{A}_{1},\ldots,A_{n},\bar{A}_{n}\\}$ and
${\boldsymbol{o}}\in\\{\Diamond,{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\\}$.
Since $\mathcal{D}_{0}^{\prime}$ is a positive example, ${\boldsymbol{o}}$
cannot be $\bigcirc$ and $\boldsymbol{q}=\Diamond\rho$. By construction of the
positive examples $\mathcal{D}_{i}$, $1\leq i\leq n$, for every $i$ at most
one of $A_{i},\bar{A}_{i}$ is contained in $\rho$. Since all
$\mathcal{D}^{2}_{i}$ are negative examples, also at least one of
$A_{i},\bar{A}_{i}$ is contained in $\rho$. Thus, $\rho=\rho_{\mathfrak{a}}$
for some variable assignment $\mathfrak{a}$. It remains to show that
$\mathfrak{a}$ is a model for $\varphi$. Let $\psi_{i}$ be a clause of
$\varphi$ and assume that $\mathfrak{a}\not\models\psi_{i}$. Then
$\mathfrak{a}(x_{j})=1$ (and hence $A_{j}\in\rho$ if $x_{j}$ occurs negatively
in $\psi_{i}$ and $\mathfrak{a}(x_{j})=0$ (and hence $\bar{A}_{j}\in\rho$) if
$x_{j}$ occurs positively. It is now readily checked that
$\mathcal{D}_{i}^{1},0\models\Diamond\rho$, a contradiction. ∎

Observe that the $\Diamond\rho_{\mathfrak{a}}$ are pairwise incomparable
w.r.t. containment. Hence, it follows from Lemma 32 that
$\Diamond\rho_{\mathfrak{a}_{0}}$ is not the unique most specific/general
separator in
$\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
(equivalenty, $\mathcal{Q}_{p}[\Diamond]$ or $\mathcal{Q}_{\textit{in}}$) iff
there is an assignment $\mathfrak{a}$ distinct from $\mathfrak{a}_{0}$
satisfying $\varphi$.

For $\mathcal{Q}[\Diamond]$ the same argument applies, but only for unique
most general separators. ∎

Theorem 21. Let
$\mathcal{Q}\subseteq\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
be any class containing all $\Diamond\rho$ with $\rho$ a conjunction of atoms.
Then

  * •

counting most specific/general $\mathcal{Q}$-separators is $\sharp P$-hard.

  * •

the existence of unique most specific/general separator is US-hard.

even for $E=(E^{+},E^{-})$ and $\sigma=\mathsf{sig}(E)$ with

  1. 1.

$|E^{-}|\leq 1$; or

  2. 2.

$|E^{-}|\leq 1$, $|\sigma|=2$ and $\mathcal{Q}=\mathcal{Q}_{\textit{in}}$ or
$\mathcal{Q}\supseteq\mathcal{Q}_{p}[\Diamond]$; or

  3. 3.

$|E^{+}|\leq 4$, $|\sigma|=3$, and
$\mathcal{Q}\supseteq\mathcal{Q}_{p}[\Diamond]$.

This result also holds for most general separator case for
$\mathcal{Q}[\Diamond]$ and $|E^{-}|=1$ and $|\sigma|=2$.

###### Proof.

We start with the proof of Point 1. For the sake of readability, we provide
the proof first for an unbounded number of negative examples and argue
afterwards that a single negative examples suffices.

We reduce from SAT in essentially the same way as in the lower bound proof for
Theorem 18 above. Let $\varphi=\psi_{1}\wedge\ldots\wedge\psi_{k}$ a
propositional formula with $k$ clauses over $n$ variables
$x_{1},\ldots,x_{n}$. We assume without loss of generality that no variable
occurs both positively and negatively in a clause. We use $2n$ atoms
$A_{1},\bar{A}_{1},\ldots,A_{n},\bar{A}_{n}$. Define the examples
$E=(E^{+},E^{-})$ in exactly the same way as in the proof of Theorem 18. Then
Lemma 32 holds. Point 1 for an unbounded number of negative examples follows
directly.

To finish the proof for $|E^{-}|=1$, it remains to join the negative examples
into a single one. Recall that, due to the structure of the positive examples,
any separator for $E$ has temporal depth at most $1$. Based on this
observation, it can be verified that Lemma 32 continues to hold when $E^{-}$
is replaced by $\\{\mathcal{D}^{-}\\}$ for the data instance

$\mathcal{D}^{-}=\emptyset\mathcal{D}^{1}_{1}\emptyset^{2}\cdots\emptyset^{2}\mathcal{D}^{1}_{k}\emptyset^{2}\mathcal{D}^{2}_{1}\emptyset^{2}\cdots\emptyset^{2}\mathcal{D}^{2}_{n}.$

We next provide the proof of Point 2. We start by considering
$\mathcal{Q}_{\textit{in}}$. Again, we provide the proof first for an
unbounded number of negative examples and argue afterwards that a single
negative examples suffices.

####  $\mathcal{Q}_{\textit{in}}$

We reduce from SAT. Let $\varphi=\psi_{1}\wedge\ldots\wedge\psi_{k}$ a
propositional formula with $k$ clauses over $n$ variables
$x_{1},\ldots,x_{n}$. We use three atoms $M,A,\bar{A}$. Define the positive
examples $E^{+}=\\{\mathcal{D}_{0},\mathcal{D}_{1},\ldots,\mathcal{D}_{n}\\}$
by including in $\mathcal{D}_{i}$, for $1\leq i\leq n$ the assertions:

  * •

$M(1)$ and $M(n+1)$, and

  * •

$A(i)$ and $\bar{A}(n+i)$, and

  * •

$A(j),\bar{A}(n+j)$ for all $j\neq i$.

In $\mathcal{D}_{0}$, we include

  * •

$M(1)$, and

  * •

$A(i),\bar{A}(i)$, for all $1\leq i\leq n$.

We next define negative examples
$E^{-}=\\{\mathcal{D}^{0},\mathcal{D}_{1}^{1},\ldots,\mathcal{D}_{k}^{1},\mathcal{D}^{2},\mathcal{D}^{3}_{1},\ldots,\mathcal{D}^{3}_{n}\\}$.
In $\mathcal{D}^{0}$, we include

  * •

$M(i),A(i),\bar{A}(i)$, for all $1\leq i\leq n-1$.

In $\mathcal{D}_{i}^{1}$, $1\leq i\leq k$, we include

  * •

$M(1)$, and

  * •

$\bar{A}(j)$, if $x_{j}$ does not occur negatively in $\psi_{i}$, and

  * •

$A(j)$, if $x_{j}$ does not occur positively in $\psi_{i}$.

In $\mathcal{D}^{2}$, we include

  * •

$A(j),\bar{A}(j)$, for all $1\leq j\leq n$.

In $\mathcal{D}^{3}_{i}$, $1\leq i\leq n$, we include

  * •

$M(1)$,

  * •

$A(j),\bar{A}(j)$, for all $i\neq j$.

Set $E=(E^{+},E^{-})$. For a variable assignment $\mathfrak{a}$ for
$x_{1},\ldots,x_{n}$, we denote with $\boldsymbol{q}_{\mathfrak{a}}$ the query

$\boldsymbol{q}_{\mathfrak{a}}=\Diamond(\rho^{1}_{\mathfrak{a}}\wedge({\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\rho^{2}_{\mathfrak{a}}\wedge(\ldots\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\rho_{\mathfrak{a}}^{n})\ldots))$

where $\rho_{\mathfrak{a}}^{1}=\\{M,A\\}$ if $\mathfrak{a}(x_{1})=1$ and
$\rho_{\mathfrak{a}}^{1}=\\{M,\bar{A}\\}$ otherwise, and for all $i>1$,
$\rho_{\mathfrak{a}}^{i}=\\{A\\}$ if $\mathfrak{a}(x_{i})=1$ and
$\rho_{\mathfrak{a}}^{i}=\\{\bar{A}\\}$, otherwise.

######  Lemma 33.

  1. (i)

For every model $\mathfrak{a}$ of $\varphi$, $\boldsymbol{q}_{\mathfrak{a}}$
separates $E$.

  2. (ii)

If $\boldsymbol{q}\in\mathcal{Q}_{\textit{in}}$ separates $E$, then
$\boldsymbol{q}\equiv\boldsymbol{q}_{\mathfrak{a}}$ for some model
$\mathfrak{a}$ of $\varphi$.

  3. (iii)

Every $\mathcal{Q}_{\textit{in}}$-separator for $E$ is both a most general and
most specific separator.

###### Proof.

Point (iii) is immediate from Points (i) and (ii) and the fact that all
$\boldsymbol{q}_{\mathfrak{a}}$ are pairwise incomparable w.r.t. containment.
We hence concentrate on Points (i) and (ii).

Point (i) is straightforward.

For Point (ii), take any separator

$\boldsymbol{q}=\Diamond(\rho^{1}\wedge({\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\rho^{2}\wedge(\ldots\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\rho^{m})\ldots))$

for $E$, for some $m>0$ and sets $\rho^{i}$. Since $\mathcal{D}^{0}$ is a
negative example for $\boldsymbol{q}$, we have $m\geq n$. Since
$\mathcal{D}_{0}$ is a positive example for $\boldsymbol{q}$, we have that
$m\leq n$, hence $m=n$. Then observe that some $\rho^{i}$ has to contain $M$,
since otherwise $\mathcal{D}^{2},0\models\boldsymbol{q}$. By $\mathcal{D}_{0}$
again, it can only be $\rho^{1}$.

By construction of the positive examples, for every $i$ at most one of
$A,\bar{A}$ is contained in $\rho^{i}$. Since all $\mathcal{D}^{3}_{i}$ are
negative examples, each $\rho_{i}$ contains also at least one of $A,\bar{A}$.
Thus, $\boldsymbol{q}=\boldsymbol{q}_{\mathfrak{a}}$ for some variable
assignment $\mathfrak{a}$.

It remains to show that $\mathfrak{a}$ is a model for $\varphi$. Let
$\psi_{i}$ be a clause of $\varphi$ and assume that $v\not\models\psi_{i}$ for
some $i$. Then $\mathfrak{a}(x_{j})=1$ (and hence $A\in\rho_{j})$ if $x_{j}$
occurs negatively in $\psi_{i}$ and $\mathfrak{a}(x_{j})=0$ (and hence
$\bar{A}\in\rho_{j}$) if $x_{j}$ occurs positively. It is now readily checked
that $\mathcal{D}_{i}^{1},0\models\boldsymbol{q}_{\mathfrak{a}}$, a
contradiction. ∎

It remains to join the negative examples into a single one. Recall that,
because of $\mathcal{D}_{0}\in E^{+}$, any separator for $E$ has temporal
depth at most $n$. Based on this observation, it can be verified that Lemma 33
continues to hold when $E^{-}$ is replaced by $\\{\mathcal{D}^{-}\\}$ for the
data instance

$\mathcal{D}^{-}=\emptyset\mathcal{D}^{0}\emptyset^{n}\mathcal{D}^{1}_{1}\emptyset^{n}\cdots\emptyset^{n}\mathcal{D}^{1}_{k}\emptyset^{n}\mathcal{D}^{2}\emptyset^{n}\mathcal{D}^{3}_{1}\emptyset^{n}\cdots\emptyset^{n}\mathcal{D}^{3}_{n}.$

We next assume that
$\mathcal{Q}_{p}[\Diamond]\subseteq\mathcal{Q}\subseteq\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$.

We employ a reduction of 3SAT to a longest common subsequence problem, which
is defined as follows: Given a set $S$ of sequences and a number $m$, decide
whether the sequences in $S$ have a common subsequence of length $m$. We use
the following result [Blin et al., 2012, Proposition 6]. Given a formula
$\varphi=\psi_{1}\wedge\cdots\wedge\psi_{k}$ with $k$ clauses over $n$
variables $x_{1},\ldots,x_{n}$, one can construct in polynomial time a set $S$
of sequences over the alphabet $\\{H,T\\}$ such that

  * •

$S$ contains $k+2$ sequences;

  * •

there is a poly-time computable bijection $f$ from the set $L$ of common
subsequences of $S$ of length exactly $11n$ onto the set $V$ of variable
assignments $\mathfrak{a}$ satisfying $\varphi$;

  * •

no common subsequence of the sequences in $S$ of length $>11n$ exists.

Thus, given $\varphi$ as above, we use $S$ to construct $E=(E^{+},E^{-})$. For
any sequence $s_{1}\cdots s_{\ell}\in S$ we include in $E^{+}$ the data
instance $\emptyset\\{s_{1}\\}\cdots\\{s_{\ell}\\}$. We also include in
$E^{+}$ the data instances $\mathcal{D}_{1}^{+}=\emptyset\\{H,T\\}^{11n}$ and
$\mathcal{D}_{2}^{+}=\emptyset(\emptyset^{11n}\\{H,T\\})^{11n}$ and include in
$E^{-}$ the data instances $\mathcal{D}_{1}^{-}=\emptyset\\{H,T\\}^{11n-1}$
and $\mathcal{D}_{2}^{-}=\emptyset(\emptyset^{11n}\\{H,T\\})^{11n-1}$.

Claim 1. Any query $\boldsymbol{q}\in\mathcal{Q}$ separating $E$ is a
$\Diamond$-path sequence query and the sequence defined by $\boldsymbol{q}$ is
a common subsequence of the sequences in $S$.

Proof of Claim 1. To prove Claim 1 suppose $\boldsymbol{q}\in\mathcal{Q}$ of
the form

$\boldsymbol{q}=\rho_{0}\land{\boldsymbol{o}}_{1}(\rho_{1}\land{\boldsymbol{o}}_{2}(\rho_{2}\land\dots\land{\boldsymbol{o}}_{\ell}\rho_{\ell})),$
(4)

separates $E$. By definition of separation it is clear that $\rho_{0}=\top$
and $|\rho_{i}|\leq 1$. From $\mathcal{D}_{1}^{+}\in E^{+}$ it follows that
$\ell\leq 11n$ and from $\mathcal{D}_{1}^{-}\in E^{-}$ it follows that
$\ell\geq 11n$. Hence $\ell=11n$.

It follows from $\mathcal{D}_{2}^{+}\in E^{+}$ and $\ell=11n$ that
${\boldsymbol{o}}_{i}=\Diamond$ for all $i\leq\ell$. We obtain from
$\mathcal{D}_{2}\in E^{-}$ that $|\rho_{i}|\geq 1$ for all $i\geq 1$. Thus,
$\boldsymbol{q}$ is a $\Diamond$-path sequence query of length $11n$. Since we
included one positive example for every sequence in $S$, the sequence
corresponding to $\boldsymbol{q}$ is a common subsequence of the sequences in
$S$. This finishes the proof of Claim 1.

The following claim follows directly from the definition of $E$.

Claim 2. For every $s_{1}\ldots s_{\ell}\in S$, the corresponding
$\Diamond$-path query $\Diamond(s_{1}\land\Diamond(s_{2}\cdots\Diamond
s_{\ell}))$ separates $E$.

It follows from Claims 1 and 2 and the fact that all sequence $\Diamond$-path
queries of the same temporal depth are pairwise incomparable w.r.t.
containment, that there is a poly-time computable bijection $f$ from the set
$L^{\prime}$ of queries in $\mathcal{Q}$ separating $E$ onto the set $V$ of
satisfying assignments for $\varphi$.

We now come to the proof of Point 3. We use an existing reduction showing NP-
hardness of the _consistent subsequence problem_ , defined as follows. Given
two sets $P,N$ of sequences, decide whether there is a sequence $s$
_consistent with $P,N$_, that is, $s$ is a subsequence of each sequence in
$P$, but of no sequence in $N$.

We use the following result [Fraser, 1996, Theorem 2.1]. Given a 3CNF formula
$\varphi=\psi_{1}\wedge\ldots\wedge\psi_{k}$ with $k$ clauses over $n$
variables, one can construct in polynomial time two sets $P,N$ of sequences
over an alphabet $\sigma=\\{\\#,0,1\\}$ such that

  * •

$P$ contains two sequences;

  * •

there is a poly-time computable bijection $f$ from the set $L$ of sequences
that are consistent with $P,N$ of length $6k$ onto the set of models of
$\varphi$;

  * •

any sequence that is consistent with $P,N$ has length exactly $6k$.

Thus, given $\varphi$ as above, we use $P,N$ to construct $E=(E^{+},E^{-})$.
For any sequence $s_{1}\cdots s_{\ell}\in P$ we include in $E^{+}$ the data
instance $\emptyset\\{s_{1}\\}\cdots\\{s_{\ell}\\}$. Similarly, for any
sequence $s_{1}\cdots s_{\ell}\in N$, we include in $E^{-}$ the data instance
$\emptyset\\{s_{1}\\}\cdots\\{s_{\ell}\\}$. We also include in $E^{+}$ the
data instances $\mathcal{D}_{1}^{+}=\emptyset\\{0,1,\\#\\}^{6k}$ and
$\mathcal{D}_{2}^{+}=\emptyset(\emptyset^{6k}\\{0,1,\\#\\})^{6k}$, and include
in $E^{-}$ the data instances
$\mathcal{D}_{1}^{-}=\emptyset(\\{0,1,\\#\\})^{6k-1}$ and
$\mathcal{D}_{2}^{-}=\emptyset(\emptyset^{6k}\\{0,1,\\#\\})^{6k-1}$.

Assume now that a set $\mathcal{Q}$ with
$\mathcal{Q}_{p}[\Diamond]\subseteq\mathcal{Q}\subseteq\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
is given.

Claim 1. Any query $\boldsymbol{q}\in\mathcal{Q}$ separating $E$ is a
$\Diamond$-path sequence query and the sequence defined by $\boldsymbol{q}$ is
consistent with $P,N$.

Proof of Claim 1. Suppose $\boldsymbol{q}\in\mathcal{Q}$ of the form

$\boldsymbol{q}=\rho_{0}\land{\boldsymbol{o}}_{1}(\rho_{1}\land{\boldsymbol{o}}_{2}(\rho_{2}\land\dots\land{\boldsymbol{o}}_{\ell}\rho_{\ell}))$

separates $E$. By definition of separation it is clear that $\rho_{0}=\top$
and $|\rho_{i}|\leq 1$. From $\mathcal{D}_{1}^{+}\in E^{+}$ it follows that
$\ell\leq 6k$ and from $\mathcal{D}_{1}^{-}\in E^{-}$ it follows that
$\ell\geq 6k$. Hence $\ell=6k$. From $\mathcal{D}_{2}^{-}\in E^{-}$ it also
follows that $\rho_{i}\neq\emptyset$ for all $i>1$, hence $\boldsymbol{q}$ is
a ${\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond$-path sequence
query.

It follows from $\mathcal{D}_{2}^{+}\in E^{+}$ and $\ell=6k$ that
${\boldsymbol{o}}_{i}=\Diamond$ for all $i\leq\ell$. We have thus shown that
$\boldsymbol{q}$ is a $\Diamond$-path sequence query of length $6k$. Finally,
it is easy to see that the corresponding sequence is consistent with $P,N$.
This finishes the proof of Claim 1.

The following claim follows directly from the definition of $E$.

Claim 2. For every sequence consistent with $P,N$, the corresponding
$\Diamond$-path query separates $E$.

It follows from Claims 1 and 2 to that we have a poly-time computable
bijection $f$ from the set $L^{\prime}$ of queries in $\mathcal{Q}$ separating
$E$ onto the set of models of $\varphi$. Moreover, the queries in $L^{\prime}$
are all $\Diamond$-path sequence queries of the same length and therefore
incomparable w.r.t. $\models$.

We finally come to $\mathcal{Q}[\Diamond]$. Observe that our claim follow
directly from Point 2 for $\mathcal{Q}_{p}[\Diamond]$: as we have only one
negative example, any separating query in $\mathcal{Q}[\Diamond]$ contains a
conjunct in $\mathcal{Q}_{p}[\Diamond]$ that separates. Hence the most general
separating queries in $\mathcal{Q}[\Diamond]$ and $\mathcal{Q}_{p}[\Diamond]$
coincide (up to logical equivalence). So the $\sharp\textsc{P}$-lower bound
established for $\mathcal{Q}_{p}[\Diamond]$ for counting most general
separating queries and the US-lower bound for the existence of a unique most
general separator also hold for $\mathcal{Q}[\Diamond]$. ∎

Theorem 22. Let $\mathcal{Q}=\mathcal{Q}[\Diamond]$ or
$\mathcal{Q}\subseteq\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
be any class containing all $\Diamond\rho$ with a conjunction of atoms $\rho$.
Then counting most general $\mathcal{Q}$-separators is $\sharp\textsc{P}$-hard
even for example sets $E=(E^{+},E^{-})$ with $|E^{+}|=2$ and $|E^{-}|=1$.

###### Proof.

By reduction from counting the number of satisfying assignments for a monotone
propositional formula (that is, a formula in conjunctive normal form without
negation). We re-use data instances introduced before.

Take a monotone Boolean formula $\varphi=\psi_{1}\wedge\dots\wedge\psi_{k}$
with clauses $\psi_{i}$ over variables $x_{1},\dots,x_{n}$. We construct
$E=(E^{+},E^{-})$ such that there is a bijection between the satisfying
assignments for $\varphi$ and the most general separators for $E$ in
$\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
(even queries of the form $\Diamond\rho$). Define the positive examples
$E^{+}=\\{\mathcal{D}_{0},\mathcal{D}_{0}^{\prime}\\}$ with $2n$ atoms
$A_{1},\bar{A}_{1},\dots,A_{n},\bar{A}_{n}$ by taking

$\displaystyle\mathcal{D}_{0}=\\{A_{i}(1),\bar{A}_{i}(1)\mid 1\leq i\leq
n\\},$ $\displaystyle\mathcal{D}_{0}^{\prime}=\\{A_{i}(2),\bar{A}_{i}(2)\mid
1\leq i\leq n\\}$

Let $E^{-}=\\{\mathcal{D}^{-}\\}$ with

$\mathcal{D}^{-}=\emptyset\mathcal{D}^{1}_{1}\emptyset^{2}\cdots\emptyset^{2}\mathcal{D}^{1}_{k}\emptyset^{2}\mathcal{D}^{2}_{1}\emptyset^{2}\cdots\emptyset^{2}\mathcal{D}^{2}_{n}.$

where $\mathcal{D}_{i}^{1}$, $1\leq i\leq k$, comprises all $\bar{A}_{j}(1)$
and $A_{j}(1)$ if $x_{j}$ does not occur positively in $\psi_{i}$, and
$\mathcal{D}_{i}^{2}=\\{A_{j}(1),\bar{A}_{j}(1)\mid j\neq i\\}$.

For a variable assignment $\mathfrak{a}$ for $x_{1},\ldots,x_{n}$, we denote
with $\rho_{\mathfrak{a}}$ the set that contains, for all $i$, $A_{i}$, if
$\mathfrak{a}(x_{i})=1$ and $\bar{A}_{i}$, otherwise. Now one can easily show:

  1. (i)

For every model $\mathfrak{a}$ of $\varphi$, $\Diamond\rho_{\mathfrak{a}}$
separates $E$.

  2. (ii)

If
$\boldsymbol{q}\in\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
separates $E$, then
$\boldsymbol{q}\equiv\Diamond(\rho_{\mathfrak{a}}\cup\rho)$ for some model
$\mathfrak{a}$ of $\varphi$ and some set $\rho$ of atoms of the form
$\bar{A}_{i}$.

The claim for
$\mathcal{Q}\subseteq\mathcal{Q}_{p}[{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}\Diamond]$
follows. The claim for $\mathcal{Q}[\Diamond]$ also follows since we have only
one negative example and so any most general separator is in
$\mathcal{Q}[\Diamond]$. ∎

We show the properties of $\mathcal{Q}_{\textit{in}}$ that are stated in
Section 6.

######  Theorem 34.

(1) For $\mathcal{Q}_{\textit{in}}$, counting most specific separators is in P
if $|E^{+}|$ is bounded.

(2) For example data instances $E=(E^{+},E^{-})$ that contain sequences,
counting most specific sequence queries in $\mathcal{Q}_{\textit{in}}$ that
separate $E$ is in P.

###### Proof.

We extend the proof of Theorem 29.

(1) Assume $E^{+}=\\{\mathcal{D}_{1},\ldots,\mathcal{D}_{n}\\}$. Let $\Xi$ be
the set of queries defined in the proof of Theorem 29. Then the most specific
queries in $\Xi$ that separate $E$ coincide with the most specific queries in
$\mathcal{Q}_{\textit{in}}$ that separate $E$, and so can be counted in
polytime.

(2) $E^{+}=\\{\mathcal{D}_{1},\ldots,\mathcal{D}_{n}\\}$ be a set of
sequences. Assume

$\mathcal{D}_{1}=\\{A_{0}\\}\\{A_{1}\\}\cdots\\{A_{m}\\}$

Then any possible separating sequence query in $\mathcal{Q}_{\textit{in}}$
takes the form

$\Diamond(A_{k_{1}}\wedge{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}(\cdots{\raisebox{1.07639pt}{\text{\scriptsize$\bigcirc$}}}A_{k_{2}}))$

with $0<k_{1}\leq k_{2}\leq m$. Clearly the most specific queries of this form
that separate $E$ can be counted in P. ∎

##  Appendix E Proofs for Section 7

Let $t_{\mathcal{D}}(n)=\\{A\mid A(n)\in\mathcal{D}\\}$. It will be convenient
to assume that $t_{\mathcal{E}_{j}}(\infty)=\sigma$, for $E_{j}\in E^{-}$,
where $\sigma$ is the set of symbols occurring in $E^{+}$.

Lemma 24. _$\mathsf{s}(E,\mathcal{Q})\neq\emptyset$ iff
$\mathfrak{P}\otimes\mathfrak{N}$ contains a separating path $\pi$, with
$\boldsymbol{q}_{\pi}$ separating $E$._

###### Proof.

$(\Rightarrow)$ Suppose $\boldsymbol{q}$ of the form
$\rho_{0}\land\Diamond(\rho_{1}\land(\dots\Diamond\rho_{\ell})\dots)$
separates $E$. If $\ell=0$, then $\rho_{0}\subseteq\boldsymbol{l}(\bar{0})$
and $\rho_{0}\not\subseteq t_{\mathcal{E}_{j}}(0)$ for all $1\leq j\leq
c_{-}$. It follows that $\boldsymbol{l}(\bar{0})\neq\emptyset$ and
$(\bar{0},\bar{\infty})$ is in $\mathfrak{P}\times\mathfrak{N}$, which
completes the proof. Suppose $\ell>0$. Further, we assume that
$\rho_{0}\land\Diamond(\rho_{1}\land(\dots\Diamond\rho_{\ell-1})\dots)$ does
not separate $E$, which implies $\rho_{\ell}\neq\emptyset$. We define
$\boldsymbol{n}^{0}=\bar{0}$. Suppose
$\boldsymbol{n}^{i}=(n_{1},\dots,n_{c_{+}})$ has been defined, we define
$\boldsymbol{n}^{i+1}=(n_{1}^{\prime},\dots,n_{c_{+}}^{\prime})$ where
$n_{j}^{\prime}=\min\\{n\mid n>n_{j},\rho_{i+1}\subseteq
t_{\mathcal{D}_{j}}(n)\\}$, for $0\leq i<\ell$. It follows that
$\boldsymbol{l}(\boldsymbol{n}^{\ell})\neq\emptyset$. Then we take
$\boldsymbol{m}^{0}$ to be the root of $\mathfrak{N}$ and set
$\boldsymbol{m}^{i+1}$ to be $\boldsymbol{m}^{\prime}$ such that
$(\boldsymbol{n}^{i},\boldsymbol{m}^{i})\to(\boldsymbol{n}^{i+1},\boldsymbol{m}^{\prime})$.
We claim that the path
$(\boldsymbol{n}^{0},\boldsymbol{m}^{0}),\dots,(\boldsymbol{n}^{\ell},\boldsymbol{m}^{\ell})$
is such that $\boldsymbol{m}^{\ell}=\bar{\infty}$. To prove the claim, we
introduce some notation. For a data instance $\mathcal{E}$ and $t\geq 0$,
denote by $\mathcal{E}^{\leq t}$ the data instance obtained from $\mathcal{E}$
by removing all assertions $A(n)$ with $n>t$. Set $m_{j}^{i}=\min\\{t\mid
t\geq i\text{ and }\mathcal{E}_{j}^{\leq
t}\models\rho_{0}\land\Diamond(\rho_{1}\land(\dots\Diamond\rho_{i})\dots)\\}$
or $m_{j}^{i}=\infty$ if $t$ as above does not exist, for $0\leq i\leq c_{-}$
and $1\leq j\leq l$. Let
$\boldsymbol{m}^{i}_{-}=(m_{1}^{i},\dots,m_{c_{-}}^{i})$. It follows that
$\boldsymbol{m}^{\ell}_{-}=\bar{\infty}$. It is easily shown by induction on
$i$ that $\boldsymbol{m}^{i}_{-}=\boldsymbol{m}^{i}$, which completes the
proof.

$(\Leftarrow)$ Let
$(\boldsymbol{n}^{0},\boldsymbol{m}^{0}),\dots,(\boldsymbol{n}^{\ell},\boldsymbol{m}^{\ell})$
be a path with $\boldsymbol{n}^{0}=\bar{0}$,
$\boldsymbol{l}(\boldsymbol{n}^{\ell})\neq\emptyset$ and
$\boldsymbol{m}^{\ell}=\bar{\infty}$. We will show that
$\boldsymbol{q}=\rho_{0}\land\Diamond(\rho_{1}\land(\dots\Diamond\rho_{\ell})\dots)$
with $\rho_{i}=\boldsymbol{l}(\boldsymbol{n}^{i})$ separates $E$. Indeed,
clearly $\mathcal{D}\models\boldsymbol{q}$ for each $\mathcal{D}\in E^{+}$. By
induction on $i$, we show that $\boldsymbol{m}^{i}_{-}=\boldsymbol{m}^{i}$. It
follows that $\mathcal{E}\not\models\boldsymbol{q}$ for all $\mathcal{E}\in
E^{-}$ which completes the proof. ∎

Lemma 40. _If $\boldsymbol{q}$ of the form (1) separates $E$, then there is a
separating path of the form (2) with
$\rho_{i}\subseteq\boldsymbol{l}(\boldsymbol{n}_{i})$, for all $i\leq n$._

###### Proof.

Straightforwardly follows from the construction in $(\Rightarrow)$ above. ∎

Lemma 26. _A $\mathcal{Q}_{p}[\Diamond]$-query $\boldsymbol{q}$ is a unique
most specific $\mathcal{Q}_{p}[\Diamond]$-separator for $E$ iff there is a
separating path $\pi$ such that $\boldsymbol{q}=\boldsymbol{q}_{\pi}$ and
$\boldsymbol{q}_{\pi}\models\boldsymbol{q}_{\nu}$, for every separating path
$\nu$._

###### Proof.

$(\Rightarrow)$ Let
$\boldsymbol{q}=\rho_{0}\land\Diamond(\rho_{1}\land(\dots\Diamond\rho_{\ell})\dots)$
be a unique most specific separator. Consider the path
$\pi=(\boldsymbol{n}^{0},\boldsymbol{m}^{0}),\dots,(\boldsymbol{n}^{\ell},\boldsymbol{m}^{\ell})$
constructed in the proof of Lemma 24 $(\Rightarrow)$. Clearly, $\pi$ is a
separating path. Because $\boldsymbol{q}$ is a most specific separator and
$\rho_{i}\subseteq\boldsymbol{l}(\boldsymbol{n}^{i})$, it follows that
$\boldsymbol{l}(\boldsymbol{n}^{i})=\rho_{i}$, and so
$\boldsymbol{q}=\boldsymbol{q}_{\pi}$. Let $\nu$ be an arbitrary separating
path in $\mathfrak{P}\times\mathfrak{N}$. From the proof of Lemma 24
$(\Leftarrow)$ we obtain that $\boldsymbol{q}_{\nu}$ is a separator. It
follows that $\boldsymbol{q}_{\pi}\models\boldsymbol{q}_{\nu}$.

$(\Leftarrow)$ Let $\pi$ be a separating path such that
$\boldsymbol{q}_{\pi}\models\boldsymbol{q}_{\nu}$ for every separating path
$\nu$ in $\mathfrak{P}\otimes\mathfrak{N}$. Let
$\boldsymbol{q}=\rho_{0}^{\prime}\land\Diamond(\rho_{1}^{\prime}\land(\dots\Diamond\rho^{\prime}_{\ell^{\prime}})\dots)$
be a separator (for $E$), we only need to show that
$\boldsymbol{q}_{\pi}\models\boldsymbol{q}^{\prime}$. Consider the separating
path
$\nu^{\prime}=(\boldsymbol{n}^{0},\boldsymbol{m}^{0}),\dots,(\boldsymbol{n}^{\ell^{\prime}},\boldsymbol{m}^{\ell^{\prime}})$
constructed in the proof of Lemma 24 $(\Rightarrow)$ for
$\boldsymbol{q}^{\prime}$. Clearly,
$\rho_{i}^{\prime}\subseteq\boldsymbol{l}(\boldsymbol{n}^{i})$. Since we have
$\boldsymbol{q}_{\pi}\models\boldsymbol{q}_{\nu^{\prime}}$, we also obtain
$\boldsymbol{q}_{\pi}\models\boldsymbol{q}^{\prime}$. ∎

We now explain how checking the existence of a separating path $\pi$ such that
$\boldsymbol{q}_{\pi}\models\boldsymbol{q}_{\nu}$ for every separating path
$\nu$ in $\mathfrak{P}\otimes\mathfrak{N}$ can be checked in P. We compute the
required separator $\boldsymbol{q}_{\pi}$ by analysing the queries associated
with the paths leading to each node $(\boldsymbol{n},\boldsymbol{m})$ of
$\mathfrak{P}\otimes\mathfrak{N}$ from its root
$(\bar{0},\boldsymbol{m}_{0})$. We mark inductively each
$(\boldsymbol{n},\boldsymbol{m})$ either by a query $\boldsymbol{q}_{\pi}$,
for some path $\pi$, or by $\varepsilon$. The root is marked by
$\boldsymbol{q}_{\pi}$ for $\pi=(\bar{0},\boldsymbol{m}_{0})$. Now, assume
that all immediate predecessors of $(\boldsymbol{n},\boldsymbol{m})$ have
already been marked. Let $\boldsymbol{q}_{\pi_{i}}$, $i=1,\dots,k$, be all of
their marks different from $\varepsilon$. Consider the extended paths