Information Technology Reference
In-Depth Information
F
=(
F,
ⓦ
)
be the group generated by the automorphisms
f
a
where
f
a
is obtained by item
4 of Theorem 8 for a sequence
Using the above idea, we now define the operation auto. First we let
A
where no
a
i
is located
in the first or the last row. For a team
Y
of
A
,wethenlet
a
listing
a
1
,...,a
k−
1
∈
auto(
Y
):=
{
f
ⓦ
s
|
f
∈F
,s
∈
Y
}
.
Finally, we will show that these two approaches can be combined. We let
X
∗
:= swap(auto(
X
)) and prove by structural induction that (4) follows from
(3). This concludes the sketch of Step 3.
By Theorem 7 and Lemma 1 we now conclude that Theorem 6 holds.
4Con lu on
We have shown that the arity fragments of inclusion logic give rise to a strict ex-
pressivity hierarchy. Earlier, analogous results have been proved for dependence
logic and independence logic. We also observed that the FO(
ↆ
)(
k
∀
)-hierarchy
collapses at a very low level as it is the case with the FO(
↥
c
)(
k
∀
)-hierarchy. How-
ever, the FO(=(
...
))(
k
∀
)-hierarchy is infinite since it can be related to the strict
ESO
f
(
k
)-hierarchy. From the results of [10,4] and this article, we obtain the
following classification for syntactical hierarchies of dependence, independence
and inclusion logic under the lax semantics.
∀
Arity of Dependency Atom
Number of
∀
FO(=(
...
)) strict
FO(=(
...
))(
k
-dep)
<
FO(=(
...
))(
k
+1-dep)
infinite
FO(=(
...
))(
k
)
<
FO(=(
...
))(2
k
+2
∀
∀
)
FO(
↥
c
)
strict
FO(
collapse at 2
FO(
↥
c
)(
k
-ind)
<
FO(
↥
c
)(2
∀
)=FO(
↥
c
)
↥
c
)(
k
+ 1-ind)
FO(
ↆ
)
strict
FO(
collapse at 1
FO(
ↆ
)(
k
-inc)
<
ↆ
)(1
∀
)=FO(
ↆ
)
FO(
ↆ
)(
k
+1-inc)
) captures PTIME in finite ordered models, it would be interest-
ing to investigate syntactical fragments of inclusion logic in that setting. It ap-
pears that then the techniques used in this article would be of no use. Namely,
we cannot hope to construct two ordered models in the style of Theorem 8.
In fixed-point logics, this same question has been studied in the 90s. Imhof
showed in [19] that the arity hierarchy of PFP remains strict in ordered models
(PFP
k
<
O
PFP
k
+1
) by relating the PFP
k
-fragments to the degree hierarchy
within PSPACE. For LFP and IFP, the same question appears to be more dif-
ficult, since both collapse and its negation have strong complexity theoretical
consequences. That is, for both IFP and LFP in ordered models, collapse of
arity hierarchy implies PTIME
<
PSPACE, and infinite arity hierarchy implies
Since FO(
ↆ
