∫ ≠ ≤ ≥ ∑ ∞ ≡ ∩ ≈ ∏ ∆ ∂ Ω  

3.4. Tablo algoritms ALC paplašinājumiem

Kādi ALC paplašinājumi "nesagrautu" mūsu tikko iegūtos secinājumus? T.i. tablo algoritmam joprojām vienmēr jābeidz darbs galīgā skaitā soļu, un ir jābūt korektam un pilnīgam.

3.4.1. Lomu inversija (loģika ALCI).

Atcerēsimies, ka loģikā ALCI katrai lomai r mēs drīkstam izmantot arī inverso lomu r^-1. Šī operācija it kā "neko īpaši jaunu nedod", jo formulu r^-1(c, d) visur var aizstāt ar r(d, c).

Un tomēr, loģikai ALCI tablo algoritms ir nedaudz jāpapildina.

Solī 1:

1) Sākumkopā ir tikai formulas no dotās kopa S (visas formulas ir negāciju normālformā). Nepieciešama papildus darbība: ja kopā S ir formula r(d, e) vai ~r(d, e), tad kopai jāpievieno arī attiecīgā formula r^-1(e, d) vai ~r^-1(e, d). Un otrādi: ja kopā S ir formula r^-1(d, e) vai ~r^-1(e, d), tad kopai jāpievieno arī attiecīgā formula r(e, d) vai ~r(e, d).

Arī solī 4 tablo algoritms jāpapildina pavisam nedaudz:

4) Ja kopā ir formula C(d) = Ey(r(d, y)&B(y)), bet nevienai objektu konstantei e mūsu kopā nav abu formulu r(d, e) un B(e), tad kopai pievienojam formulas r(d, e) un B(e), kur e - pilnīgi jauna objektu konstante. Nepieciešama papildus darbība: līdz ar formulu r(d, e) kopai jāpievieno arī formula r^-1(e, d).

Šeit r vietā drīkst būt arī r^-1:

4') Ja kopā ir formula C(d') = Ey(r^-1(d', y)&B(y)), bet nevienai objektu konstantei e' mūsu kopā nav abu formulu r^-1(d', e') un B(e'), tad kopai pievienojam formulas r^-1(d', e') un B(e'), kur e' - pilnīgi jauna objektu konstante. Nepieciešama papildus darbība: līdz ar formulu r^-1(d', e') kopai jāpievieno formula r(e', d').

Tādā veidā algoritma ģenerētajā kopā katram pārim (d, e) būs abas formulas - r(d, e) un r^-1(e, d), vai neviena no tām.

Tāpēc soļa 5 darbība nemainās - nav svarīgi, vai formulā C(d) ieiet loma r, vai r^-1:

5) Ja kopā ir formula C(d) = Ay(r(d, y)->B(y)), un kādai objektu konstantei e formula r(d, e) jau ir kopā, bet B(e) vēl nav, tad kopai pievienojam B(e).

5) Ja kopā ir formula C(d) = Ay(r^-1(d, y)->B(y)), un kādai objektu konstantei e formula r^-1(d, e) jau ir kopā, bet B(e) vēl nav, tad kopai pievienojam B(e).

Bet kā šīs nelielās izmaiņas ietekmēs mūsu algoritma darbības analīzi, kuras pamatā bija īpaši definēta augoša grafa G[S] novērošana?

Vispirms mums ir jāievēro, ka tagad reizē ar formulu r(d, e) (vai tās negāciju) mums visur reizē parādās arī formula r^-1(e, d) (vai tās negācija). Un otrādi. Tātad, ja no virsotnes d uz virsotni e ved šķautne ar formulu r(d, e) (vai tās negāciju), tad no e atpakaļ uz d ved šķautne ar formulu r^-1(e, d) (vai tās negāciju). Formāli tas it kā izjauc novēroto "koku augšanas" procesu? Ierastās kārtības atjaunošanai mums vajadzēs nedaudz izmainīt grafa G[S] šķautņu definīciju, jauno grafu nosaucot par G'[S]:

a) Soļos 4 un 4', kad aiz virsotnes d tiek radīta jauna virsotne e un formulu kopai tiek pievienotas formulas r(d, e), r^-1(e, d) un B(e), mēs grafā G'[S] novelkam vienu šķautni, kas ved no d uz e, un kurai pierakstītas divas formulas - r(d, e), r^-1(e, d). T.i. šķautnes virziens vienmēr ved uz jaunradīto virsotni e.

b) Solī 1, ja kopā S ir kāda no formulām r(d, e), r^-1(e, d),~r(d, e), ~r^-1(e, d), tad virsotnes d un e savienojam ar šķautni, kurai pierakstītas visas lomu formulas, kas saista d ar e vai e ar d. Šķautnes virzienu izvēlamies patvaļīgi.

Grafa G'[S] augšana notiek mums jau ierastajā veidā: sākumā mums ir patvaļīgs orientēts grafs, bet pēc tam no sākumgrafa virsotnēm "aug koki".

Izsekojot mūsu analīzi tālāk, un grafa G[S] vietā aplūkojot grafu G'[S}, mēs redzam, ka jākoriģē ir tikai novērojums d), jo jaunradītai virsotnei e solis 5 tagad var radīt jaunas formulas kopā K(e) ne tikai no kopas K(d) formulām (ja no virsotnes d uz e ved vienīgā virsotnē e ieejošā škautne r(d, e)). Tiešām, ja kādā virsotnē f ir formula Ay(q(f, y)->B(y)), tad solis 5 no tās var radīt formulu B(e) tikai tad, ja algoritma ģenerētājā kopā ir formulas q(f, e) un q^-1(e, f), t.i. no e uz f ved šķautne q^-1(e, f). Tātad solis 5 tagad var radīt jaunas formulas kopā K(e) ne tikai no virsotnes e "priekšteča" kopas K(d) formulām, bet arī no e "pēcteču" kopām K(f) (tās var būt vairākas). Vai tas varētu izmainīt novērojuma d) izšķirošo secinājumu: vissarežģītākā kopas K(e) formula ir vienkāršāka par vissarežģītāko "priekšteča" kopas K(d) formulu? Tiešām, virsotņu formulu kopās K(x) "formulas no malas" uzrodas tikai soļos 4 un 5, un katru reizi jaunās formulas "loģiskais dziļums" ir mazāks par izcelsmes formulas "dziļumu". Iesākumā ir solis 4, kurš rada šķautni r(d, e) uz jaunradītu virsotni e, un ievieto kopā K(e) pirmo formulu B(e). Pēc tam solis 5 var radīt K(e) citas formulas no kopas K(d) formulām, bet soļi 2 un 3 - var no esošām K(e) formulām radīt jaunas K(e) formulas. Un katru reizi no sarežģītākas formulas rodas vienkāršāka. Tad atkal solis 4 var radīt šķautni q(e, f) uz jaunradītu virsotni f, ievietojot kopā K(f) pirmo formulu B'(f) - tā būs vienkāršāka par to K(e) formulu, no kuras tā radīsies. Un tālāk solis 5 varēs papildināt gan K(d), gan K(e), gan K(f), pie tam K(e) tagad jau var papildināties no abām pusēm - no K(d) un no K(f). Utt.

