People

Research activity in 1995

L'attivita' di questo gruppo si colloca principalmente nell'area della Programmazione Logica, del Ragionamento Non-Monotono e delle Basi di Dati Deduttive ed e' stata svolta nell'ambito del progetto ESPRIT BRA Medlar II, del progetto CNR "Ambienti e strumenti per la gestione di informazioni temporali" e del Working Group "Logic and Change". Tale attivita' ha stretti collegamenti con l'attivita' svolta dal gruppo di Intelligenza Artificiale.

Per quanto riguarda la programmazione logica, l'attivita' di ricerca e' stata principalmente rivolta alla definizione di estensioni delle clausole di Horn che ne aumentino il potere espressivo senza pregiudicarne la chiarezza semantica e la dichiarativita'. In particolare, si sono affrontate le seguenti tematiche:

(1) estensioni modali: meccanismi di strutturazione dei programmi e modalita' epistemiche,
(2) ragionamento ipotetico,
(3) ragionamento su azioni,
(4) negazione "classica",
(5) negazione per fallimento,
(6) espressivita' di logiche nonmonotone.

I punti (2), (3), (4), (5) e (6) coinvolgono problematiche di ragionamento non-monotono.

(1) E' stata definita un'estensione modale della programmazione logica che, da un lato consente di strutturare un programma logico in moduli e dall'altro, permette di modellare le credenze di agenti. Il linguaggio contiene modalita' della forma [ai] (per rappresentare le credenze dell'agente i-esimo) e una [] modalita' che rappresenta la "conoscenza comune" a tutti gli agenti. Tali modalita' possono essere utilizzate per strutturare la conoscenza in moduli: le modalita' [ai] vengono associate ai singoli moduli ed utilizzate sia per definire i moduli stessi che per fare delle query su di essi. La modalita' [] viene utilizzata per definire cio' che i singoli moduli esportano. In tale linguaggio e' possibile realizzare differenti tipi di composizione di moduli come anche fare ragionamenti di tipo ipotetico.

(2) Per quanto riguarda il ragionamento ipotetico, da un lato e' stato studiato il problema di introdurre la negazione per fallimento in N_Prolog, un linguaggio di programmazione logica che permette di formulare "query" di tipo ipotetico. Dall'altro, e' stato definito un linguaggio che permette di fare aggiornamenti ipotetici in presenza di vincoli e possiede meccanismi di revisione delle credenze che mantengono la base di conoscenza consistente. Tale linguaggio permette di ragionare su basi di conoscenza priorizzate e di aggiornarle e fornisce gli strumenti per fare ragionamento di tipo condizionale, controfattuale e non-monotono. Per esso sono state definite una semantica abduttiva ed una procedura di prova diretta dal goal che calcola le soluzioni abduttive.

(3) La logica modale permette di formalizzare il ragionamento su azioni in modo molto naturale, rappresentando le azioni come modalità. In questo contesto è stato sviluppato un linguaggio di programmazione logica modale, che estende il linguaggio A di Gelfond e Lifschitz, e permette di trattare il problema della "ramificazione", facendo uso di relazioni "causali" fra i fluenti. Tale linguaggio ha una semantica abduttiva e una procedura di prova diretta dal goal.

(4) La negazione "esplicita" (o "classica") consente di aumentare l'espressivita' dei linguaggi logici, e solitamente tale estensione consiste nell'introdurre nuovi atomi per rappresentare i letterali negativi. E' stata proposta invece una caratterizzazione semantica della negazione esplicita, basata sull'idea di utilizzare le logiche a tre valori per dare un'interpretazione ai programmi. Variando la logica si ottiene un framework unificante che cattura semantiche differenti. In particolare, quella basata sulla logica di Lucasiewicz aumenta il potere espressivo del linguaggio senza aumentarne la complessita' computazionale.

(5) Per quanto riguarda la negazione per fallimento, oltre alle ricerche gia' menzionate in relazione al ragionamento ipotetico e alla negazione classica, si e' indagata l'interpretazione abduttiva della negazione per fallimento e si e' definita una semantica che generalizza la "semantica dei modelli stabili" e permette di modellare i risultati della procedure abduttiva di Eshghi e Kowalski.

(6) E' stata anche studiata l'espressivita' delle principali logiche nonmonotone e di alcuni dei piu' popolari linguaggi di programmazione logica, usati come linguaggi di interrogazione per database disgiuntivi. I risultati evidenziano le differenze di espressivita' nei suddetti formalismi, che nell'ambito dei database relazionali hanno la stessa espressivita'. Per uno dei risultati negativi, e' stata introdotta una nuova tecnica di dimostrazione basata su counting argument.

Un altro tema di ricerca affrontato è quello della programmazione logica e basi di dati. A questo riguardo, in collaborazione con il prof. V. S. Subrahmanian dell'Universita' di Maryland, e' stato studiato il problema della sicurezza nei Sistemi Mediati (sistemi che integrano basi di dati eterogenee mediante un mediatore). In particolare, e' stata data una caratterizzazione formale di Sistemi Mediati che consentono agli utenti operazioni di aggiornamento, oltre a quelle di interrogazione, garantendo il rispetto della sicurezza sia a livello locale (cioe' a livello dei singoli domini integrati dal sistema), sia a livello globale (cioe', sulle relazioni derivate definite dal mediatore).
La caratterizzazione formale e' basata sul concetto di vista sicura, mediante il quale di definiscono una nozione di stato del sistema, ed una nozione di transizione di stato, in corrispondenza di operazioni di interrogazione e di aggiornamento da parte degli utenti. Sono stati inoltre sviluppati algoritmi di aggiornamento e di risposta alle interrogazioni, che consentono di preservare la sicurezza in Sistemi Mediati.

Altri temi di ricerca del gruppo sono stati: la definizione di procedure di prova dirette dal goal per frammenti implicazionali di logiche modali e substrutturali (come la logica rilevante e la logica lineare) e la caratterizzazione semantica di linguaggi di programmazione logica estesi con operatori espliciti di controllo.

1995 Publications

P. Bonatti and T. Eiter, "Querying disjunctive databases through nonmonotonic logics," in Proc. of the International Conference on Database Theory (ICDT-95) - LNCS 893, Springer-Verlag, 1995.

P. Bonatti, "A three-valued formalization of provability," Journal of Logic and Computation, vol. 5, 173-201, 1995.

P. Bonatti, "Autoepistemic logics as a unifying framework for the semantics of logic programs," Journal of Logic Programming, vol. 22, 91-149, 1995.

P. Bonatti, S. Kraus, and V.S. Subrahmanian, "Foundations of secure deductive databases," IEEE Trans. on Knowledge and Data Engineering, vol. 7, 406-422, 1995.

A.V. P. Bonatti, "On the meaning of complementary systems," in Proc. of the 10th Int. Congress of Logic, Methodology and Philosophy of Science, Firenze, 1995.

L.G. L.G. and A.M. A.M., "A Logical Characterization for Truth Maintenance Systems with Dependency-Directed Backtracking," Computational Intelligence, vol. 11, no. 1, 11-46, 1995.

P.A. Bonatti and L.G. L.G., "Three-valued semantics for Extended logic programming," in Proc. 1994 joint Conf. on Declarative Programming GULP-PRODE'95, 1995.

L. Console, M.L. Sapino, and D.T. Dupre`, "The Role of Abduction in Database View Updating," Journal of Intelligent Information Systems, vol. 4, no. 3, 261-280, 1995.

D.M. Gabbay, L. Giordano, A. Martelli, and N. Olivetti, "Hypothetical updates, priority and inconsistency in a logic programming language," in Third Int. Conference on Logic Programming and Non-monotonic Reasoning, vol. 928V.W. Marek, A. Nerode, and M. Truszczynsky, Springer Verlag, Lexington, KY, USA, 1995, pp. 203-216.

A. Martelli, Logic Programming and Nonmonotonic Reasoning, in "Ten Years of Logic Programming in Italy" (Maria I. Sessa ed.), Cap. 4, Palladio, 1995, 105-136.