resources used between the queries: $\mathcal{Q}$ is called polynomial query
learnable wrt $\mathcal{L}$-ontologies using membership queries if there is a
learning algorithm that receives an ontology $\mathcal{O}$ and a positive
example $\mathcal{D},a$ with $\mathcal{D}$ satisfiable wrt $\mathcal{O}$, and
constructs ${\bm{q}}_{T}$ (up to equivalence wrt $\mathcal{O}$) using
polynomially-many queries of polynomial size in the size of
${\bm{q}}_{T},\mathcal{O}$, and $\mathcal{D}$.

Before we can state the main technical result of this section, we introduce
two further conditions on ontologies: polynomially bounded generalisations and
polynomial-time instance checking. An ontology language $\mathcal{L}$ _admits
polynomial-time instance checking_ if given an $\mathcal{L}$-ontology
$\mathcal{O}$, a labeled instance $\mathcal{D},a$, and a concept name $A$, it
is decidable in polynomial time whether $\mathcal{O},\mathcal{D}\models A(a)$.
Let ${\bm{q}}$ be a CQ. We say that ${\bm{q}}$ is
$({\bm{q}}_{T},\mathcal{O})$-minimal if
${\bm{q}}^{\prime}\not\models_{\mathcal{O}}{\bm{q}}_{T}$, for every
restriction ${\bm{q}}^{\prime}$ of ${\bm{q}}$ to a strict subset of the
variables in ${\bm{q}}$. Moreover, ${\bm{q}}$ is $\mathcal{O}$-saturated if
$\mathcal{O},\hat{\bm{q}}\models A(y)$ implies that $A(y)$ is a conjunct in
${\bm{q}}$, for every variable $y$ in ${\bm{q}}$ and every concept name $A$
that occurs in $\mathcal{O}$. A _generalisation sequence for ${\bm{q}}$ wrt
$\mathcal{O}$_ is a sequence ${\bm{q}}_{1},{\bm{q}}_{2},\ldots$ of CQs that
satisfies the following conditions, for all $i\geq 1$:
${\bm{q}}_{i}\models_{\mathcal{O}}{\bm{q}}_{i+1}$ and
${\bm{q}}_{i+1}\not\models_{\mathcal{O}}{\bm{q}}_{i}$, and
${\bm{q}}_{i}\models_{\mathcal{O}}{\bm{q}}$. We say that $\mathcal{O}$ has
_polynomially-bounded generalisation_ if for every CQ ${\bm{q}}$, any
generalisation sequence ${\bm{q}}_{1},{\bm{q}}_{2},\dots$ towards ${\bm{q}}$
such that all ${\bm{q}}_{i}$ are satisfiable wrt $\mathcal{O}$,
$({\bm{q}}_{T},\mathcal{O})$-minimal, and $\mathcal{O}$-saturated has length
bounded by a polynomial in the size of ${\bm{q}}$ and $\mathcal{O}$.

Throughout the section, we consider ontologies in normal form. We strongly
conjecture that this restriction to normal form is not needed, that is, all
results below hold for ontologies that are not necessarily in normal
form.111More concretely, we conjecture that learnability of two-dimensional
query classes $\mathcal{Q}$ wrt $\mathcal{ELHIF}^{\bot}$-ontologies can be
reduced to learnability of $\mathcal{Q}$ wrt
$\mathcal{ELHIF}^{\bot}$-ontologies in normal form just as in the non-temporal
case; cf. [25, Lemma 10]. However, the normal form enables us to easily lift
several results obtained for ${\cal E\\!\\!\>LIF}^{\bot}$ [25] to the two-
dimensional setting. An $\mathcal{ELHIF}^{\bot}$-ontology is in _normal form_
if every concept inclusion takes one of the following forms:

$A\sqsubseteq\exists R.A^{\prime},\quad\quad\exists R.A\sqsubseteq
A^{\prime},\quad\quad A\sqcap A^{\prime}\sqsubseteq B,$

where $A,A^{\prime}$ are concept names or $\top$, $B$ is a concept name or
$\bot$, and $R$ is a role. It has been shown that ${\cal E\\!\\!\>LIF}^{\bot}$
ontologies in normal form have polynomially-bounded generalisations [25,
Theorem 13], and using the same techniques it can be proved that the same is
true for $\mathcal{ELHIF}^{\bot}$ ontologies.

######  Theorem 20.

Let $\mathcal{L}$ be an ontology language that contains only
$\mathcal{ELHIF}^{\bot}$-onto-logies in normal form and that admits polysize
frontiers within ELIQ that can be computed. Then:

$(i)$

The class of safe queries in
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\text{ELIQ})$
is polynomial query learnable wrt $\mathcal{L}$-ontologies using membership
queries.

$(ii)$

The class
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\text{ELIQ})$
is polynomial query learnable wrt $\mathcal{L}$-ontologies using membership
queries if the learner knows the temporal depth of the target query in
advance.

$(iii)$

The class
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond}}(\text{ELIQ})$
is polynomial query learnable wrt $\mathcal{L}$-ontologies using membership
queries.

If $\mathcal{L}$ further admits polynomial-time instance checking and
polynomial-time computable frontiers within ELIQ, then in $(ii)$ and $(iii)$,
polynomial query learnability can be replaced by polynomial-time learnability.
If, in addition, meet-reducibility of ELIQs wrt $\mathcal{L}$-ontologies can
be decided in polynomial time, then also in $(i)$ polynomial query
learnability can be replaced by polynomial-time learnability.