Tas nozīmē, ka vajadzīgo secinājumu mēs varam iegūt, izmantojot šādu lemmu (tur minētie naturālie skaitļi ir mūsu formulu "loģiskie dziļumi"):

Lemma. Aplūkosim šādu koka būvēšanas procedūru. Kokā būs virsotnes un šķautnes, katrai virsotnei v būs piekārtota galīga naturālo skaitļu kopa N(v). Sākumā kokā būs tikai saknes virsotne s un tai piekārtota kopa N(s). Koku būvējam ar 4 operāciju palīdzību:

1) Ja virsotnes d kopā N(d) ir skaitlis n>1, tad drīkstam radīt jaunu koka zaru uz jaunu virsotni e ar kopu N(e) ={m}, kur m<n.

2) Ja virsotnes d kopā N(d) ir skaitlis n>1, tad drīkstam kopai N(d) pievienot skaitli m<n.

3) Ja no virsotnes d iet šķautne uz virsotni e, un kopā N(d) ir skaitlis n>1, tad drīkstam kopai N(e) pievienot skaitli m<n.

4) Ja no virsotnes d iet šķautne uz virsotni e, un kopā N(e) ir skaitlis n>1, tad drīkstam kopai N(d) pievienot skaitli m<n.

Tad jebkurām divām koka virsotnēm d, e, ja no d uz e iet šķautne, tad max N(d) > max N(e), t.i. kopas N(e) lielākais skaitlis ir mazāks par kopas N(d) lielāko skaitli. Un tāpēc, katra koka zara augšana kādā brīdi tiek pārtraukta un tālak nenotiek (t.i. zara gala virsotnei operācija 1 vairs nav lietojama).

Pierādījums. Pirmkārt, kad operāciju 1 pielietojam pirmoreiz, lemmas apgalvojums izpildās. Tāpēc pieņemsim no pretējā, ka nupat pirmo reizi ir pienācis brīdi, kad lemmas apgalvojums vairs neizpildās, t.i. ir divas tādas virsotnes d, e, kur no d uz e iet šķautne, bet max N(d) <= max N(e). Kura no 4 operācijām šādu situāciju varēja radīt? T.i. kura no operācijām varēja pievienot kopai N(e) skaitli m >= max N(d)?

Operācijas 1 un 2 to izdarīt nevarēja. Arī operācija 3, pielietota virsotnēm d, e, to izdarīt nevarēja. Paliek vēl operācija 4, pielietota virsotnēm e, f, kur no e uz f iet šķautne. Saskaņā ar pieņēmumu, pirms operācijas: max N(d) > max N(e) > max N(f). Operācija 4 pievieno kopai N(e) skaitli m < max N(f), t.i. m < max N(e) < maxN(d), t.i. skaitļa m >= max N(d) pievienošana kopai N(e) nav iespējama. Pretruna. Q.E.D.

Līdz ar to esam parādījuši, ka arī loģikas ALCI gadījumā (mūsu modificētais) tablo algoritms būvēs savu ierasto koku kolekciju, un kaut kad darbu beigs - ar pozitīvu vai negatīvu rezultātu. Arī korektības un pilnības teorēmu pierādījumi ir derīgi bez izmaiņām, jo lomas r un tās inversās lomas r^-1 interpretācijas ir "pilnīgi paralēlas" - definējot interpretāciju, formulas r^-1(d', e') un r(e', d') jādefinē kā patiesas (vai aplamas) abas vienlaicīgi). Arī Finite model property saglabājas,. Un saglabājas arī Tree model property (ja sākumkopā nav apgalvojumu par lomām).

Kāda ir mūsu modificētā tablo algoritma sarežģītība (tukšas T-kastes gadījumā) - PSPACE vai sliktāka? Zoļina navigatorā loģikai ALCI ar tukšu T-kasti:

a) Uzdevuma "Concept consistency" sarežģītība ir PSPACE-complete.

b) Uzdevuma "ABox consistency" sarežģītība minēta kā neatrisināta problēma!

Bet, skatoties uz mūsu tikko izpētīto, liekas, ka starpības starp abiem uzdevumiem nav nekādas (tāpat kā ALC gadījumā)! Vai tas varētu nozīmēt, ka arī ABox consistency uzdevuma sarežģītība loģikai ALCI ir PSPACE-complete?

Uzdevums (varētu būt labs iesākums maģistra darbam). Sekojot paraugam sadaļas 3.3 beigās, pamēģiniet pārveidot mūsu modificēto tablo algoritmu loģikai ALCI par algoritmu, kas strādā polinomiālā atmiņā (NPSPACE).

Tagad - 2007.gada augustā - Zoļina navigatorā reģistrēts jauns rezultāts: loģikai ALCI uzdevuma "ABox consistency" sarežģītība arī ir PSPACE-complete!

