

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

![0_image_2.png](0_image_2.png)

![0_image_3.png](0_image_3.png)

An important point concerns computational complexity. The complexity result **shows**
that the additional expressive power has no impact from a computational complexity **point**
of **view.**
The extension of DLs to the management of vagueness is not new (Tresp & **Molitor,**
1998; Yen, 1991). Yen was the first, to the best of my knowledge, introducing **vagueness**
into a simple DL. His language has two interesting points not included into our **language.**
Firstly, it allows the definition of vague concepts by means of explicit membership **functions**
over a domain, **e.g.** LowPressure:≈ **domain**(AirPressure); membershipfx(λp.low(p)). **Here**
the domain over p ranges is **given** by AirPressure. λp.low(p) determines the **membership**
degree of being a pressure p low. Secondly, the language allows concept modifiers, **like** Very or Slightly, by means of which concepts like "very low pressure" can be defined **through**
VeryLowPressure:≈ Very(LowPressure). This last idea has been generalised to ALC by **Tresp**
and Molitor (1998) where a certain type of concept modifiers are allowed. Strictly speaking, the language defined by Tresp and Molitor is more expressive, as we do not **consider**
concept modifiers. From a semantics point of view, the extension to Tresp and **Molitor's**
language is quite straightforward. But, the cost that we have to pay for this **increasing**
expressive power is that, from a computational complexity and algorithms point of **view,**
things changes radically. Indeed, according to Tresp and Molitor for each **"completion"** a linear optimisation problem is generated (set of inequations of the form op1(t1)Rop2(t2) or op1(t1)Rf(op2(t2)), **where** ti is a truth-value variable, R ∈ {≤, ≥, =, opi ∈ {id, mi}, **with**
id(t) the identity and mi(t) is a modifier function over truth-value variables, **respectively,**
and f ∈ {min, max}-derived from the semantics of the connectors ⊓,⊔) and then solved for the best value. Then, the minimum among all computed solutions is taken. The **solutions**
can be computed by relying on methods from the domain of linear programming, e.g. the