Let $\mathcal{L}$ be an ontology language as in the theorem. We start with
proving $(i)$. Let ${\bm{q}}_{T}$ be the target query, $\mathcal{O}$ an
$\mathcal{L}$-ontology, and $\mathcal{D},a$ be a positive example with
$\mathcal{D}=\mathcal{A}_{0}\ldots\mathcal{A}_{n}$ and $\mathcal{D}$
satisfiable wrt $\mathcal{O}$. We modify $\mathcal{D}$ in a number of steps
such that in the end $\mathcal{D}$ viewed as a two-dimensional query is
equivalent to ${\bm{q}}_{T}$. As a general proviso we assume that at all times
each $\mathcal{A}_{i}$ (viewed as CQ) is $\mathcal{O}$-saturated; this is
without loss of generality since instance checking wrt
$\mathcal{ELHIF}^{\bot}$-ontologies is decidable [47]. By Lemma 5, we can
assume ${\bm{q}}_{T}$ to be in normal form. We further assume ${\bm{q}}_{T}$
to be of shape (9):

$\displaystyle{\bm{q}}_{T}={\bm{q}}_{0}\mathcal{R}_{1}{\bm{q}}_{1}\dots\mathcal{R}_{n}{\bm{q}}_{n},$

As ${\bm{q}}_{T}$ is safe, it does not have lone conjuncts.

#### Step 1.

We first aim to find a temporal data instance which is _tree-shaped_ , meaning
that in $\mathcal{D}=\mathcal{A}_{0}\ldots\mathcal{A}_{n}$ each
$\mathcal{A}_{i}$ is tree-shaped. To achieve this, we exhaustively apply the
following rules Unwind and Minimise with a preference given to Minimise. A
cycle in a data instance is a sequence
$R_{1}(a_{1},a_{2}),\ldots,R_{n}(a_{n},a_{1})$ of distinct atoms such that
$a_{1},\ldots,a_{n}$ are distinct.

Minimise. If there is some $i$ and some individual
$b\in\textit{ind}(\mathcal{A}_{i})$ such that $\mathcal{D}^{\prime},a$ is a
positive example where $\mathcal{D}^{\prime}$ is obtained from $\mathcal{D}$
by dropping from $\mathcal{A}_{i}$ all atoms that mention $b$, then replace
$\mathcal{D}$ with $\mathcal{D}^{\prime}$.

Unwind. Choose an atom $R(a,b)\in\mathcal{A}_{i}$ that is part of a cycle.
Obtain $\mathcal{A}_{i}^{\prime}$ by first adding a disjoint copy
$\mathcal{A}^{\prime}_{i}$ of $\mathcal{A}_{i}$ to $\mathcal{A}_{i}$ and let
$a^{\prime},b^{\prime}$ be the copies of $a,b$ in $\mathcal{A}_{i}^{\prime}$.
Then replace all atoms $S(a,b)$ (respectively, $S(a^{\prime},b^{\prime})$) by
$S(a,b^{\prime})$ (respectively, $S(a^{\prime},b)$), for all roles $S$.

It is clear that the resulting temporal data instance is tree-shaped as
required.

#### Step 2.

Repeat the following until $\mathcal{D}$ stabilizes. If there is some $i$ such
that $\mathcal{D}^{\prime},a$ is a positive example where
$\mathcal{D}^{\prime}$ is obtained from $\mathcal{D}$ by dropping
$\mathcal{A}_{i}$ from $\mathcal{D}$, then replace $\mathcal{D}$ with
$\mathcal{D}^{\prime}$. Clearly, the length of the resulting temporal data
sequence $\mathcal{D}$ is at least as large as the number of occurrences of
$suc$ and $<$ in ${\bm{q}}_{T}$. Finally, observe that every root
$\mathcal{O}$-homomorphism $h:{\bm{q}}_{T}\to\mathcal{D}$ is block surjective
for the block size $b:=\max(\mathcal{D})+1$ (note that $\mathcal{D}$ has only
one block for this $b$).

#### Step 3.

In this step, we ‘close’ $\mathcal{D}$ under applications of the Rules (a)–(e)
used in Lemma 6. Formally, consider the following Rule 3(x), for
$\text{x}\in\\{\text{a,b,c,d,e}\\}$.

  1. 3(x)

Let $\mathcal{D}^{\prime}$ be a data instance obtained from $\mathcal{D}$ by
applying Rule (x). If $\mathcal{D}^{\prime},a$ is a positive example, replace
$\mathcal{D}$ with the result of the exhaustive application of Minimise to
$\mathcal{D}^{\prime}$.

We first apply 3(b) and 3(c) until $\mathcal{D}$ stabilises. Then, we
exhaustively apply 3(a), 3(d), and 3(e) giving preference to 3(a).

After Step 3, $\mathcal{D}$ satisfies that, if $\mathcal{D}^{\prime}$ is the
result of an application of Rules (a)–(e), then $\mathcal{D}^{\prime},a$ is
not a positive example.

#### Step 4.