Yu Ding, Volker Haarslev, and Jiewen Wu. A new mapping from ALCI to ALC. In Proc. of the 20th Int. Workshop on Description Logics (DL'2007), vol. 250 in CEUR, pp. 267–274, Brixen, Italy, June 2007. Available here (pdf) and here (pdf).

3.4.2. Kvantori ar skaitliskiem ierobežojumiem (loģika ALCQ).

Atcerēsimies, ka runa te ir par kvantoru >=n r.C ("tie objekti, kam loma r noved klasē C uz vismaz n dažādiem objektiem") un kvantoru <=n r.C ("tie objekti, kam loma r noved klasē C uz ne vairāk kā n dažādiem objektiem"). Šeit n ir konkrēts naturāls skaitlis (unārā vai binārā pierakstā - ja vērtēsim algoritmu sarežģītību, tad šī atšķirība var izrādīties būtiska).

Parastais kvantors E r.C tad ir uzrakstāms kā >=1 r.C, bet parastais A r.C - kā <=0 r.-C. Līdz ar to varam uzskatīt, ka loģikā ALCQ konstruktori E r.C un A r.C vispār nav vajadzīgi.

Kas tad notiek ar formulu negāciju normālformu? Nekādas problēmas te nerodas, jo negācija ierobežoto kvantoru priekšā burtiski "pazūd":

-(<=n r.C) pārveidojas par >=n+1 r.C;

-(>=n r.C) pārveidojas par <=n-1 r.C (ja n>0) vai par B^-B jeb tukšo jēdzienu (ja n=0).

Bet šo kvantoru translācija uz predikātu formulām jau prasa vienādības predikāta izmantošanu.

>=n r.C ir jātranslē kā

Ey₁Ey₂...Ey_n(... & r(x, y_i) & B(y_i) & ... & ... & ~(y_i=y_j) & ... ),

kur r(x, y_i) & B(y_i) atkārtojas n reizes, bet ~(y_i=y_j) - pavisam n(n-1)/2 reizes (t.i. katram pārim i, j, kur 1<=i<j<=n).

<=n r.C ir jātranslē kā -(>=n+1 r.C), t.i.:

~Ey₁Ey₂...Ey_n+1(... & r(x, y_i) & B(y_i) & ... & ... & ~(y_i=y_j) & ... ),

Ay₁Ay₂...Ay_n+1~(... & r(x, y_i) & B(y_i) & ... & ... & ~(y_i=y_j) & ... ),

Ay₁Ay₂...Ay_n+1(... & r(x, y_i) & B(y_i) & ... -> ... v (y_i=y_j) v ... ) (ja n=1, tad disjunkciju no 0 locekļiem uzskatām par aplamu).

Divu veidu pretrunas

Aplūkojot tablo algoritma darba rezultātus (uzģenerēto formulu kopu), mums tagad ir jāievēro, ka tur var būt vēl viens pretrunas veids (bez q(c) un ~q(c) vienlaicīgas parādīšanās): ja kopā ir formulas d: <=n r.C translācija un ir n+1 objektu konstantes e₁, ..., e_n+1, kam kopā ir abas formulas r(d, e_i) un B(e_i) un visas formulas ~(e_i=e_j). Ja tā ir noticis, tad algoritma darba rezultātu uzskatīsim par negatīvu. [Kāpēc nav vajadzīgs vēl viens pretrunas veids - formulām d: >=n r.C? T.i. ja kopā ir formulas d: >=n r.C translācija, bet nav atrodamas n objektu konstantes e₁, ..., e_n, kam kopā ir abas formulas r(d, e_i) un B(e_i) - vai tā nav pretruna? Tā nav pretruna, bet tikai "nepabeigtība" - process vienkārši jāturpina, mēģinot radīt trūkstošās konstantes Toties ar d: <=n r.C saistītā situācija vairs nav labojama - konstantu ir saradies "pārāk daudz".]

Šādi papildinot pozitīvā un negatīvā rezultāta definīciju, mēs tagad varam meģināt izveidot tablo algoritmu loģikai ALCQ.

Tablo algoritma versija loģikai ALCQ (Hollunder, Baader, 1991).

Šī elegantā versija ir labi aprakstīta S.Tobies disertācijas 4.nodaļā. Ideja: drošāk izmantot nedeterminētās izvēles!

1) [Tāpat kā ALC.] Sākumā kopā ir tikai formulas no dotās kopa S (visas formulas ir negāciju normālformā).

2) [Tāpat kā ALC.] Ja kopā ir formula A(c)&B(c), bet tajā nav kādas no formulām A(c), B(c), tad kopai šo (šīs) trūkstošo(ās) formulu(as) pievienojam.

3) [Tāpat kā ALC.] Ja kopā ir formula A(c)vB(c), bet tajā nav nevienas no formulām A(c), B(c), tad kopai pievienojam formulu A(c) vai formulu B(c) (būtiski nedeterminēta izvēle).

3') (Jaunums! Tā sauktā choose-kārtula.) Ja kopā ir formula C(d) = (Ey>=n)(r(d,y)&B(y)) vai formula C(d) = (Ey<=n)(r(d,y)&B(y)), un kādai konstantei e kopā ir arī formula r(d, e), bet nav ne B(e), ne ~B(e), tad ievietojam kopā vai nu formulu B(e), vai ~B(e) (būtiski nedeterminēta izvēle). [Ideja: galu galā mums beigās (pozitīva iznākuma gadījumā), veidojot interpretāciju, tāpat būs jāizlemj vai nu B(e) patiesums, vai ~B(e) patiesums. Labāk, lai tas noskaidrojas jau agrāk - nedeterminētas izvēles procesā, un galvenais - PARĀDĀS ATKLĀTI mūsu ģenerētajā formulu kopā. Citādi beigās var būt grūtības ar formulu Ay(r(d, y)->B(y)) patiesuma nodrošināšanu: kādai konstantei e formulai r(d, e) jābūt patiesai, bet par B(e) patiesumu neesam parūpējušies.]

4') [Tikai nedaudz papildināts, salīdzinot ar ALC.] Ja kopā ir formula C(d) = (E>=n)y (r(d,y)&B(y)) (pie n=1 tā būtu Ey(r(d,y)&B(y)), bet tajā ir atrodamas tikai k (kur k<n, t.i. "par maz") dažādas objektu konstantes e₁, ..., e_k, kam kopā atrodas abas formulas r(d, e_i) un B(e_i), un visas formulas ~(e_i=e_j), tad ievedam pilnīgi jaunu objektu konstanti e, un pievienojam kopai formulas r(d, e) un B(e), un visas formulas ~(e_i=e).

5') (Jaunums!) Ja kopā ir formula C(d) = (E<=n)y (r(d,y)&B(y)), tad sameklējam visas objektu konstantes e₁, ..., e_k, kam kopā atrodas abas formulas r(d, e_i) un B(e_i). Ja izrādās, ka k>n (t.i. ir "sanācis par daudz") tad sameklējam visus tos pārus (e_i, e_j), kam i<j un kam kopā nav atrodamam ne formula ~(e_i=e_j), ne formula ~(e_j=e_i). Nederminēti izvēlamies vienu no šiem pāriem (e_i, e_j), un pieņemsim, ka mēs drīkstam uzskatīt, ka e_i=e_j. Un ja tā, tad izslēgsim e_j no visām mūsu kopas formulām, visur aizstājot e_j ar e_i.

Algoritma konverģence

Teorēma. Neatkarīgi no soļu 2-5' izpildes secības, mūsu nedeterminētais algoritms vienmēr "konverģē" t.i. beidz darbu pēc galīga soļu skaita.

Pierādījums. Algoritma darba procesā būvējam jau zināmo grafu G[S], kur:

- Grafa virsotnes: visas objektu konstantes, kas šobrīd sastopamas kopas formulās; katrai virsotnei d tiek piekārtota "augoša" kopa K(d) no visām tām formulām izskatā C(d), kas šobrīd ir algoritma uzģenerētajā formulu kopā. Tādā veidā visas sākumkopas S formulas un visas formulas, kas tiek uzģenerētas algoritma darba laikā, tiek sagrupētas pa kopām K(d), t.i. pa grafa virsotnēm.

