
| Name                                                              | Syntax   | Semantics                                         | Symbol                      |     |
|-------------------------------------------------------------------|----------|---------------------------------------------------|-----------------------------|-----|
| Role composition                                                  | R1 0 R2  | {(a, b) E  Δ x  Δ x                               |                             |     |
| Ðá E A T . (a, c) E R T A (c, b) E R T                            |          |                                                   |                             |     |
| Role complement                                                   | R        | {(a, b) ∈ Δ T × Δ T | (a, b) ∈ R T                |                             |     |
| Role conjunction                                                  | R1 R2    | {(a, b) ∈ Δ T × Δ T | (a, b) ∈ R T ∧ (a, b) ∈ R T | n                           |     |
| Role disjunction                                                  | R1 U R2  | {(a, b) E A x A x                                 | (a, b) ∈ R T V (a, b) ∈ R T | D   |
| Inverse roles                                                     | R-1      | {(a, b) E  Δ x  Δ x                               | (b, a) E R 2                | - 1 |
| Transitive closure                                                | R        | {(a, b) E Δ x Δ x                                 | | (a, b) E (R 2 ) 2         | +   |
| Universal role                                                    | U        | A x A x                                           | U                           |     |
| For a binary relation R , R + denotes the transitive closure of R |          |                                                   |                             |     |

## 2.1.3 Role Constructors

Role constructors allow us to build complex role descriptions. A collection of role constructors can be found in Figure 2. Again, the rightmost column indicates the naming scheme, where name modifiers for role constructors are written in superscript and separated by commas. For example, ALC Q with inverse roles and transitive closure is called ALC Q+,-1 In DLs admitting role constructors, the set of role descriptions is defined inductively, analogously to the set of concept descriptions. The semantics of role constructors is given in the third column of Figure 2. As with concept descriptions, it can be used to extend the interpretation function from role names to role descriptions.

In a DL with role constructors, role descriptions can be used wherever role names may be used in the corresponding DLs without role constructors. For example,
∃( R 1 ∩ R 3 ). C ∩ ∀( R 2 ∩ R 2 ). ¬C
is an ALC - n -concept description. This concept description is unsatisfiable since R 2 ∪ R 2 is equivalent to the universal role. Note that role descriptions can also be used within role assertions in an ABox.

The DL ALC°,µ,+ was first treated by Baader (1991) (under the name ALCtrans); Schild
(1991) has shown that this DL is a notational variant of propositional dynamic logic (PDL).

DLs with Boolean operators on roles were investigated by Lutz and Sattler (2000). The inverse operator was available in the system CRACK (Bresciani, Franconi, & Tessaris, 1995), and reasoning in DLs with inverse roles was, for example, investigated by Calvanese et al. (1998) and Horrocks et al. (2000). The universal role can be expressed using DLs with Boolean operators on roles (see the above example), and it can in turn be used to simulate general concept inclusion axioms within concept descriptions.

## 2.2 Restricting The Syntax

Until now, constructors could be combined arbitrarily. Sometimes it makes sense to restrict the interaction between constructors since reasoning in the restricted DL may be easier than reasoning in the unrestricted DL. We will consider DLs imposing certain restrictions on