In this step, we take care of lone conjuncts in $\mathcal{D}$ by applying
$(\ast)$ below as long as $\mathcal{D}$ contains one. Recall that, by Lemma 3,
a CQ ${\bm{q}}$ is meet-reducible iff $|\mathcal{F}_{\bm{q}}|\geq 2$ provided
that ${\bm{q}}^{\prime}\not\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$, for
all distinct
${\bm{q}}^{\prime},{\bm{q}}^{\prime\prime}\in\mathcal{F}_{\bm{q}}$. We can
compute such a minimal frontier $\mathcal{F}_{\bm{q}}$ by first computing any
frontier $F$ (which is possible by assumption) and then exhaustively removing
from $F$ queries ${\bm{q}}^{\prime\prime}$ such that
${\bm{q}}^{\prime}\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$ for some
${\bm{q}}^{\prime}\in F$ with ${\bm{q}}^{\prime}\neq{\bm{q}}^{\prime\prime}$.
Note that the test
${\bm{q}}^{\prime}\models_{\mathcal{O}}{\bm{q}}^{\prime\prime}$ is decidable
for $\mathcal{ELHIF}^{\bot}$-ontologies [14].

  * $(\ast)$

Choose a primitive block $\emptyset^{b}\mathcal{A}\emptyset^{b}$ in
$\mathcal{D}$ such that $|\mathcal{F}_{\bm{q}}|\geq 2$, for the ELIQ
${\bm{q}}$ with $\mathcal{A}=\hat{\bm{q}}$. Let
$\mathcal{F}_{\bm{q}}=\\{{\bm{q}}_{1},\ldots,{\bm{q}}_{\ell}\\}$ and
$w=\hat{\bm{q}}_{1}\emptyset^{b}\hat{\bm{q}}_{2}\emptyset^{b}\dots\hat{\bm{q}}_{\ell}\emptyset^{b}$.
Denote with $\mathcal{D}_{k}$ the result of replacing
$\emptyset^{b}\mathcal{A}\emptyset^{b}$ in $\mathcal{D}$ with
$\emptyset^{b}(w)^{k}$. Then identify some $i\geq 1$ such that
$\mathcal{D}_{i},a$ is a positive example, by using membership queries for
$i=1,2,\dots$. Notice that this requires only polynomially-many membership
queries as $\mathcal{D}_{k},a$ is a positive example for $k=|{\bm{q}}_{T}|$,
and that all queries are of polynomial size since $\mathcal{F}_{\bm{q}}$ is of
polynomial size. Replace $\mathcal{D}$ with the result of exhaustively
applying Rule 3(a) to $\mathcal{D}_{i}$ and subsequently shortening blocks
$\emptyset^{d}$ for $d>b$ to $\emptyset^{b}$.

Let $\mathcal{D}$ be the result of Step 4. It is routine to verify that
3(a)–3(e) are not applicable, that $\mathcal{D}$ is $b$-normal, and that
$\mathcal{D}$ is without lone conjuncts wrt $\mathcal{O}$ within
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\text{ELIQ})$.
By Lemma 6, any root $\mathcal{O}$-homomorphism is a root
$\mathcal{O}$-isomorphism. Thus, the algorithm has identified all blocks in
the following sense. Suppose that
${\bm{q}}_{T}={\bm{q}}_{0}\mathcal{R}_{1}{\bm{q}}_{1}\ldots\mathcal{R}_{m}{\bm{q}}_{m}$
is a sequence of blocks
${\bm{q}}_{i}=\bm{r}_{0}^{i}\ldots\bm{r}_{\ell_{i}}^{i}$ and

$\mathcal{D}=\mathcal{D}_{0}\emptyset^{b}\mathcal{D}_{1}\ldots\emptyset^{b}\mathcal{D}_{n}\text{
where }\mathcal{D}_{i}=\mathcal{A}_{0}^{i}\ldots\mathcal{A}_{k_{i}}^{i}.$

Then $m=n$ and each block $\mathcal{D}_{i}$ in $\mathcal{D}$ is isomorphic to
${\bm{q}}_{i}$, that is, $\ell_{i}=k_{i}$ and
$\hat{\bm{r}}_{j}^{i}=\mathcal{A}_{j}^{i}$, for all $i,j$ with $0\leq i\leq n$
and $0\leq j\leq k_{i}$. It is unclear, however, whether the $\mathcal{R}_{i}$
are (a single) $\leq$ or a sequence of $<$. This is resolved in the final
step.

#### Step 5.

We determine $\mathcal{R}_{i+1}$, for each $i$ with $0\leq i<n$, as follows:

  * •

If $\bm{r}^{i}_{k_{i}}$ and $\bm{r}^{i+1}_{0}$ are compatible wrt
$\mathcal{O}$ and $\mathcal{D}_{i},a$ with
$\mathcal{D}_{i}=\mathcal{D}_{0}\emptyset^{b}\ldots\emptyset^{b}\mathcal{D}_{i}\Join\mathcal{D}_{i+1}\emptyset^{b}\ldots\emptyset^{b}\mathcal{D}_{n}$
($\Join$ defined as in the proof of Theorem 15) is a positive example, then
$\mathcal{R}_{i+1}$ is $\leq$. Otherwise, let $s$ be minimal such that
$\mathcal{D}^{\prime}_{i},a$ is a positive example for
$\mathcal{D}^{\prime}_{i}=\mathcal{D}_{0}\emptyset^{b}\ldots\emptyset^{b}\mathcal{D}_{i}\emptyset^{s}\mathcal{D}_{i+1}\emptyset^{b}\ldots\emptyset^{b}\mathcal{D}_{n}$.
Then, $\mathcal{R}_{i+1}$ is a sequence of $s$ times $<$.