- No virsotnes d uz virsotni e tiek vilkta šķautne, ja algoritma uzģenerētajā kopā ir (vai parādās) kāda formula r(d, e) vai ~r(d, e); un šķautnei tiek piekārtota visu šādu formulu kopa (no algoritma uzģenerētās kopas).

Novērojumi:

1) Algoritma darba sākumā šis grafs būtībā ir patvaļīgs galīgs orientēts grafs. Tā virsotnes atbilst sākumkopā S atrodamajām objektu konstantēm: d, e, .... Ja kopā S ir formula d: C, tad kopā K(d) tiks iekļauta formula C(d). Ja kopā S ir formula (d, e): r vai (d, e): r, tad mūsu grafā no virsotnes d uz virsotni e būs novilkta šķautne, kurai tiks pierakstīta formula r(d, e) vai formula ~r(d, e). Vienai šķautnei var būt pierakstītas vairākas šādas formulas. Nekādu ierobežojumu te nav, tāpēc mūsu grafa sākumstāvoklis būtībā ir patvaļīgs galīgs orientēts grafs.

Kas notiek tālāk?

2) Ja virsotnei c kopā K(c) ir formula A(c)&B(c), un tai tiek izpildīts solis 2, tad kopai K(c) tiek pievienota viena vai divas formulas - A(c) un/vai B(c). Skaidrs, ka formulai A(c)&B(c) neviens no algoritma soļiem turpmāk vairs lietojams nekad nebūs, tāpēc šo formulu mēs varētu atzīmēt kā "apstrādātu". Pievienoto formulu "loģiskais dziļums" ir par vienu mazāks nekā formulas A(c)&B(c) "loģiskais dziļums", un tās ir formulas A(c)&B(c) apakšformulas.

3) Ja virsotnei c kopā K(c) ir formula A(c)vB(c), un tai tiek izpildīts solis 3, tad kopai K(c) tiek pievienota viena no formulām - A(c) vai B(c). Skaidrs, ka formulai A(c)vB(c) neviens no algoritma soļiem turpmāk vairs lietojams nekad nebūs, tāpēc šo formulu mēs varētu atzīmēt kā "apstrādātu". Pievienotās formulas "loģiskais dziļums" ir par vienu mazāks nekā formulas A(c)vB(c) "loģiskais dziļums", un tā ir formulas A(c)vB(c) apakšformula.

3') Ja virsotnei d kopā K(d) ir formula C(d) = (Ey>=n)(r(d,y)&B(y)) vai formula C(d) = (Ey<=n)(r(d,y)&B(y)), un tai tiek izpildīts solis 3', t.i., ja no d uz kādu virsotni e ved šķautne ar formulu r(d, e), bet kopā K(e) nav ne formulas B(e), ne ~B(e), tad kopā K(e) tiek ievietota vai nu formula B(e), vai ~B(e). Pievienotās formulas "loģiskais dziļums" ir par divi mazāks nekā formulas C(d) "loģiskais dziļums", un tā ir formulas C(d) apakšformulas B(y) instance.

Piezīme par "loģisko dziļumu". Visas formulas mums ir negāciju normālformā, un negācijas tajās parādās tikai pie atomiem, tāpēc loģiskā dziļuma definīcijā tās nevajag iekļaut: šo dziļumu veido tikai konjunkcijas, disjunkcijas un kvantori. Arī tad, kad kopai pievienojam formulu ~B(e), tad mēs to pārveidojam negāciju normālformā un tās loģiskais dziļums ir tāds pats kā formulai B(e). Par to viegli pārliecināties ar indukciju pa formulas konstrukciju. [PĀRLIECINĀSIMIES?]

4') Pieņemsim, ka virsotnei d kopā K(d) ir formula C(d) = (E>=n)y (r(d,y)&B(y)), un tai tiek izpildīts solis 4'. T.i., pieņemsim, ka grafā ir tikai k (kur k<n) virsotnes e₁, ..., e_k ar šādu īpašību: a) no virsotnes d uz virsotni e_i ved šķautne r(d, e_i), b) kopā K(e_i) atrodas formula B(e_i), c) algoritms ir uzģenerējis visas formulas ~(e_i=e_j). Tādā gadījumā solis 4' ieved grafā jaunu virsotni e, novelk no d uz e šķautni r(d, e), kopā K(e) ievieto formulu B(e), kā arī uzģenerē visas formulas ~(e_i=e). Pievienotās formulas B(e) "loģiskais dziļums" ir par divi mazāks nekā formulas C(d) "loģiskais dziļums", un tā ir formulas C(d) apakšformulas B(y) instance.

Vēl kas: tā kā solī 4' vienmēr tiek radīta jauna virsotne e (un citi algoritma soļi ne jaunas virsotnes, ne jaunas šķautnes nerada), tad, pirmkārt, jaunajā virsotnē ieies tikai viena šķautne - tā, kuru tikko novilkām, un otrkārt, pie šīs šķautnes būs pierakstīta tikai viena formula - r(d,e). Un no e izejošās šķautnes (kas, varbūt, radīsies vēlak un varēs būt vairākas) vedīs tikai uz jaunradītām virsotnēm. Tātad šis jaunu virsotņu un šķautņu pievienošanas process būtībā ir "koku augšana" (ar "zarošanos"), kas sākas no virsotnēm, kas grafā bija jau sākumstāvoklī. Kopējā aina tātad ir šāda: sākumā mums ir patvaļīgs orientēts grafs, no kura virsotnēm "aug koki".

5') Pieņemsim, ka virsotnei d kopā K(d) ir formula C(d) = (E<=n)y (r(d,y)&B(y)), un tai tiek izpildīts solis 5'. T.i., sameklējam grafā visas virsotnes e₁, ..., e_k, kam no d uz e_i ved šķautne ar formulu r(d, e_i) un kopā K(e_i) atrodas formula B(e_i). Ja izrādās, ka k>n, tad sameklējam visus tos pārus (e_i, e_j), kam i<j un kam kopā nav atrodamam ne formula ~(e_i=e_j), ne formula ~(e_j=e_i). Algoritms izvēlas vienu no šiem pāriem (e_i, e_j), un pieņem, ka drīkst uzskatīt, ka e_i=e_j. Un ja tā, tad algoritms izslēdz no grafa virsotni e_j, "salīmējot" to ar virsotni e_i.

