=Paper=
{{Paper
|id=Vol-2954/paper-15
|storemode=property
|title=Perceptron Operators That Count
|pdfUrl=https://ceur-ws.org/Vol-2954/paper-15.pdf
|volume=Vol-2954
|authors=Pietro Galliani,Oliver Kutz,Nicolas Troquard
|dblpUrl=https://dblp.org/rec/conf/dlog/GallianiKT21
}}
==Perceptron Operators That Count==
https://ceur-ws.org/Vol-2954/paper-15.pdf
Perceptron Operators That Count
Pietro Galliani, Oliver Kutz, and Nicolas Troquard
KRDB Research Centre for Knowledge and Data
Free University of Bozen-Bolzano, Italy
{firstname.lastname}@unibz.it
Abstract. The Felony Score Sheet used in the US State of Florida,
describes various features of a crime and their assigned points. Features
may include ‘possession of cocaine’, or ‘number of caused injuries’. A
threshold must be reached to decide compulsory imprisonment.
In previous research, we have introduced a perceptron operator for knowl-
edge representation languages. With it, concepts can be defined by listing
a concept’s features with associated weights, and a threshold. An individ-
ual belongs to such a concept if the weighted sum of the listed features it
belongs to reaches the threshold. It can capture the concept of compul-
sory imprisonment defined by the Felony Score Sheet. However, it suffers
some limitations in that one must artificially use concepts like ‘caused
one injury’, ‘caused two injuries’, etc, to be able to count.
This paper proposes an extension of the perceptron operator to define
concepts like the compulsory imprisonment from the Felony Score Sheet
faithfully and easily, relying on role-successors counting. We show that
when the weights are non-negative, reasoning in ALC augmented with
the perceptron operator can be reduced to reasoning in ALCQ. Capital-
izing on the recent ALCSCC, we also show that adding the operator to
ALC does not affect the complexity of reasoning in general.
1 Introduction
The Felony Score Sheet used in the State of Florida1 , describes various features
of a crime and their assigned points. A threshold must be reached to decide
compulsory imprisonment. For example, if the primary offence is possession of
cocaine, then it corresponds to 16 points, one victim injury describable as “mod-
erate” corresponds to 18 points, and a failure to appear for a criminal proceeding
results in 4 points. Imprisonment is compulsory if the total is greater than 44
points and not compulsory otherwise.
Copyright © 2021 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
1
http://www.dc.state.fl.us/pub/scoresheet/cpc_manual.pdf (accessed: June.
2021)
2 P. Galliani, O. Kutz, N. Troquard
In [1], we introduced a threshold operator for knowledge representation lan-
guages. If C1 , . . . , Cn are concept expressions, w1 . . . wn ∈ Z are weights, and
t ∈ Z is a threshold, we can introduce a new concept
∇∇t (C1 : w1 . . . Cn : wn )
to designate in an interpretation I those individuals d ∈ ∆I such that:
X
{wi | d ∈ (Ci )I } ≥ t .
We call it the threshold or perceptron operator, or “tooth”. Adding the percep-
tron operator to ALC does not increase the expressivity, since every instance
of the operator can be replaced with an equivalent boolean expression. In [2],
we also showed that adding the perceptron operator to ALC did not affect the
complexity of reasoning. It is ExpTime-complete to do reasoning wrt. a TBox,
as there exists a linear transformation to eliminate the perceptron operator and
obtain an equi-satisfiable ALC formula (although obfuscating the original read-
ability of such defined concepts).
A knowledge base describing the laws of Florida would need to represent this
score sheet as part of its definition of its CompulsoryImprisonment concept, for
instance as
∇44 (CocainePrimary : 16, ModerateInjuries : 18, . . .) .
∇
The Felony Score Sheet is slightly more complicated, though. For instance, 18
points are added for every instance (every count) of a ‘moderate injury victim’.
Of course we can use one concept 1MI, 2MI, 3MI, ... for each number of
moderate injury. With all of them pairwise disjoint and with weights 18, 36, 54,
... we can use
∇44 (CocainePrimary : 16, 1MI : 18, 2MI : 36, 3MI : 54, . . .) .
∇
With each (i + 1)MI a subset of iMI, we can use
∇44 (CocainePrimary : 16, 1MI : 18, 2MI : 18, 3MI : 18, . . .) .
∇
No matter what, one must decide what will be the maximum number of moderate
injuries that are taken into account, introduce new concepts (and possibly axioms
in the TBox), multiply weights, and write them all into a perceptron operator.
Isn’t there some more flexible way to specify this kind of concepts? The
problem at hand is to investigate how to extend the ∇∇ operator to accommodate
the Florida example faithfully and with simplicity. In this paper, we extend the
regular tooth with role-successor counting abilities.
Related work. [3] introduces a description logic (DL) to define EL concepts in an
approximate way, through a graded membership function. The authors introduce
Perceptron Operators That Count 3
threshold concepts to capture the set of individuals belonging to a concept with
a certain degree.
[4] introduces a powerful counting mechanism for description logics. It makes
use of number variables in concepts to say that there is an n, and the number
of role successors is n or more. Adding this mechanism to ALC yields an unde-
cidable DL. [5] presents a general method to use arithmetic reasoning as part
of the inference engine of description logics. Useful counting operators can be
then devised and integrated into DL, and remain decidable. [6] introduces the
extension ALCSCC 2 of ALC with expressive statements of constraints on role
successors (formulas of quantifier-free Boolean algebra with Pressburger arith-
metic (QFBAPA) [7]). It is strictly more expressive than ALCQ; it can, e.g.,
express “has as many sons as daughters”, which ALCQ cannot. Concept satisfi-
ability is ExpTime-complete, and PSpace-complete wrt. an empty TBox (hence
no harder than ALC [8] or ALCQ [9]). [10] extends ALC with global expressive
cardinality constraints. ALCQ with global constraints was already studied in [9].
Adding global cardinality constraints in ALC leads to an NExpTime-complete
complexity for reasoning tasks in general. In ALCSCC, the interpretations are re-
stricted to finite-branching roles. In [11], ALCSCC ∞ is introduced over arbitrary
models. The complexity of reasoning is unaffected. [12] show that combining the
local expressive cardinality constraints of [6] with the global expressive cardinal-
ity constraints of [10] does not impact the complexity.
Outline. We present ALCSCC ∞ in Section 2, and define ALC and ALCQ as
fragments. In Section 3 we introduce our extension of the tooth with counting
capabilities. In Section 4, we show how to embed into ALCQ the logic ALC
equipped with the new perceptron operator where the weights are positive. The
embedding suffices to show that reasoning can be done in 2ExpTime when
the threshold is expressed in binary, and that it is ExpTime-complete when the
threshold is expressed in unary. Section 5 provides an embedding into ALCSCC ∞ ,
showing that ALC equipped with the new perceptron operator is ExpTime-
complete in general. In Section 6, we briefly suggest a further way to extend the
perceptron operator. Section 7 concludes.
2 ALC and its extensions with cardinality restrictions
We present ALCSCC ∞ and its well-known fragments ALC and ALCQ. See [13]
for a general introduction of DL.
QFBAPA∞ . The Description Logic ALCSCC ∞ uses formulas of the quantifier-
free Boolean algebra with Pressburger arithmetic (QFBAPA) to express con-
straints on role successors.
QFBAPA over finite integers is presented in [7]. It is extended with infinity
in [11]. It uses a simple arithmetic with a single (positive) infinity. With z ∈ N,
we stipulate that over N ∪ {∞}, the operator + is commutative, and < is a strict
2
Here, ‘SCC’ stands for ‘Set and Cardinality Constraints’.
4 P. Galliani, O. Kutz, N. Troquard
linear order, = is an equivalence relation, and: ∞ + z = ∞, z < ∞, z ≤ ∞,
0 · ∞ = 0, ∞ + ∞ = ∞, ∞ < 6 ∞.
A QFBAPA∞ formula F is a Boolean combination of set and numerical
constraints like AT .
F ::= AT | AB | ¬F | F ∧ F | F ∨ F
AB ::= B = B | B ⊆ B
AT ::= T = T | T < T
B ::= x | ∅ | U | B ∪ B | B ∩ B | B
T ::= k | K | |B| | T + T | K · T
K ::= 0 | 1 | 2 | . . .
Set terms like B are obtained by applying intersection, union, and complement
to set variables and constants ∅ and U. Set constraints like AB are of the form
B1 = B2 and B1 ⊆ B2 , where B1 , B2 are set terms like B.
Presburger Arithmetic (PA) expressions T are built from variables, non-
negative integer constants from K, and set cardinalities |B|, and then closed
under addition as well as multiplication with non-negative integer constants
from K. They can be used to form the numerical constraints AT , namely of the
form T1 = T2 and T1 < T2 , where T1 , T2 are PA expressions of type T .
The semantics of set terms B is defined using substitutions σ that assign a
set σ(U) to the constant U and subsets of σ(U) to set variables. The evaluation
of all set terms under σ is done using the rules of set theory.
Set constraints of the form AB are evaluated to true or false under σ, also
by using the rules of set theory.
Then the domain of σ is extended to PA expressions T by assigning to them
an element of N ∪ {∞}. The cardinality expression |B| is evaluated as the car-
dinality of σ(B) if B is finite, and as ∞ if it is not. The evaluation of all PA
expressions under σ is done using the rules of addition and multiplication (ex-
tended with infinity as above).
Numerical constraints AT are evaluated to true or false under σ, under the
rules of basic arithmetic.
Finally, a solution σ of a QFBAPA∞ formula F is a substitution that eval-
uates F to true, using the rules of Boolean logic.
Syntax of ALCSCC ∞ . Let NC and NR be two disjoint sets of concept names,
and role names, respectively.
The set of ALCSCC concept expressions over NC and NR is defined as follows:
C ::= A | ¬C | C u C | C t C | succ(F ) ,
where A ∈ NC , F is a QFBAPA∞ formula using role names and ALCSCC
concept expressions over NC and NR as set variables.
An ALCSCC ∞ TBox over NC and NR is a finite set of concept inclusions of
the form C v D, where C and D are ALCSCC ∞ concept expressions over NC
and NR . We write C ≡ D to signify that C v D and D v C.
Perceptron Operators That Count 5
Semantics of ALCSCC ∞ . Given finite, disjoint sets NC and NR of concept and
role names, respectively, an interpretation I consists of a non-empty set ∆I and
a mapping ·I that maps every concept name C to a subset C I ⊆ ∆I and every
role name R ∈ NR to a binary relation RI ⊆ ∆I × ∆I . Given an individual
d ∈ ∆I and a role name R ∈ NR , we define RI (d) as the set of R-successors. We
define ARS I (d) as the set of all successors of d. The mapping ·I is extended to
Boolean combinations of concept expressions in the obvious way.
Successor constraints are evaluated according to the semantics of QFBAPA∞ .
To determine whether d ∈ (succ(F ))I , U is evaluated as ARS I (d), the roles oc-
curring in F are substituted with RI (d), and the concept expressions C occurring
in F are substituted with C I ∩ ARS I (d).
Then, d ∈ (succ(F ))I is true iff this substitution is a solution of the QFBAPA∞
formula F .
The interpretation I is a model of the TBox T if for every concept inclusion
C v D in T , it is the case that C I ⊆ DI .
A concept expression C is satisfiable wrt. the TBox T if there exists a model
of the TBox such that C I 6= ∅.
Example 1. In the ALCSCC ∞ formula succ(|causes| < 2), 2 is an integer con-
stant (also a PA expression), causes is a role, but also a set term, |causes|
is a set cardinality (also a PA expression), and |causes| < 2 is a numerical
constraint.
When deciding whether d ∈ (succ(|causes| < 2))I , we build the substitution
σ, such that σ(2) = 2, and σ(causes) = causesI (d).
Let I be an interpretation, and suppose that d has 2 causes-successors,
namely d1 and d2 (and nothing else). We then have σ(causes) = {d1 , d2 },
σ(|causes|) = 2, and σ(|causes| < 2) = f alse. There are no other possible
substitutions to consider. So d 6∈ (succ(|causes| < 2))I .
Suppose that we also have InjuryI = {d2 , d3 , d4 }, and (d, d3 ) ∈ hasI (but
nothing else).
When deciding whether d ∈ (succ(|causes ∩ Injury| = 1))I , Injury is a
concept description but also a set term, and we build the substitution σ 0 such
that σ 0 (1) = 1, σ 0 (causes) = causesI (d) = {d1 , d2 }, σ 0 (Injury) = InjuryI ∩
ARS I (d) = {d2 , d3 }, σ 0 (causes ∩ Injury) = σ 0 (causes) ∩ σ 0 (Injury) = {d2 },
σ 0 (|causes ∩ Injury|) = 1, and σ 0 (|causes ∩ Injury| = 1) = true. Hence σ 0 is a
solution of the QFBAPA∞ formula |causes ∩ Injury| = 1. So
d ∈ (succ(|causes ∩ Injury| = 1))I .
ALC and ALCQ. ALCQ is the fragment of ALCSCC ∞ such that succ(F ) is of
the form succ(|R∩C| ≤ n) or succ(|R∩C| ≥ n), where C is a concept expression
and R ∈ NR , and n ∈ N. ALC is the fragment of ALCSCC ∞ such that succ(F )
is of the form succ(|R ∩ C| ≥ 1).
Hence, we can define ∃R.C = succ(|R ∩ C| ≥ 1), (≤ n R.C) = succ(|R ∩ C| ≤
n), and (≥ n R.C) = succ(|R ∩ C| ≥ n). Qualified cardinality restrictions of
ALCQ are equivalently defined as:
(≤ n R.C)I = d ∈ ∆I |{c ∈ ∆I , (d, c) ∈ RI ∧ c ∈ C I }| ≤ n
6 P. Galliani, O. Kutz, N. Troquard
and
(≥ n R.C)I = d ∈ ∆I |{c ∈ ∆I , (d, c) ∈ RI ∧ c ∈ C I }| ≥ n
We define (= n R.C) = (≥ n R.C) u (≤ n R.C).
3 Teeth that count
We define a new collection of perceptron operators, that we call simply counting
teeth:
∇t∗ C1 : w1 , . . . , Cp : wp | (R1 , D1 ) : m1 , . . . , (Rq , Dq ) : mq ,
C=∇
where w~ = (w1 , . . . , wp ) ∈ Zp , m
~ = (m1 , . . . , mq ) ∈ Zq , t ∈ Z, Ci and Di
are concepts expressions and Ri are roles. (The tooth from our previous work,
without role-successor counting will be called regular tooth.)
With caused a role, we can now faithfully define the concept
CompulsoryImprisonment of the Felony Score Sheet:
∇44
∇ ∗ CocainePrimary : 16, · · · | (caused, ModerateInjury) : 18, . . . .
Semantics. When an individual d has only a finite number of Di -successors in
I, or when the weights are all non-negative, then the value of a d ∈ ∆I under
the counting tooth C is:
X X
vCI (d) = {wi | d ∈ CIi } + (mi · |{c ∈ ∆I | (d, c) ∈ RiI ∧ c ∈ DiI }|) .
i∈{1,...,p} i∈{1,...,q}
In a manner analogous to the truth value of the regular tooth, we would have:
CI = {d ∈ ∆I | vCI (d) ≥ t} .
When the individual d can have an infinite number of Di -successors and
some weights are positive and others are negative, then vCI (d) can be ill-defined.
(I.e. what should be the value of ∞ − ∞?) So instead of the single value vCI (d),
I I
we introduce two values, vC≥0 (d) and vC<0 (d), that represent the sum of the
non-negative summands and the sum of the negative summands, respectively.
X X
I
vC≥0 (d) = {wi | d ∈ CIi }+ (mi ·|{c ∈ ∆I | (d, c) ∈ RiI ∧c ∈ DiI }|) .
i∈{1,...,p} i∈{1,...,q}
wi ≥0 mi ≥0
X X
I
vC<0 (d) = {wi | d ∈ CIi }+ (mi ·|{c ∈ ∆I | (d, c) ∈ RiI ∧c ∈ DiI }|) .
i∈{1,...,p} i∈{1,...,q}
wi <0 mi <0
I I
Clearly vC≥0 (d) ≥ 0 and vC<0 (d) ≤ 0.
Finally, the semantics of C in a possibly infinite-branching interpretation I is
given as follows:
CI = {d ∈ ∆I | vC≥0
I I
(d) ≥ t − vC<0 (d)} .
Perceptron Operators That Count 7
Example 2. For purposes of illustration we define a ‘Modified Compulsory Im-
prisonment’ as
∇44
MCI = ∇ ∗ CocainePrimary : 16 | (caused, ModerateInjury) : 18),
(preventiveDetention, Month) : −1 ,
where only cocaine possession as primary offence and the number of moderate
injuries are kept from the original score sheet, and where in addition every month
of preventive detention lowers the score by one.
We want to decide whether the felony d ∈ ∆I falls within the definition
of this modified compulsory imprisonment, under the assumptions that d is
not in CocainePrimaryI , that |preventiveDetentionI (d) ∩ MonthI | = 12, and
|causedI (d) ∩ ModerateInjuryI | = 3.
I I
So, we have: vMCI≥0 (d) = 0 + 3 · 18 = 54 and vMCI<0 (d) = 12 · (−1) = −12.
I I
We must evaluate vMCI≥0 (d) ≥ t − vMCI<0 (d), which is 54 ≥ 44 + 12, or 54 ≥ 56,
which is false. So d does not fall within the modified compulsory imprisonment.
4 Particular case: Embedding ALC with counting teeth
with non-negative weights into ALCQ, and preliminary
complexity results
In practice, negative weights are not always necessary. As evidence, one can ob-
serve that the Felony Score Sheet does not contain negative points for computing
the total number of points.
Let us then first restrict our attention to counting teeth ∇∇t∗ C1 : w1 , . . . , Cp :
~ ∈ Nq . In this section we will
wp | (R1 , D1 ) : m1 , . . . , (Rq , Dq ) : mq such that m
still allow the weights on the concepts to be negative: w ~ ∈ Zp . For regular teeth,
we stipulate that the weights are non-negative simply for brevity, and because it
does not really matter. Indeed, a regular tooth with negative weights on concepts
can be transformed efficiently into a regular tooth with only non-negative weights
on concepts, as shown in [14, Prop. 3].
We show that the language ALC equipped with counting teeth ∇∇∗ is no
more expressive than ALCQ (Prop. 1) when the weights are non-negative. We
show that reasoning can be done in 2ExpTime when the threshold is expressed
in binary and in ExpTime when it is expressed in unary (Prop. 2). We will
improve upon the 2ExpTime upper-bound in Section 5. However, this section
has the merit to show how one can transform the problem of reasoning with
ALC equipped with the counting tooth with non-negative weights into a problem
of reasoning with ALCQ (although inefficiently when the threshold is encoded
in binary), for which efficient reasoning tools exist. We leave for future work
whether an efficient embedding into ALCQ is possible even when the threshold
is encoded in binary.
Let us observe that ALC equipped with counting teeth restricted to non-
negative weights is strictly less expressive than when negative weights are al-
8 P. Galliani, O. Kutz, N. Troquard
lowed. Indeed, one can express “has as many sons as daughters”:
∇0∗
AsMany =∇ | (isParentOf, Boy) : 1, (isParentOf, Girl) : −1 u
∇0∗
∇ | (isParentOf, Girl) : 1, (isParentOf, Boy) : −1 .
This cannot be expressed in ALCQ [6, Lemma 2], but ALC equipped with
counting teeth with non-negative weights has the same expressivity as ALCQ
(Prop. 1).
We recall that, in contrast, adding the regular tooth of [2] to ALC has the
same expressivity whether the weights are possibly negative or not.
Iterated elimination of role-successors counting and expressivity. Consider the
counting tooth C = ∇ ∇t∗ C1 : w1 , . . . , Cp : wp | (R1 , D1 ) : m1 , . . . , (Rq , Dq ) : mq
where all mj ∈ m~ are non-negative.
Now define the counting tooth
C0 = ∇
∇t∗ C1 : w10 , . . . , Cp : wp0 , E1 : wp+1
0 0
, . . . , Er : wp+r |
(R2 , D2 ) : m2 , . . . , (Rq , Dq ) : mq
where:
– wi0 = wi , for 1 ≤ i ≤ p
0
– wp+i = i · m , for 1 ≤ i ≤ r
l t+P 1 |w0 | m
– r= 1≤i≤p
m1
i
(in fact it’s enough to sum only |wi0 | when wi0 < 0)
– Ei = (= i R1 .D1 ), for 0 ≤ i ≤ r − 1
– Er = (≥ r R1 .D1 )
Lemma 1.
(C)I = (C0 )I .
Proof. We must show that for d ∈ ∆I , we have vC≥0 I
(d) ≥ t − vC<0 I
(d) iff
vCI0 ≥0 (d) ≥ t − vCI0 <0 (d).
To make the proof smoother, we can start with a simple observation. When
C=∇ ∇t∗ C1 : w1 , . . . , Cp : wp | (R1 , D1 ) : m1 , . . . , (Rq , Dq ) : mq and m ~ ∈ Nq ,
then for every d ∈ ∆I we have vCI (d) ≥ t iff vC≥0 I
(d) ≥ t − vC<0 I
(d). Indeed, when
q I I I
~ ∈ N , then vC<0 (d) is finite. So vC≥0 (d) + vC<0 (d) is well defined and equal to
m
vCI (d).
To prove the lemma, we can then verify that for d ∈ ∆I , we have vCI0 (d) ≥ t
iff vCI (d) ≥ t. We can see that vCI (d) ≥ vCI0 (d). So if vCI0 (d) ≥ t, then vCI (d) ≥ t.
Hence it suffices to verify that if vCI (d) ≥ t then vCI0 (d) ≥ t.
Let k be the number of R1 -successors of d that are in D1I .
If k ≤ r, we can focus specifically on the contributions of (R1 , D1 ) : m1 in
0
vCI (d) and of all Ei : wp+i in vCI0 (d). The contribution of (R1 , D1 ) : m1 in vCI (d) is
0
k · m1 , and (when k ≤ r), so is the contribution of all Ei : wp+i in vCI0 (d). Then
I I I I
clearly, vC0 (d) = vC (d), so vC0 (d) ≥ t iff vC (d) ≥ t.
Perceptron Operators That Count 9
It remains to verify the case of k > r. We must show that if vCI (d) ≥ t
0
then vCI0 (d) ≥ t. When k > r, the contribution of all Ei : wp+i in vCI0 (d) is
I
r · m1 ; so vC0 ≥0 (d) is bounded below by r · m1 . Since we only consider teeth
~ ∈ Nq in this section, vCI0 <0 (d) is bounded below by − 1≤i≤p |wi0 |. So
P
with m
l t+P 0
1≤i≤p |wi |
m
vCI0 (d) = vCI0 ≥0 (d) + vCI0 <0 (d) ≥ · m1 − 1≤i≤p |wi0 |. So vCI0 (d) ≥ t.
P
m1
Example 3. With C = ∇ ∇3∗ C1 : −2 | (R, D) : 1 , we have r = d(3 + 2)/1e = 5.
The rationale is that if an individual is a C1 it is still sufficient for it to have 5
R-successors that are D for this individual to be a C. If it is not a C1 , then 3, 4,
5 or more R-successors that are D are sufficient.
We get C0 = ∇ ∇3∗ C1 : −2, (= 1 R.D) : 1, (= 2 R.D) : 2, (= 3 R.D) : 3, (=
4 R.D) : 4, (≥ 5 R.D) : 5 | . Of course, it is equivalent to the regular tooth
C00 = ∇
∇3 C1 : −2, (= 1 R.D) : 1, (= 2 R.D) : 2, (= 3 R.D) : 3, (= 4 R.D) : 4, (≥
5 R.D) : 5 .
So a counting tooth with ALC concepts can be transformed into a regular
tooth with ALCQ concepts when only non-negative weights are allowed. In turn,
we know how to (efficiently) transform it into an ALCQ concept [2]. We obtain
the following proposition.
Proposition 1. ALC with counting teeth with non-negative weights has the
same expressivity as ALCQ.
Preliminary complexity results. In the rewriting above, the size of the tooth
strictly grows, as one pair (R1 , D1 ) is removed, but r new concepts are added,
each of size larger than the combined sizes of R1 plus D1 . Yet, r is bounded by
the threshold t. So, when the threshold is expressed in unary, the rewriting only
causes a linear expansion. But if the weights are encoded in binary, this is not
an efficient rewriting! It only yields this partial result.
Proposition 2. Reasoning with ALC with counting teeth, disallowing
non-negative weights, wrt. to a TBox, is in 2ExpTime. When the threshold is
represented in unary, then it is ExpTime-complete.
Proof. When deciding whether the concept C is satisfiable wrt. T , (1) if there are
nested counting teeth (in T or C), pick the inner-most (breaking ties at random)
tooth concept (T ), (2) introduce a fresh concept name F reshT , (3) repeat 1–2,
with C := C[T /F reshT ] is satisfiable wrt. T := T [T /F reshT ] ∪ {F reshT ≡ T },
(where X[A/B] stands for the uniform substitution with B of every occurrence
of A in X).
The number of teeth in T and C is linear in the size of T and C, so the
procedure above terminates in polynomial time, and results in a combined size
of the T and C that are linear in the combined size of T and C at the start of
the procedure.
Now, observe that:
10 P. Galliani, O. Kutz, N. Troquard
– C is satisfiable wrt. T iff C[T /F reshT ] is satisfiable wrt. T [T /F reshT ] ∪
{F reshT ≡ T }.
– when the procedure halts, there are no more nested teeth in T and C.
It now suffices to transform all the counting teeth in the resulting T and C
into regular teeth applying iteratively the rewriting proposed above. We obtain
T and C which are now written in ALCQ equipped with regular teeth. It causes
a blow-up in size exponential in the larger threshold of an occurring counting
tooth, when represented in binary, and only a polynomial increase when the
thresholds are represented in unary.
Finally, using the transformations of [2], eliminating the regular teeth alto-
gether is efficient, and we obtain a problem of deciding the satisfiability of an
ALCQ concept wrt. an ALCQ TBox, which is ExpTime-complete [9].
5 General case: Embedding ALC with counting teeth
into ALCSCC ∞
In Section 4, we failed to establish a precise complexity of ALC with counting
teeth, even restricting our attention to only non-negative weights for roles. Here
we embed it into ALCSCC ∞ , showing that the complexity is in ExpTime.
This approach has a practical drawback: ALCSCC ∞ is not a logic supported
by the existing reasoning services, and algorithms fit for implementation do not
exist. But it will allow us to pin down the complexity of reasoning in ALC
augmented with counting tooth operators.
Let C = ∇∇t∗ C1 : w1 , . . . , Cp : wp | (R1 , D1 ) : wp+1 , . . . , (Rq , Dq ) : wq . Let
us assume for now that C does not have nested teeth. Let T be a TBox. Let us
assume for now that T is an ALC TBox (without teeth).
We want to decide whether the concept description C is satisfiable wrt. the
TBox T .
We add a fresh role name zooCi (‘zero-or-one’) adding the axioms
(= 1 zooCi .>) ≡ Ci and (= 0 zooCi .>) ≡ ¬Ci for every 1 ≤ i ≤ p to T . We
obtain the TBox T 0 .
Now, we define summands =
w1 · |zooC1 ∩ >|, . . . , wp · |zooCp ∩ >|, wp+1 · |R1 ∩ D1 |, . . . , wq · |Rq ∩ Dq | .
Roughly speaking, C is the set of individuals such that the sum of the elements
of summands is greater or equal to t. The quantity |zooCi ∩ >| will be 1 if the
individual is a Ci and 0 if it is not.
But some of these summands could be negative, exactly those where wi < 0,
and QFBAPA∞ does not allow using negative constants. In [11], the authors
observe that “Dispensing with negative constants is not really a restriction since
we can always write the numerical constraints of QFBAPA in a way that does
not use negative integer constants (by bringing negative summands to the other
side of a constraint).” We are going to do just that.
Perceptron Operators That Count 11
When n ∈ N, we syntactically identify ∼−n with n. If t ≥ 0, then tl = t and
tr = 0, else tl = 0 and tr =∼ t. Now consider the ALCSCC concept
X X
C0 = succ
tl + ∼ wi · xi ≤ tr + wi · xi
.
wi ·xi ∈summands wi ·xi ∈summands
wi <0 wi ≥0
(In order to be totally rigorous, T1 ≤ T2 represents the QFBAPA∞ formula
(T1 < T2 ) ∨ (T2 = T1 ).)
Lemma 2. C is satisfiable in T iff C0 is satisfiable in T 0 .
We can now do better than Proposition 2.
Proposition 3. Reasoning in ALC with counting teeth, wrt. a TBox is
ExpTime-complete, even when the threshold is expressed in binary, and even
when the weights on roles are allowed to be negative.
Proof. Starting from the deepest teeth (in the concept and the TBox), we rewrite
them into an ALCSCC concept as above, adding zoo role axioms into the TBox
as we go. Those are a series of polynomial transformations, all equi-satisfiable.
The result follows because reasoning in ALCSCC can be done in ExpTime [6].
6 Teeth that count more
In the previous extended family of teeth, the additional weights are used as
multiplying factor to the number of features reached by a role.
We could envisage to replace these weights with arbitrary functions f , from
N (or N ∪ {∞}) to R. A feature with weight w could be represented by a feature
with function f (n) = w · n.
Now, although irremediably leaving the cosy realm of linearity, f could be
anything, e.g., a polynomial, a sigmoid, a binomial distribution, etc.
We define a new collection of perceptron operators
∇t∗ C1 : w1 , . . . , Cp : wp | (R1 , D1 ) : f1 , . . . , (Rq , Dq ) : fq
C=∇ ,
where w ~ = (w1 , . . . , wp ) ∈ Rp , f~ = (f1 , . . . , fq ) is a q-vector of functions from N
to R, Ri and Di are roles and concepts respectively.
When role-branching is finite (for simplicity of exposition), the value of a
d ∈ ∆I under a C is:
X X
vCI (d) = {wi | d ∈ CIi } + fq (|{c ∈ ∆I | (d, c) ∈ RiI ∧ c ∈ DI }|) .
i∈{1,...,p} i∈{1,...,q}
As illustrated in [2], teeth operators are simply linear classification models, and it
is possible to use standard linear classification algorithms (such as the Perceptron
Algorithm, Logistic Regression, or Linear SVM) to learn its weights and its
threshold given a set of assertions about individuals (ABox). This richer family
of operators would offer a new perspective of integrating into ontologies concepts
learnt with more advanced algorithms.
12 P. Galliani, O. Kutz, N. Troquard
7 Conclusions
We extended the tooth with role-successors counting.
When we do not allow negative weights, the extended perceptron operator
can faithfully and easily express concepts like ‘compulsory imprisonment’ from
the Florida Score Sheet. When added to ALC, the resulting logic has exactly
the same expressivity as ALCQ. We showed how reasoning can be transformed
into reasoning in ALCQ, allowing one to straightforwardly use state-of-the-art
reasoning services for ALCQ. When the threshold is expressed in unary, it is no
more succinct. Whether it is more succinct than ALCQ when the threshold is
expressed in binary remains an open question.
When we allow negative weights, the extended perceptron operator can ex-
press concepts like “has more sons than daughters”, “has as many arms than
legs”, ... When added to ALC it yields a DL that is strictly more expressive than
ALCQ, and is not anymore a fragment of FOL.
The complexity of the DL that is obtained by adding the extended perceptron
operator to ALC is ExpTime-complete, no matter whether we allow negative
weights or not, or whether the threshold is represented in unary or binary.
References
1. D. Porello, O. Kutz, G. Righetti, N. Troquard, P. Galliani, and C. Masolo. A
toothful of concepts: Towards a theory of weighted concept combination. In Pro-
ceedings of the 32nd International Workshop on Description Logics, Oslo, Norway,
June 18-21, 2019, 2019.
2. P. Galliani, G. Righetti, O. Kutz, D. Porello, and N. Troquard. Perceptron connec-
tives in knowledge representation. In Knowledge Engineering and Knowledge Man-
agement - 22nd International Conference, EKAW 2020, Bolzano, Italy, September
16-20, 2020, Proceedings, pages 183–193, 2020.
3. F. Baader, G. Brewka, and O. F. Gil. Adding threshold concepts to the description
logic EL. In C. Lutz and S. Ranise, editors, Frontiers of Combining Systems, pages
33–48, Cham, 2015. Springer International Publishing.
4. F. Baader and U. Sattler. Expressive number restrictions in description logics. J.
Log. Comput., 9(3):319–350, 1999.
5. H. J. Ohlbach and J. Koehler. Modal logics, description logics and arithmetic
reasoning. Artificial Intelligence, 109(1):1–31, 1999.
6. F. Baader. A new description logic with set constraints and cardinality constraints
on role successors. In C. Dixon and M. Finger, editors, Frontiers of Combining
Systems - 11th International Symposium, FroCoS 2017, Brası́lia, Brazil, September
27-29, 2017, Proceedings, volume 10483 of Lecture Notes in Computer Science,
pages 43–59. Springer, 2017.
7. V. Kuncak and M. C. Rinard. Towards Efficient Satisfiability Checking for Boolean
Algebra with Presburger Arithmetic. In F. Pfenning, editor, Automated Deduction
- CADE-21, 21st International Conference on Automated Deduction, Bremen, Ger-
many, July 17-20, 2007, Proceedings, volume 4603 of Lecture Notes in Computer
Science, pages 215–230. Springer, 2007.
Perceptron Operators That Count 13
8. K. Schild. A correspondence theory for terminological logics: Preliminary report.
In J. Mylopoulos and R. Reiter, editors, Proceedings of the 12th International Joint
Conference on Artificial Intelligence. Sydney, Australia, August 24-30, 1991, pages
466–471. Morgan Kaufmann, 1991.
9. S. Tobies. The complexity of reasoning with cardinality restrictions and nominals
in expressive description logics. J. Artif. Intell. Res., 12:199–217, 2000.
10. F. Baader and A. Ecke. Extending the description logic ALC with more expres-
sive cardinality constraints on concepts. In C. Benzmüller, C. L. Lisetti, and
M. Theobald, editors, GCAI 2017, 3rd Global Conference on Artificial Intelligence,
Miami, FL, USA, 18-22 October 2017, volume 50 of EPiC Series in Computing,
pages 6–19. EasyChair, 2017.
11. F. Baader and F. De Bortoli. On the expressive power of description logics with
cardinality constraints on finite and infinite sets. In A. Herzig and A. Popescu,
editors, Frontiers of Combining Systems, pages 203–219, Cham, 2019. Springer
International Publishing.
12. F. Baader, B. Bednarczyk, and S. Rudolph. Satisfiability and query answering in
description logics with global and local cardinality constraints. In G. D. Giacomo,
A. Catalá, B. Dilkina, M. Milano, S. Barro, A. Bugarı́n, and J. Lang, editors, ECAI
2020 - 24th European Conference on Artificial Intelligence, 29 August-8 September
2020, Santiago de Compostela, Spain, August 29 - September 8, 2020 - Including
10th Conference on Prestigious Applications of Artificial Intelligence (PAIS 2020),
volume 325 of Frontiers in Artificial Intelligence and Applications, pages 616–623.
IOS Press, 2020.
13. F. Baader, I. Horrocks, C. Lutz, and U. Sattler. An Introduction to Description
Logic. Cambridge University Press, 2017.
14. P. Galliani, O. Kutz, D. Porello, G. Righetti, and N. Troquard. On knowledge
dependence in weighted description logic. In GCAI 2019. Proceedings of the 5th
Global Conference on Artificial Intelligence, Bozen/Bolzano, Italy, 17-19 Septem-
ber 2019, pages 68–80, 2019.