We show now that indeed the returned query is equivalent to ${\bm{q}}_{T}$ and
that the algorithm issues only polynomially-many membership queries. We
analyse Steps 1–5 separately.

For Step 1, we lift the notion of generalisation sequences to temporal data
instances. For the sake of convenience, we treat the data instances in the
time points as CQs. A sequence $\mathcal{D}_{1},\ldots$ of temporal data
instances is a _generalisation sequence towards ${\bm{q}}$ wrt $\mathcal{O}$_
if for all $i\geq 1$:

  * •

$\mathcal{D}_{i+1}$ is obtained from $\mathcal{D}_{i}$ by modifying one non-
temporal CQ $\bm{r}_{j}$ in $\mathcal{D}_{i}$ to $\bm{r}_{j}^{\prime}$ such
that $\bm{r}_{j}\models_{\mathcal{O}}\bm{r}_{j}^{\prime}$ and
$\bm{r}_{j}^{\prime}\not\models_{\mathcal{O}}\bm{r}_{j}$;

  * •

$\mathcal{O},\mathcal{D}_{i}\models{\bm{q}}$ for all $i\geq 1$.

######  Lemma 7.

Let ${\bm{q}}$ be a CQ. The length of a generalisation sequence
$\mathcal{D}_{1},\ldots,\mathcal{D}_{n}$ towards ${\bm{q}}$ wrt $\mathcal{O}$
such that all $\mathcal{D}_{i}$ are satisfiable wrt $\mathcal{O}$,
$\mathcal{O}$-saturated, and $({\bm{q}},\mathcal{O})$-minimal is bounded by a
polynomial in the size of ${\bm{q}}$, $\mathcal{O}$, and $\mathcal{D}_{1}$.

###### Proof.

Consider a time point $i$ and let $\bm{r}_{1},\bm{r}_{2},\ldots$ be the
sequence of different queries at time point $i$ that occur in the
generalisation sequence, that is,
$\bm{r}_{j}\models_{\mathcal{O}}\bm{r}_{j+1}$ and
$\bm{r}_{j+1}\not\models_{\mathcal{O}}\bm{r}_{j}$, for each $j$. Let $h$ be a
root homomorphism from ${\bm{q}}$ to $\mathcal{D}_{n}$ and let $I$ be the set
of all $t$ with $h(t)=i$. (By construction, $h$ is a root homomorphism from
${\bm{q}}$ to all $\mathcal{D}_{j}$.) Consider
${\bm{q}}^{\prime}=\bigwedge_{i\in I}{\bm{q}}_{i}$. Clearly,
$\bm{r}_{1},\bm{r}_{2},\ldots,$ is a generalisation sequence towards
${\bm{q}}^{\prime}$ wrt $\mathcal{O}$. Since all $\mathcal{D}_{j}$ are
satisfiable wrt $\mathcal{O}$, $\mathcal{O}$-saturated and
$({\bm{q}},\mathcal{O})$-minimal, it follows that in particular, all
$\bm{r}_{1},\bm{r}_{2},\ldots$ are satisfiable wrt $\mathcal{O}$,
$\mathcal{O}$-saturated and $({\bm{q}},\mathcal{O})$-minimal. By [25, Theorem
13], the length of $\bm{r}_{1},\bm{r}_{2},\ldots$ is bounded polynomially.
Since there are only $\max(\mathcal{D}_{1})$ time points to consider, the
sequence $\mathcal{D}_{1},\mathcal{D}_{2},\ldots,\mathcal{D}_{n}$ is
polynomially bounded. ∎

Now, let $\mathcal{D}_{1},\mathcal{D}_{2},\ldots$ be the sequence of temporal
data instances that Unwind is applied to during Step 1. Clearly, all these
queries are $({\bm{q}}_{T},\mathcal{O})$-minimal (recall that we give
preference to Minimise) and $\mathcal{O}$-saturated. Since an application of
Minimise decreases the overall number of individuals in the instance, there
are only polynomially-many applications of Minimise between $\mathcal{D}_{i}$
and $\mathcal{D}_{i+1}$. In the proof of Lemma 14 in [25], it is shown that
the operation Unwind222Unwind is called Double Cycle in [25]. applied to a
$({\bm{q}}_{T},\mathcal{O})$-minimal CQ ${\bm{q}}$ leads to a strictly weaker
CQ ${\bm{q}}^{\prime}$, that is,
${\bm{q}}\models_{\mathcal{O}}{\bm{q}}^{\prime}$, but not vice versa. This
applies here as well, and implies that
$\mathcal{D}_{1},\mathcal{D}_{2},\ldots$ is a generalisation sequence towards
${\bm{q}}_{T}$ wrt $\mathcal{O}$. Applying Lemma 7 yields that Step 1
terminates in time polynomial in the size of ${\bm{q}}_{T}$, $\mathcal{O}$,
and $\mathcal{D}$.

It should be clear that only polynomially-many (in $\mathcal{D}$) membership
queries are asked in Step 2.