Ko nozīmē "salīmēšana"? Soļa 5' aprakstā teikts: "izslēgsim e_j no visām mūsu kopas formulām, visur aizstājot e_j ar e_i." Mūsu grafā tas nozīmē: a) virsotnes e_j uzlikšanu virsū virsotnei e_i, b) jebkuras šķautnes, kas ved no kādas virsotnes d uz e_j galapunkta e_j pārcelšanu uz e_i (ja no d uz e_i jau ved šķautne, tad šīs divas šķautnes saplūst, un tām pierakstītās formulu kopas apvienojas), c) tas pats par šķautnēm, kas ved no e_j uz kādu virsotni f, d) kopas K(e_j) visās formulās e_j aizstājam ar e_i un pievienojam tās kopai K(e_i).

Svarīgi ir arī tas, ka salīmētas tiek tikai tādas divas virsotnes e un e', uz kurām ved šķautnes no kādas kopīgas virsotnes d ar to vienu un to pašu lomu r(d, e) un r(d, e').

Novērojumi-secinājumi:

a) Katra kopas K(d) formula ir formā C(d), un tā ir dotās formulu kopas S formula, vai arī kādas S formulas kādas apakšformulas C(x) instance C(d). Tātad formulu skaits kopā K(d) nekad nepārsniegs skaitli |S| (kopas S formulu visu apakšformulu kopskaitu).

b) Grafam G[S] augot, uz katru jaunradītu virsotni ved tieši viena šķautne, kam piekārtota tieši viena formula r(d, e) (viss tas rodas solī 4' kopā ar pašu virsotni). Un no jaunradītas virsotnes uz sākumgrafa virsotnēm šķautnes nevar vest.

Pierādīsim šos divus apgalvojumus kā lemmu 1. Solis 4' nevar novest pie šo apgalvojumu pārkāpšanas. Bet solis 5'? Ja solī 5' tiek salīmētas divas virsotnes e un e', tad, kā jau redzējām, uz tām ved šķautnes no kādas kopīgas virsotnes d ar to vienu un to pašu lomu r(d, e) un r(d, e'). Ja e un e' abas pieder sākumgrafam, tad to salīmēšana mūs neinteresē. Ja e un e' abas ir jaunradītas virsotnes, tad varam uzskatīt, ka tām abām izpildās abi lemmas apgalvojumi. Salīmējot e un e', radīsies virsotne e, uz kuru vedīs viena vienīga šķautne ar tieši vienu formulu r(d, e) no virsotnes d, un nekādas šķautnes nevedīs no e uz sākumgrafa virsotnēm. To arī vajadzēja pierādīt. Atliek aplūkot gadījumu, kad e ir jaunradīta virsotne, bet e' - sākumgrafa virsotne. Tā kā no d uz e' ved šķautne, tad d arī ir sākumgrafa virsotne. Tāpēc, salīmējot e un e', varam uzskatīt, ka mums paliek tā pati sākumgrafa virsotne e'. Lemma 1 pierādīta.

Tas nozīmē, ka katrai jaunradītai virsotnei e, "ejot atpakaļ" pa šķautnēm, atbilst tikai viena virsotne d. Tātad, ja neskaita to grafa daļu, kas atbilst dotās kopas S elementiem, tad mūsu grafs sastāv no galīga skaita koku. Katra koka sakne ir kāda konstante c, kas ir dota kopas S formulās (sk. soli 1).

c) Pieņemsim, ka grafa virsotnes d, e savieno šķautne r(d, e), pie tam e ir jaunradīta virsotne. Ko var teikt par formulu kopām K(d) un K(e), kas piekārtotas virsotnēm d un e? Pierādīsim kā lemmu 2 šādu apgalvojumu: katrai kopas K(e) formulai eksistē kopas K(d) formula, kuras "loģiskais dziļums" ir lielāks.

Kopā K(e) jauna formula var rasties 3 veidos: 1) vai nu soļos 2, 3 (t.i. no citas formulas, kas jau ir kopā K(e)), 2) soļos 3', 4' - no kādas formulas, kas ir kopā K(d), 3) solī 5' - "pielīmējot" virsotnei e kādu citu virsotni e'.

Pirmajos divos gadījumos (veidos) varam secināt, ka K(e) formula vai nu "atnāk no K(d)" kā apakšformula, vai rodas kā apakšformula no citas K(e) formulas, t.i. šai K(e) formulai eksistē K(d) formula, kuras "loģiskais dziļums" ir lielāks.

Bet kā ar trešo gadījumu - soli 5'? Sk. lemmas 1 pierādījumu. Ja virsotni e salīmē ar sākumgrafa virsotni e', tad tad tā pati kļūst par sākumgrafa virsotni, un tāpēc mūs vairs neinteresē. Bet ja e salīmē ar citu jaunradītu virsotni e', tad ir skaidrs, ka no virsotnes d uz e' ved tāda pat šķautne r(d, e'), kā no d uz e. Ja lemmas 2 apgalvojums izpildījās kopām K(e), K(e') un K(d) pirms salīmēšanas, tad solī 5' kopas K(e) un K(e') tiks "apvienotas", tāpēc arī apvienotajai kopai lemmas 2 apgalvojums izpildīsies. Lemma 2 pierādīta.

Secinājums: vissarežģītākā K(e) formula ir vienkāršāka par vissarežģītāko K(d) formulu. Bet ejot pa kādu koka zaru mūsu grafā (t.i. radot arvien jaunas virsotnes e) šī formulu sarežģītība nevar dilt neierobežoti - pirms nulles procesam ir jāapstājas. Tātad minētajos mūsu grafa kokos visi zari ir galīgi (un to garums nepārsniedz |S| - kopas S formulu visu apakšformulu skaitu).

d) Pierādisim kā lemmu 3, ka no katras grafa G[S] virsotnes d virzienā uz jaunradītajām virsotnēm var iziet tikai galīgs skaits šķautņu.

Šādas šķautnes rodas tikai solī 4' no kopas K(d) formulām C(d), un nevienai formulai C(d) = (Ey>=n)(r(d,y)&B(y)) šis solis netiks pielietots varāk kā n reizes. Tiešām, soļos 5' notiekošās salīmēšanas "nekaitīgas", jo nekad netiek salīmētas tādas virsotnes e, e', kam algoritma ģenerētajā kopā jau ir iekļauta formula ~(e=e') vai ~(e'=e). Tas nozīmē, ka solis 5' nekad neizjauc soļa 4' darba rezultātus (ja solis 4' kādai formulai C(d) vairs nav lietojams, tad tāds tas paliks visu laiku).

Un to, ka kopas K(d) apjoms, kura satur formulu C(d), ir ierobežots (ar kopas S formulu visu apakšformulu skaitu |S|), mēs jau zinām. Tātad no katras grafa virsotnes d virzienā uz jaunradītajām virsotnēm var iziet ne vairāk kā N*|S| šķautnes, kur N - maksimālais n pie kopas S formulu kvantoriem. Lemma 3 pierādīta.

