Sulla complessità della sussunzione in linguaggi a frame con restrizioni numeriche

Tra i linguaggi di rappresentazione della conoscenza più popolari oggi in uso vi sono certamente quelli basati sulla nozione di frame, detti Frame Representation Languages (FRLs); tali linguaggi permettono di rappresentare conoscenza di natura tassonomica mediante costrutti fortemente strutturati. Ultimamente sono apparsi nella letteratura svariati risultati relativi alla complessità computazionale del calcolo della sussunzione nei FRLs. La maggior parte di questi risultati sono purtroppo "negativi", nel senso che mostrano che i FRLs presi in considerazione sono computazionalmente intrattabili. In questa nota, dopo una breve rassegna riguardante i concetti fondamentali che stanno alla base dei FRLs e i risultati attualmente noti e relativi al calcolo della sussunzione, mostriamo che tale operazione è trattabile nel linguaggio FL ? N-, un'estensione del linguaggio FL- di Brachman e Levesque. Il linguaggio FL ? N- è dunque il linguaggio più espressivo fra quelli fino a oggi noti per essere computazionalmente trattabili.