We next analyse Step 3, starting with Rules 3(b) and 3(c). First note that the
number of applications of Rules 3(b) and 3(c) is bounded by the number of $<$
and $\leq$ in ${\bm{q}}_{T}$. To see this, we inductively show that Rules 3(b)
and 3(c) preserve the fact that every root $\mathcal{O}$-homomorphism
$h:{\bm{q}}_{T}\to\mathcal{D}$ is block surjective. As noted above, this
certainly holds before Step 3. Suppose now that $\mathcal{D}^{\prime}$ is
obtained by a single application of 3(b) or 3(c) to $\mathcal{D}$, and that
there is a root $\mathcal{O}$-homomorphism that is not block surjective. Then
we can easily construct a non-block surjective homomorphism from
${\bm{q}}_{T}$ to $\mathcal{D}$, a contradiction. Applications of Minimise
also preserve the claim.

We next analyse Rules 3(a), 3(d), and 3(e). Let
$\mathcal{D}_{1},\mathcal{D}_{2},\ldots$ be a sequence of databases obtained
by a sequence of applications of 3(a). Clearly,
$\mathcal{D}_{1},\mathcal{D}_{2},\ldots$ is a generalisation sequence towards
${\bm{q}}_{T}$ wrt $\mathcal{O}$ such that all $\mathcal{D}_{i}$ are
satisfiable wrt $\mathcal{O}$, $\mathcal{O}$-saturated, and
$({\bm{q}}_{T},\mathcal{O})$-minimal. By Lemma 7, the length of the sequence
is polynomially bounded. Further note that applications of 3(a) preserve that
every root $\mathcal{O}$-homomorphism is block surjective and that 3(b) and
3(c) remain not applicable.

Next consider an application of 3(d) to a temporal data instance $\mathcal{D}$
where 3(a) is not applicable and such that every root
$\mathcal{O}$-homomorphism is block surjective. Let $\mathcal{D}^{\prime}$ be
the result. Since 3(a) is not applicable, every root
$\mathcal{O}$-homomorphism to $\mathcal{D}^{\prime}$ must also be block
surjective. Thus, the number of applications of 3(d) is bounded by the number
of $<$ and $\leq$ in ${\bm{q}}_{T}$. The same argument works for 3(e). It is
readily seen that 3(b) and 3(c) are still not applicable, thus none of the
rules is applicable to $\mathcal{D}$. Overall, we obtain a polynomial number
of rule applications. This finishes the analysis of Step 3.

Consider now Step 4. As noted in $(\ast)$, identifying the right
$\mathcal{D}_{i}$ needs only polynomially many membership queries (despite the
fact that deciding meet-reducibility might require more time). Since
exhaustive application of 3(a) requires only polynomial time, a single
application of $(\ast)$ requires only polynomially many membership queries.
Moreover, using the fact that 3(a) is not applicable before application of
$(\ast)$ one can show that the number of ‘gaps’ is increased and that the rule
preserves that every root $\mathcal{O}$-homomorphism is block surjective.
Hence, $(\ast)$ is applied at most once for each $\leq$ in ${\bm{q}}_{T}$.

It remains to analyse the running time of Step 5. Clearly, only linearly many
(in the size of ${\bm{q}}_{T}$) membership queries are asked. To finish the
argument, we only note that $\mathcal{ELHIF}^{\bot}$ admits tractable
containment reduction and that satisfiability wrt
$\mathcal{ELHIF}^{\bot}$-ontologies is decidable.

We argue next that the above algorithm runs in polynomial time if
$\mathcal{L}$ additionally admits polynomial-time instance checking,
polynomial-time computable frontiers, and meet-reducibility of ELIQs wrt
$\mathcal{L}$-ontologies can be decided in polynomial time. First note that
$\mathcal{O}$-saturation of $\mathcal{D}$ (which is assumed throughout the
algorithm) can be established in polynomial time via instance checking. Then
observe that, in Step 4, a (not necessarily minimal) frontier
$\mathcal{F}_{\bm{q}}$ can be computed in polynomial time and meet-
reducibility can also be decided in polynomial time, by assumption. Together
with the analysis of Step 4 above, this yields that Step 4 needs only
polynomial time. Finally observe that also Step 5 runs in polynomial time
since the tests for satisfiability can be reduced to (polynomial time)
instance checking.

It remains to prove Points $(ii)$ and $(iii)$ from Theorem 20. The learning
algorithm for Point $(ii)$ is similar to the algorithm provided above, but
with a modified Step 4 since in this case ${\bm{q}}_{T}$ might have lone
conjuncts and possibly more than one variable from
$\textit{var}({\bm{q}}_{T})$ is mapped to the same time point in
$\mathcal{D}$. Let $T$ be the temporal depth of the target query.

#### Step 4′.

In this step, we apply $(\ast^{\prime})$ until $\mathcal{D}$ stabilises.

  * $(\ast^{\prime})$

Choose a primitive block $\emptyset^{b}\mathcal{A}\emptyset^{b}$ and an ELIQ
${\bm{q}}$ with $\mathcal{A}=\hat{\bm{q}}$. Let
$\mathcal{F}_{\bm{q}}=\\{{\bm{q}}_{1},\ldots,{\bm{q}}_{\ell}\\}$ and
$w=\hat{\bm{q}}_{1}\emptyset^{b}\hat{\bm{q}}_{2}\emptyset^{b}\dots\hat{\bm{q}}_{\ell}\emptyset^{b}$.
Let $\mathcal{D}^{\prime}$ be the result of replacing
$\emptyset^{b}\mathcal{A}\emptyset^{b}$ in $\mathcal{D}$ with
$\emptyset^{b}(w)^{T}$. If $\mathcal{D}^{\prime},a$ is a positive example,
then replace $\mathcal{D}$ with the result of exhaustively applying Rule 3(a)
to $\mathcal{D}^{\prime}$ and subsequently shortening blocks $\emptyset^{d}$
for $d>b$ to $\emptyset^{b}$.