Saskaņā ar Kēniga lemmu tas viss kopā nozīmē, ka algoritma darba laikā mūsu grafā G[S] virsotņu skaits palielinās tikai līdz noteiktai robežai (t.i. sava darba laikā algoritms ievedīs tikai galīgu skaitu jaunu konstantu e).

Galīgais secinājums: neatkarīgi no soļu 2)-5') izpildes secības, mūsu nedeterminētais algoritms beidz darbu pēc galīga soļu skaita. Tiešām, katrā izpildītā algoritma solī rodas vismaz viena jauna formula B(d), tāpēc, ja algoritma izpildīto soļu skaits būtu bezgalīgs, tad visu kopu K(d) apvienojums arī būtu bezgalīgs. Bet tas nav iespējams, jo mēs jau zinām, ka: 1) katra kopa K(d) ir galīga, 2) dažādo d skaits arī ir galīgs.

Algoritma korektība

Teorēma. Ja algoritma darba rezultāts ir pozitīvs, tad dotā formulu kopa S ir izpildāma. Pie tam attiecīgajā interpretācijā objektu apgabals ir galīgs (Finite model property). Un ja A-kastē nav apgalvojumu par lomām, tad modeļa grafs ir koku kolekcija (Tree model property).

Pierādījums. Ja algoritma darba rezultāts ir pozitīvs, tad aplūkosim formulu kopu, kas darba laikā radusies, un uz tās pamata izveidosim šādu interpretāciju J. Interpretācijas apgabals būs visas objektu konstantes, kas ir dotās kopas S formulās vai ir ievestas darba laikā (t.i. grafa G[S] virsotnes - to skaits ir galīgs). Katras objektu konstantes interpretācija būs pati šī konstante. Vienvietīgo predikātu q interpretācijas definēsim šādi: ja formula q(d) atrodas kopā, tad q(d) būs "patiess", bet ja kopā atrodas formula ~q(d), tad q(d) būs "aplams". Ja kopā nav ne viena, ne otra formula, tad q(d) patiesuma vērtību varam izvēlēties patvaļīgi. Divvietīgo (t.i. lomu) predikātu r(d, e) interpretācijas definēsim šādi: ja formula r(d, e) atrodas kopā, tad r(d, e) būs "patiess", ja neatrodas - tad r(d, e) būs "aplams". Visas konstantes uzskatīsim par dažādiem objektiem, t.i. vienādības predikātu interpretēsim šādi: c=c katrai konstantei c, bet ja c un d ir dažādas konstantes, tad ~(c=d).

Pirmkārt, šīs interpretācijas apgabals ir galīgs (jo galīgs ir augstāk aplūkotais grafs).

Otrkārt, interpretācijā J visas uzģenerētās kopas formulas ir patiesas (t.i. arī dotās kopas S formulas ir patiesas). Tiešām, sāksim ar uzģenerētajam atomārajām formulām (ar vai bez negācijām). Tās visas ir patiesas. Tālāk pierādīsim ar indukciju pa kopas formulu loģisko dziļumu. Aplūkosim kādu kopas formulu G, kas nav atomāra formula ar vai bez negācijas.

1) Ja G ir A(c)&B(c), un solis 2) nav lietojams, tad kopā ir arī abas formulas A(c), B(c). Pēc indukcijas pieņēmuma, tās ir patiesas, tātad patiesa ir arī G.

2) Ja G ir A(c)vB(c), un solis 3) nav lietojams, tad kopā ir arī viena no formulām A(c), B(c). Pēc indukcijas pieņēmuma, šī formula ir patiesa, tātad patiesa ir arī G.

3) Ja G ir (Ey>=n)(r(d,y)&B(y)), un solis 4') nav lietojams, tad mūsu kopā ir atrodamas n dažādas objektu konstantes e₁, ..., e_n, kam kopā atrodas abas formulas r(d, e_i) un B(e_i), un visas formulas ~(e_i=e_j). Pēc indukcijas pieņēmuma, šīs formulas ir patiesas, tātad patiesa ir arī G.

4) Ja G ir (Ey<=n)(r(d,y)&B(y)), pieņemsim no pretējā, ka šī formula mūsu uzbūvētajā interpretācijā ir aplama. Tas nozīmē, ka algoritma darba procesā ir radušās n+1 dažādas objektu konstantes e₁, ..., e_n+1, kam abas formulas r(d, e_i) un B(e_i) ir patiesas. Saskaņā ar mūsu interpretācijas definīciju tad visas formulas r(d, e_i) atrodas uzģenerētajā kopā. Bet kā ar B(e_i)? Tās ir patiesas, bet vai tās atrodas uzģenerētajā kopā? Te tad mums arī ir vajadzīgs solis 3'. Ja formulas G un r(d, e_i) atrodas uzģenerētajā kopā, tad, ja solis 3' nav lietojams, kopā ir jāatrodas vai nu B(e_i), vai ~B(e_i). Tā kā ~B(e_i) ir aplama, un tās loģiskais dziļums ir mazāks nekā formulai G, tad tā nevar atrasties mūsu kopā, t.i. kopa ir jāatrodas formulai B(e_i). Secinājums: algoritma darba procesā ir radušās n+1 dažādas objektu konstantes e₁, ..., e_n+1, kam abas formulas r(d, e_i) un B(e_i) ir uzģenerētajā kopā. Ja uzģenerētajā kopā būtu arī visas formulas ~(e_i=e_j), tad tā būtu "otrā veida" pretruna, bet tas nav iespējams, jo mēs aplūkojam situāciju, kad algoritma darba rezultāts ir pozitīvs. Tātad kāda formula ~(e_i=e_j) kopā nebūs atrodama. Tas nozīmē, ka šajā situācija būtu lietojams solis 5', bet tas nav iespējams. Tātad formula G ir patiesa.

Piezīme. Šeit mēs izmantojām soli 3' tikai formulai (Ey<=n)(r(d,y)&B(y)), nevis Ey>=n. Ko tas varētu nozīmēt?

Tātad jāsecina, ka interpretācijā J patiesas ir visas uzģenerētās kopas formulas, t.i. arī dotās kopas S visas formulas. Q.E.D.

Algoritma pilnība

Teorēma. Ja formulu kopa S ir izpildāma (jebkādā interpretācijā), tad soļos 3, 3' un 5' vienmēr "pareizi izvēloties ceļu", algoritma darba rezultāts būs pozitīvs.

Pierādījums. Aplūkosim jebkuru interpretāciju J, kurā kopas S visas formulas ir patiesas. Algoritma darba laikā paplašināsim šo interpretāciju ar mūsu jaunievestajām konstantēm, bet šo konstantu interpretācijas vienmēr ņemsim no interpretācijas J apgabala (t.i. J apgabalu mēs nepaplašināsim).

