theoremalciaqubthm

In \((, \text{AQ})\) , an OMQ
\(Q=(,q)\)  can be evaluated on a database of cliquewidth
\(k\)  in time \(2^{O(|| \cdot k)} \cdot ||\) . 
Theorem REF  implies that OMQ evaluation in
\((, \text{AQ})\)  is in FPL, and also that it is in linear time in
data complexity when the cliquewidth of databases is bounded by a
constant.
As announced before, we assume here and in all subsequent upper
complexity bounds that a \(k\) -expression \(s_0\)  for is given as
part of the input. In fact, the number of subexpressions of \(s_0\)  must
be \(O(||)\) , a condition that is satisfied by any reasonable
\(k\) -expression for . These assumptions could clearly be dropped
if, given a database of cliquewidth \(k\) , we could compute a
\(k\) -expression that generates (or a sufficient approximation
thereof) in time \(2^{O(k)} \cdot ||\) . It is an open problem
whether this is possible, see
e.g. [1]}. There is, however,
an algorithm that computes, given a database of cliquewidth \(k\) , in
time \(|{adom}()|^3\)  a \(k^{\prime }\) -expression with \(k^{\prime } \le 2^{3k-1}\) 
[2]}. As a consequence, we obtain an analogue of
Theorem REF  that does not require a \(k\) -expression
for to be given and where the time bound is replaced with
\(2^{|Q| \cdot 2^{O(k)}} \cdot ||^3\) . While this no longer yields
FPL, it still yields FPT.