Let $\mathcal{D}$ be the result of Step 4. It is routine to verify that
3(a)–3(e) are not applicable. The following can be proven similar to Lemma 6.

######  Lemma 8.

Let $\mathcal{O}$ and ${\bm{q}}_{T}$ be as above. Let $b$ exceed the number of
$\Diamond$ and $\bigcirc$ in ${\bm{q}}_{T}$, and let $\mathcal{D}$ be
$b$-normal. If Rules 3(a)–(e) and $(\ast^{\prime})$ are not applicable, then
any root $\mathcal{O}$-homomorphim $h\colon{\bm{q}}\rightarrow\mathcal{D}$ is
a root $\mathcal{O}$-isomorphism.

As an immediate consequence, after Step 4′ modified algorithm has identified
all blocks in ${\bm{q}}_{T}$ as described above and it remains to apply Step
5.

The learning algorithm for Point $(iii)$ is a similar modification. Note that
for the query class
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(ELIQ)$,
after Step 2, we know _exactly_ the temporal depth of ${\bm{q}}_{T}$, namely
$b$. This $b$ can then be used in place of $T$ in $(\ast^{\prime})$ above.
This finishes the proof of Theorem 20. ∎

We apply Theorem 20 to concrete ontology languages, namely $\textsl{DL-
Lite}_{\mathcal{F}}^{-}$ and $\textsl{DL-Lite}_{\mathcal{H}}$. Let us denote
by $\textsl{DL-Lite}_{\cal{F}}^{-\text{nf}}$ and $\textsl{DL-
Lite}_{\mathcal{H}}^{\text{nf}}$ the set of $\textsl{DL-
Lite}_{\mathcal{F}}^{-}$ and $\textsl{DL-Lite}_{\mathcal{H}}$-ontologies in
normal form, respectively.

######  Theorem 21.

The following learnability results hold:

$(i)$

The class of safe queries in
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\text{ELIQ})$
is polynomial query learnable wrt $\textsl{DL-
Lite}_{\mathcal{H}}^{\text{nf}}$-ontologies using membership queries and
polynomial-time learnable wrt $\textsl{DL-
Lite}_{\mathcal{F}}^{-\text{nf}}$-ontologies using membership queries.

$(ii)$

The class
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\text{ELIQ})$
is polynomial-time learnable wrt both $\textsl{DL-
Lite}_{\cal{F}}^{{-}\text{nf}}$ and $\textsl{DL-
Lite}_{\mathcal{H}}^{\text{nf}}$-ontologies using membership queries if the
learner knows the temporal depth of the target query in advance.

$(iii)$

The class
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond}}(\text{ELIQ})$
is polynomial query learnable wrt both $\textsl{DL-
Lite}_{\cal{F}}^{{-}\text{nf}}$ and $\textsl{DL-
Lite}_{\mathcal{H}}^{\text{nf}}$-ontologies using membership queries.

###### Proof.

The theorem is a direct consequence of Theorem 20 and the fact that the
considered ontology languages satisfy all conditions mentioned in that
theorem. Most importantly:

  * •

$\textsl{DL-Lite}_{\cal{F}}$ admits polynomial-time instance checking [17] and
$\textsl{DL-Lite}_{\cal{F}}^{-}$ admits polynomial-time computable frontiers
[26]. Moreover, meet-reducibility in $\textsl{DL-Lite}_{\cal{F}}^{-}$ is
decidable in polynomial time, by Lemma 4.

  * •

$\textsl{DL-Lite}_{\cal{H}}$ admits polynomial-time instance checking [17] and
admits polynomial-time computable frontiers [26].

This completes the proof. ∎

We repeat that we conjecture that Theorem 21 also holds for DL-Lite-ontologies
not in normal form, but leave an investigation of this issue for future work.
We also leave for future work whether or not
$\textsl{LTL}_{p}^{\smash{\raisebox{1.0pt}{$\scriptscriptstyle\bigcirc$}\Diamond\Diamond_{r}}}(\text{ELIQ})$
is even polynomial-_time_ learnable wrt $\textsl{DL-
Lite}_{\mathcal{H}}$-ontologies using membership queries. For this to be true,
it suffices to show that meet-reducibility of _$({\bm{q}}_{T},\mathcal{O})$
-minimal_ ELIQs is decidable in polynomial time (but recall that deciding that
for general ELIQs is NP-complete, by Lemma 4).

##  7 Outlook