Solī 3) vienmēr izvēlēsimies to formulu A vai B, kas interpretācijā J ir patiesa. Solī 3' tāpat - vienmēr izvēlēsimies to formulu B(e) vai ~B(e), kas interpretācijā J ir patiesa. Un solī 5' vienmēr izvēlēsimies tādu konstantu pāri (e_i, e_j), kam abas konstantes e_i, e_j interpretējas par vienu un to pašu objektu no interpretācijas J apgabala.

Parādīsim, ka tad visas algoritma darba laikā radušās formulas būs patiesas mūsu definētajā interpretācijas J paplašinājumā. Sākuma formulu kopā S visas formulas ir patiesas. Aplūkosim tagad algoritma soļus.

1) Ja formula A(c)&B(c) ir patiesa, tad patiesas būs arī solī 2) pievienojamās formulas A(c), B(c).

2) Ja formula A(c)vB(c) ir patiesa, tad patiesa būs arī viena no formulām A(c), B(c). To arī pievienosim solī 3) (tā arī būs mūsu "nedeterminētā izvēle").

3) Ja kopā ir formula C(d) = (Ey>=n)(r(d,y)&B(y)) vai formula C(d) = (Ey<=n)(r(d,y)&B(y)), un kādai konstantei e kopā ir arī formula r(d, e), bet nav ne B(e), ne ~B(e), tad solī 3' ievietojam kopā to formulu B(e), vai ~B(e), kas ir patiesa interpretācijā J (tā arī būs mūsu "otrā veida nedeterminētā izvēle"). (Jo d un e interpretācijas ir objekti no interpretācijas J apgabala.)

4) Ja formula C(d) = (E>=n)y (r(d,y)&B(y)) ir patiesa, bet mūsu kopā ir atrodamas tikai k (kur k<n) dažādas objektu konstantes e₁, ..., e_k, kam kopā atrodas abas formulas r(d, e_i) un B(e_i), un visas formulas ~(e_i=e_j), tad ievedam pilnīgi jaunu objektu konstanti e, un pievienojam kopai formulas r(d, e) un B(e), un visas formulas ~(e_i=e). Konstantes e interpretācija būs objekts, kas atšķiras no visu konstantu e₁, ..., e_k interpretācijām un kam formulas r(d, e) un B(e) ir patiesas. Tāds objekts interpretācijas J apgabalā eksistē, jo formula C(d) šajā interpretācijā ir patiesa. Tad abas pievienotās formulas r(d, e) un B(e) arī būs patiesas.

5) Ja formula C(d) = (E<=n)y (r(d,y)&B(y)) ir patiesa, bet mūsu kopā atrodamas n+1 dažādas objektu konstantes e₁, ..., e_n+1, kam kopā atrodas abas formulas r(d, e_i) un B(e_i), tad visas šīs formulas ir arī patiesas (indukcijas pieņēmums par līdz šim brīdim izpildītajiem algoritma soļiem). Bet ja mūsu kopā atrodamas n+1 dažādas objektu konstantes e₁, ..., e_n+1, kam ir patiesas abas formulas r(d, e_i) un B(e_i), tad divām no šīm konstantēm interpretācija būs viens un tas pats objekts (citādi C(d) nebūtu patiesa formula). Indukcijas pieņēmuma dēļ tad kopā nebūs ne formulas ~(e_i=e_j), ne formulas ~(e_j=e_i). Šādu pāri tad arī izvēlēsimies, izpildot soli 5'. Tā kā e_i un e_j ir viens un tas pats objekts, tad aizstājot e_j ar e_i, formulu patiesums saglabājas. Tāpēc arī pēc soļa 5' izpildes uzģenerētajā kopā visas formulas būs patiesas.

Līdz ar to esam noskaidrojuši, ka - ar "pareizām izvēlēm" soļos 3, 3' un 5' - algoritma darba laikā rodas tikai patiesas formulas. Tāpēc darba rezultātā izveidojas kopa, kurā nevar vienlaicīgi būt ne q(d) un ~q(d), ne r(c, d) un ~r(c, d). Vai tur var būt "otrā veida" pretrunas: "kopā ir formula d: <=n r.C un ir n+1 objektu konstantes e₁, ..., e_n+1, kam kopā ir abas formulas r(d, e_i) un B(e_i) un visas formulas ~(e_i=e_j)."? Arī tas nevar būt, jo visas minētās formulas vienlaicīgi nevar būt patiesas. T.i. algoritma darba rezultāts ir pozitīvs. Q.E.D.

Par skaitlisko ierobežojumu pierakstu unārā vai binārā formā.

Rakstot mūsu formulās kvantorus (E>=n)y... un (E<=n)y..., kādā formā mēs gribētu pierakstīt skaitļus n? Tajos gadījumos, kad n ir mazs skaitlis (0, 1, 2, 3, 4,...), tas, protams, nav svarīgi. Bet ja n ir lielāks skaitlis?

Jautājums. Vai praktiskas dabas uzdevumos kvantoru skaitliskie ierobežojumi ar lieliem skaitļiem var parādīties?

Ja n=1024, tad n unārais pieraksts sastāv no 1024 vieniniekiem: 111...1, bet binārais pieraksts ir daudz īsāks: 10000000000 (desmit nulles). Šis apstāklis var ietekmēt tablo algoritma sarežģītības novērtējumus. Tiešām, algoritma darba laiku mēs cenšamies novērtēt kā funkciju no to formulu kopgaruma, ar kurām algoritms sāk darbu. Ja visi skaitļi mums jāpieraksta unārā formā, tad formulas var iznākt stipri garākas, un tāpēc algoritma darba laika "labs" novērtējums būs vieglāk sasniedzams. Savukārt, ja skaitļus pierakstīsim binārā formā, tad formulas būs īsākas, un tāpēc izveidot "labu" algoritmu būs grūtāk.

Tātad, vismaz teorētiski, ir svarīgi veidot tablo algoritmu tā, lai tā darba laika novērtējums būtu "labs" arī tad, ja skaitliskos ierobežojumus pieraksta binārā formā.

Kā teikts S.Tobies disertācijas 4.nodaļā (41.lpp.), ja skaitliskos ierobežojumus pieraksta unārā formā, tad tikko aprakstītā tablo algoritma versija loģikai ALCQ pieder klasei NPSPACE. Bet ja unārā pieraksta vietā izmantojam bināro pierakstu, tad algoritma darbam nepieciešama jau eksponenciāla atmiņa. Cēlonis ir solis 4', kas formulai (E>=n)y (r(d,y)&B(y)) pakāpeniski ģenerē n objektu konstantes e₁, ..., e_n, kam kopā jāatrodas abām formulām r(d, e_i) un B(e_i), un visām formulām ~(e_i=e_j). Jau šo formulu skaits vien ir eksponenciāls pret bināro ciparu skaitu skaitļa n pierakstā.

Tas nozīmē, ka tikko aprakstītais un izpētītais tablo algoritms loģikai ALCQ labākajā gadījumā izmantos eksponenciālu atmiņu. Tātad, ja vēlamies palikt klasē NPSPACE (polinomiāla atmiņa!), tad mūsu algoritmu vajag vēl vairāk uzlabot. To savā disertācijā ir paveicis S. Tobies.

S. Tobies uzlabotā algoritma versija

Optimizācija tiek panākta ar vēl vienu tablo algoritma versiju loģikai ALCQ (sk. S.Tobies disertācijas 4.nodaļu), kurā nedeterminētās izvēles tiek izmantotas vēl vairāk:

1, 2, 3) kā iepriekš.

3'') [savieno iepriekšējo 3', 4', 5' funkcijas]. Ja kopā ir formula C(d) = (E>=n)y (r(d,y)&B(y)), bet tajā ir atrodamas tikai k (kur k<n) dažādas objektu konstantes e₁, ..., e_k, kam kopā atrodas abas formulas r(d, e_i) un B(e_i), un visas formulas ~(e_i=e_j), kā arī nevienai formulai D(d), kas ir uzģenerētajā kopā, vairs nav lietojami soļi 2, 3, tad ievedam pilnīgi jaunu objektu konstanti e, un pievienojam kopai formulas r(d, e), B(e), visas formulas ~(e_i=e), un arī formulas o₁D₁(e), ..., o_kD_k(e), kur

{D₁, ..., D_k} = {D | kādam skaitlim m formula d: >=m r.D vai formula d: >=m r.D pieder uzģenerētajai kopai}

bet o₁, ..., o_k ir nedeterminēti izvēlētas zīmes " " vai "~". [Tas nozīmē, ka ievedot jauno konstanti e, mēs uzreiz nedeterminēti izvēlamies arī šīs konstantes īpašības attiecībā uz visiem jēdzieniem D, kuri figurē mūsu kopas formulās d: >=m r.D un d: <=m r.D.]

Tiklīdz uzrodas pretruna (viena vai otra veida), jaunais algoritms darbu beidz ar negatīvu rezultātu. Ja soļi 2,3 un 3" vairs nav lietojami un pretrunas nav uzradušās, tad algoritms beidz darbu ar pozitīvu rezultātu.

"Kur mūs novedīs" tik intensīva nedeterminēto izvēļu ekspluatēšana? Minētos tablo algoritmus determinizējot un programmējot, nedeterminētas izvēles nākas aizstāt ar meklēšanas operācijām. Mākslīgā intelekta uzdevumos tā ir parasta lieta (meklēšana dziļumā, meklēšana plašumā utt.).

Un kas notiks, ja lomu inversiju un skaitliskos ierobežojumus atļausim vienlaicīgi, t.i. ja pieņemsim loģiku ALCIQ? Arī tad A-kastes saderības uzdevums (ar tukšu vai aciklisku T-kasti) vēl paliks PSPACE-complete, sk. to pašu jau minēto rakstu:

Yu Ding, Volker Haarslev, and Jiewen Wu. A new mapping from ALCI to ALC. In Proc. of the 20th Int. Workshop on Description Logics (DL'2007), vol. 250 in CEUR, pp. 267–274, Brixen, Italy, June 2007. Available here (pdf) and here (pdf).

3.4.3. Bezgalīgi modeļi

Kādi jauni sarežģījumi mūs sagaida, ja turpināsim ALC paplašināšanu ar jauniem līdzekļiem? Vispirms, mēs varam zaudēt finite model property.

Aplūkosim to pašu loģiku ALCIQ (vai pat tikai ALCIF - sk. zemāk), kurai A-kastes saderības uzdevums (ar tukšu vai aciklisku T-kasti) ir PSPACE-complete, un spersim atlikušo soli - pāriesim uz vispārīgu T-kasti, t.i. atļausim patvaļīgas aksiomas.

Bet, piemēram, ja mums T-kastē ir šāda aksioma (no kursa grāmatas sadaļas 5.8, Calvanese 1996c):

 T <= E padotais.B ^ (<=1 prieksnieks.T); kur T ir universālā klase, bet prieksnieks = padotais^-1.

tad jēdzienam  -B galīgs modelis (interpretācija) nav iespējams, bet ir iespējams bezgalīgs modelis.

Tiešām, aksioma prasa, lai katram indivīdam: a) eksistētu padotais klasē B; b) eksistētu ne vairāk kā viens prieksnieks. Šai aksiomai vienai pašai vēl ir iespējams galīgs modelis - piemēram, noslēgta cilpa, piemēram: d--padotais->e--padotais->f--padotais->d. Te katram darbiniekam ir padotais, un ne vairāk kā viens priekšnieks.

Bet ja mēs gribam, lai klase -B nav tukša, tad tās indivīdam d0 eksistē padotais d1 klasē B. Protams, d1 nevar sakrist ar d0 (kurš nav klasē B). Šim d1 arī eksistē padotais d2 klasē B. Pie tam d2 nevar sakrist ar d0 (kurš nav klasē B) un ar d1 (jo tad d1 būtu divi priekšnieki - d0 un pats d1). Arī d2 eksistē padotais d3, kurš tāpat nevar sakrist ar d0, d1 un d2. Tādā veidā modelis, kurā klase -B nav tukša, nevar būt galīgs.

Bezgalīgu modeli (interpretāciju), kurā ir spēkā minētā aksioma, un kurā klase -B nav tukša, varam uzbūvēt pavisam viegli: indivīdi būs, piemēram, naturālie skaitļi, -B = {0}, B={1, 2, 3, 4, ...}.

Bet, diemžēl, tas nozīmē, ka mēs vairs nevarēsim iztikt ar līdzšinējām metodēm, jo tās mums var dot vienīgi galīgu modeļus (t.i. interpretācijas, kas balstās uz galīgu skaitu objektu konstantu kā interpretācijas apgabalu).

Šim novērojumam ir nepatīkamas sekas tablo algoritmu būvētājiem: jau samērā vienkāršos loģikas ALC paplašinājumos saderīgiem jēdzieniem var neeksistēt galīgi modeļi, un tad tablo algoritms var iecikloties - ja vien tas nebūs speciāli izveidots tā, lai šo situāciju pamanītu. Ciklisku modeļu kontrolētai veidošanai ir vajadzīga speciālas metodes - tādas kā bloķēšana (blocking): ja konstatējam, ka veidojas cikls, tad darbošanās attiecīgajā koka zarā ir jāizbeidz. Kā to praktiski dara - var palasīt gan kursa grāmatā, gan S.Tobies disertācijā.