Many interesting and challenging problems remain to be addressed. We discuss a
few. (1) Is it possible to overcome some of our negative results for unique
characterisability by admitting some form of infinite (but finitely
presentable) examples? Some results in this direction without ontologies are
obtained in [41]. (2) We focussed on temporal queries based on ELIQs but did
not consider in any detail interesting subclasses such as the class ELQ of
queries equivalent to $\mathcal{EL}$-concepts. We conjecture that in this case
some new results on unique characterisability and learnability using
membership queries can be obtained. (3) We did not consider learnability using
membership queries of temporal queries with until. In fact, it remains
completely open in how far our characterisability results for these queries
can be exploited to obtain polynomial query (or time) learnability results.
(4) We only considered queries in which no description logic operators are
applied to temporal operator, and within this class only path queries. This is
motivated by the negative results obtained in [22] where it is shown that (i)
applying existential restrictions $\exists P$ to queries with $\Diamond$ and
$\bigcirc$ quickly leads to non characterisability and (ii) that even without
DL-operators and without ontology, branching queries with $\Diamond$ can often
not be uniquely characterised. Still, there should be scope for useful
positive characterisation results.

## References

  * [1] Fides Aarts and Frits Vaandrager.  Learning i/o automata.  In Proc. of CONCUR, pages 71–85. Springer, 2010.
  * [2] Bogdan Alexe, Balder ten Cate, Phokion G. Kolaitis, and Wang Chiew Tan.  Characterizing schema mappings via data examples.  ACM Trans. Database Syst., 36(4):23, 2011.
  * [3] Dana Angluin.  Learning regular sets from queries and counterexamples.  Inf. Comput., 75(2):87–106, 1987.
  * [4] Dana Angluin.  Queries and concept learning.  Mach. Learn., 2(4):319–342, 1987.
  * [5] Marcelo Arenas and Gonzalo I. Diaz.  The exact complexity of the first-order logic definability problem.  ACM Trans. Database Syst., 41(2):13:1–13:14, 2016.
  * [6] Alessandro Artale, Diego Calvanese, Roman Kontchakov, and Michael Zakharyaschev.  The DL-Lite family and relations.  J. Artif. Intell. Res., 36:1–69, 2009.
  * [7] Alessandro Artale, Roman Kontchakov, Alisa Kovtunova, Vladislav Ryzhikov, Frank Wolter, and Michael Zakharyaschev.  Ontology-mediated query answering over temporal data: A survey.  In Proc. of TIME, pages 1:1–1:37. Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2017.
  * [8] Alessandro Artale, Roman Kontchakov, Alisa Kovtunova, Vladislav Ryzhikov, Frank Wolter, and Michael Zakharyaschev.  First-order rewritability of ontology-mediated queries in linear temporal logic.  Artif. Intell., 299:103536, 2021.
  * [9] Alessandro Artale, Roman Kontchakov, Alisa Kovtunova, Vladislav Ryzhikov, Frank Wolter, and Michael Zakharyaschev.  First-order rewritability and complexity of two-dimensional temporal ontology-mediated queries.  J. Artif. Intell. Res., 75:1223–1291, 2022.
  * [10] Alessandro Artale, Roman Kontchakov, Vladislav Ryzhikov, and Michael Zakharyaschev.  A cookbook for temporal conceptual data modelling with description logics.  ACM Trans. Comput. Log., 15(3):25:1–25:50, 2014.
  * [11] Franz Baader, Stefan Borgwardt, and Marcel Lippmann.  Temporal query entailment in the description logic SHQ.  J. Web Semant., 33:71–93, 2015.
  * [12] Franz Baader, Ian Horrocks, Carsten Lutz, and Ulrike Sattler.  An Introduction to Description Logics.  Cambridge University Press, 2017.
  * [13] Pablo Barceló and Miguel Romero.  The complexity of reverse engineering problems for conjunctive queries.  In Proc. of ICDT, pages 7:1–7:17, 2017.
  * [14] Meghyn Bienvenu, Peter Hansen, Carsten Lutz, and Frank Wolter.  First order-rewritability and containment of conjunctive queries in Horn description logics.  In Proc. of IJCAI, pages 965–971, 2016.
  * [15] Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter.  Ontology-based data access: A study through disjunctive datalog, CSP, and MMSNP.  ACM Trans. Database Syst., 39(4):33:1–33:44, 2014.
  * [16] Stefan Borgwardt and Veronika Thost.  Temporal query answering in the description logic EL.  In Proc. of IJCAI, pages 2819–2825. AAAI Press, 2015.
  * [17] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati.  Tractable reasoning and efficient query answering in description logics: The DL-Lite family.  J. Autom. Reasoning, 39(3):385–429, 2007.
  * [18] Alberto Camacho and Sheila A. McIlraith.  Learning interpretable models expressed in linear temporal logic.  In Proc. of ICAPS, pages 621–630. AAAI Press, 2019.
  * [19] Sofia Cassel, Falk Howar, Bengt Jonsson, and Bernhard Steffen.  Active learning for extended finite state machines.  Formal Aspects Comput., 28(2):233–263, 2016.
  * [20] C.C. Chang and H. Jerome Keisler.  Model Theory.  Elsevier, 1998.
  * [21] Nathanaël Fijalkow and Guillaume Lagarde.  The complexity of learning linear temporal formulas from examples.  CoRR, abs/2102.00876, 2021.
  * [22] Marie Fortin, Boris Konev, Vladislav Ryzhikov, Yury Savateev, Frank Wolter, and Michael Zakharyaschev.  Unique characterisability and learnability of temporal instance queries.  In Proc. of KR, 2022.
  * [23] Marie Fortin, Boris Konev, Vladislav Ryzhikov, Yury Savateev, Frank Wolter, and Michael Zakharyaschev.  Reverse engineering of temporal queries mediated by LTL ontologies.  In Proceedings of IJCAI, 2023.
  * [24] Maurice Funk, Jean Christoph Jung, and Carsten Lutz.  Actively learning concepts and conjunctive queries under ELr-ontologies.  In Proc. of IJCAI, pages 1887–1893. ijcai.org, 2021.
  * [25] Maurice Funk, Jean Christoph Jung, and Carsten Lutz.  Exact learning of ELI queries in the presence of dl-lite-horn ontologies.  In Proc. of DL. CEUR-WS.org, 2022.
  * [26] Maurice Funk, Jean Christoph Jung, and Carsten Lutz.  Frontiers and exact learning of ELI queries under dl-lite ontologies.  In Proc. of IJCAI, pages 2627–2633, 2022.
  * [27] Maurice Funk, Jean Christoph Jung, Carsten Lutz, Hadrien Pulcini, and Frank Wolter.  Learning description logic concepts: When can positive and negative examples be separated?  In Proc. of IJCAI, pages 1682–1688, 2019.
  * [28] Víctor Gutiérrez-Basulto, Jean Christoph Jung, and Roman Kontchakov.  Temporalized EL ontologies for accessing temporal data: Complexity of atomic queries.  In Proc. of IJCAI, pages 1102–1108. IJCAI/AAAI Press, 2016.
  * [29] Víctor Gutiérrez-Basulto, Jean Christoph Jung, and Leif Sabellek.  Reverse engineering queries in ontology-enriched systems: The case of expressive Horn description logic ontologies.  In Proc. of IJCAI-ECAI, 2018.
  * [30] Falk Howar and Bernhard Steffen.  Active automata learning in practice - an annotated bibliography of the years 2011 to 2016.  In Machine Learning for Dynamic Software Analysis: Potentials and Limits, International Dagstuhl Seminar 16172, volume 11026 of Lecture Notes in Computer Science, pages 123–148. Springer, 2018.
  * [31] Jean Christoph Jung, Carsten Lutz, Hadrien Pulcini, and Frank Wolter.  Logical separability of labeled data examples under ontologies.  Artif. Intell., 313:103785, 2022.
  * [32] Stanislav Kikot, Roman Kontchakov, and Michael Zakharyaschev.  On (in)tractability of OBDA with OWL 2 QL.  In Riccardo Rosati, Sebastian Rudolph, and Michael Zakharyaschev, editors, Proc. of DL. CEUR-WS.org, 2011.
  * [33] Phokion G. Kolaitis.  Schema Mappings and Data Examples: Deriving Syntax from Semantics (Invited Talk).  In Proc. of FSTTCS, volume 13, pages 25–25, Dagstuhl, Germany, 2011. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [34] Boris Konev, Carsten Lutz, Ana Ozaki, and Frank Wolter.  Exact learning of lightweight description logic ontologies.  J. Mach. Learn. Res., 18:201:1–201:63, 2017.
  * [35] Jens Lehmann and Pascal Hitzler.  Concept learning in description logics using refinement operators.  Machine Learning, 78:203–250, 2010.
  * [36] Caroline Lemieux, Dennis Park, and Ivan Beschastnikh.  General ltl specification mining (t).  In Proc. of ASE, pages 81–92. IEEE, 2015.
  * [37] Denis Mayr Lima Martins.  Reverse engineering database queries from examples: State-of-the-art, challenges, and research opportunities.  Inf. Syst., 83:89–100, 2019.
  * [38] Ralph McKenzie.  Equational bases and nonmodular lattice varieties.  Transactions of the American Mathematical Society, 174:1–43, 1972\.
  * [39] Daniel Neider and Ivan Gavran.  Learning linear temporal properties.  In Proc. of FMCAD, pages 1–10. IEEE, 2018.
  * [40] Ana Ozaki.  Learning description logic ontologies: Five approaches. where do they stand?  Künstliche Intell., 34(3):317–327, 2020.
  * [41] Patric Sestic.  Unique characterisability of linear temporal logic.  Msc, University of Amsterdam, 2023.
  * [42] Muzammil Shahbaz and Roland Groz.  Inferring mealy machines.  In Proc. of FM, pages 207–222. Springer, 2009.
  * [43] Slawek Staworko and Piotr Wieczorek.  Characterizing XML twig queries with examples.  In Proc. of ICDT, pages 144–160, 2015.
  * [44] Balder ten Cate and Victor Dalmau.  Conjunctive queries: Unique characterizations and exact learnability.  ACM Trans. Database Syst., 47(4):14:1–14:41, 2022.
  * [45] Balder ten Cate, Víctor Dalmau, and Phokion G. Kolaitis.  Learning schema mappings.  ACM Trans. Database Syst., 38(4):28:1–28:31, 2013.
  * [46] Balder ten Cate and Raoul Koudijs.  Characterising modal formulas with examples.  CoRR, abs/2304.06646, 2023.
  * [47] Stephan Tobies.  Complexity results and practical algorithms for logics in knowledge representation.  PhD thesis, RWTH Aachen University, Germany, 2001.
  * [48] Przemysław A. Wałęga, Bernardo Cuenca Grau, Mark Kaminski, and Egor V. Kostylev.  DatalogMTL over the Integer Timeline.  In Proc. of KR, pages 768–777, 9 2020.