Dipartimento di Informatica e Scienze dell'Informazione- Genova

Linguaggi Logici
Risultati



 

La ricerca afferente a questa tematica si articola nei seguenti sottotemi:
redball.gif (904 byte) Linguaggi logici con vincoli basati su semiring.

redball.gif (904 byte) Programmazione logica lineare.

redball.gif (904 byte) Semantica della Programmazione Logica.

redball.gif (904 byte) Composizionalità nei linguaggi logici.

 


Linguaggi logici con vincoli basati su semiring

L'attività di ricerca in questo sottotema ha visto la partecipazione dei ricercatori dell'unità di Catania e di Pisa.


L'attività relativa a questo sottotema è basata su una nozione molto generale di vincoli soft che permette di esprimere preferenze, costi, probabilità, e altro nell'ambito di vincoli con variabili a dominio finito [BMR95] [BMR97a]. Questa nozione di vincoli si basa su un concetto simile al semiring, che con le sue operazione permette di definire come combinare i vincoli e come confrontarli tra loro.

Sulla base di questa nozione, abbiamo studiato come i linguaggi logici con vincoli (CLP) potessero includere l'uso di questi vincoli, definendo uno schema CLP appropriato e dandogli le opportune semantiche: dichiarativa, di punto fisso, e operazionale [BMR97b].

Sempre nell'ambito dei problemi di vincoli basati sui semiring, abbiamo considerato il problema di modellare un problema reale come problema di vincoli, e abbiamo sviluppato un approccio, basato sulle techniche di apprendimento con discesa di gradiente, che permette all'utente di specificare solo alcuni esempi di preferenze per alcune soluzioni, e di apprendere poi il resto del problema di vincoli [RS98]. Risultati sperimentali hanno dimostrato la validità di questo approccio, che, se opportunamente tarato (per esempio usandone una versione incrementale), produce risultati ragionevoli con un numero di esempi non troppo grande.

Considerando invece i vincoli classici (dove i vincoli sono o soddisfatti o violati, senza possibilità di dare preferenze), abbiamo studiato il problema di fornire ai programmi logici con vincoli la possibilità di cancellare vincoli oltre che di aggiungerli durante una computazione [GCR97] [GCR98], senza però dover ripartire dallo stato presedente all'aggiunta di tali vincoli. Gli algoritmi sviluppati, pensati per il sistema di vincoli a dominio finito fd e implementati all'interno del linguaggio logico con vincoli clp(fd), hanno mostrato un overhead non significativo quando non ci sono cancellazioni, e un comportamento molto migliore rispetto ad approcci non incrementali nel caso di cancellazioni durante le computazioni.

Nell'ambito inoltre della specifica operazionale di linguaggi logici è stato sviluppato un modello astratto per la semantica operazionale del linguaggio SCLP (Semiring Constraint Logic Programming), una estenzione del formalismo di CLP (Constraint Logic Programming) per trattare sistemi con vincoli basati sulla struttura di semianello. In [BR97] viene presenta una descrizione completa della semantica operazionale del linguggio, basata sul formalismo delle ASMs (Abstract State Machines) di Gurevich. Tale modello può essere assunto come base teorica per realizzare una reale implementazione del linguaggio, ottenibile mediante raffininamenti successivi di modelli ASM fino ad un livello in cui la specifica può essere tradotta meccanicamente in codice eseguibile.


Articoli

[BMR95] S. Bistarelli, U. Montanari, F. Rossi, Constraint Solving over Semirings , in Proc. IJCAI95, Morgan Kaufmann, 1995.

[BMR97a] S. Bistarelli, U. Montanari, F. Rossi, Semiring-based Constraint Solving and Optimization, in Journal of ACM, vol.44, n.2, pp. 201-236, March 1997.

[BMR97b] S. Bistarelli, U. Montanari, F. Rossi, Semiring-based Constraint Logic Programming, in Proc. IJCAI97, Morgan Kaufmann, 1997.

[BR97] S.Bistarelli, E.Riccobene, An Operational Model for the SCLP Language, Proc. Workshop on Tools and Environments for (Constraint) Logic Programming (in association with ILPS '97), Oct. 1997.

[GCR97] Y. Georget, P. Codognet, F. Rossi, Implementing Constraint Retraction for Finite Domains, in Proc. ASIAN97 conference, Kathmandu, Nepal, December 1997, Springer-Verlag.

[GCR98] Y. Georget, P. Codognet, F. Rossi, Constraint Retraction in CLP(FD): Formal Framework and Performance Results, in CONSTRAINTS: An international journal, Kluwer, 1998.

[RS98] F. Rossi, A. Sperduti, Learning solution preferences in constraint problems, in Journal of Theoretical and Experimental Artificial Intelligence (JETAI), Vol. 10, 1998, Taylor and Francis publisher.


Programmazione logica lineare

L'attività di ricerca in questo sottotema ha visto la partecipazione dei ricercatori dell'unità di Genova.


In questo ambito l'attività si è concentrata sul linguaggio logico lineare di ordine superiore Ehhf [Del97]. Tale linguaggio è stato utilizzato per codificare descrizioni di vari paradigmi di programmazione con aspetti di object-orientation e di concorrenza [DM98], ed in particolare per la completa formalizzazione degli gli aspetti computazionali di un sistema per la gestione di basi di dati orientate ad oggetti, attive e deduttive [BDM97].

Inoltre la programmazione logica lineare è stata utilizzata per una assiomattizzazione di sistemi per la riscrittura di termini, che può essere utilizzata per la dimostrazione di proprietà del sistema. [Del98].

Su un altro versante, si è cominciata a studiare l'utilizzazione della programmazione logica lineare come linguaggio di specifica per la prototipizzazione rapida di sistemi multi-agente [BDMMZ98a], focalizzando sulla modellizzazione del comportamento computazionale di particolari architetture di agente [BDMMZ98b].


Articoli

[Del97] G. Delzanno, "Logic & Object-Oriented Programming in Linear Logic", Università di Pisa, Tesi di PhD, Dipartimento di Informatica, marzo 1997.

[DM98] G. Delzanno, M. Martelli, "Proofs as Computations in Linear Logic", DISI, Università di Genova, Technical Report DISI-TR-98-12, 1998.

[BDM97] M. Bozzano, G. Delzanno, M. Martelli, "A Linear Logic Specification of Chimera", Proceedings of DYNAMICS'97, a satellite workshop of ILPS '97, 1997

[Del98] G. Delzanno, "Refining Logical Specification of Term Rewriting", Proceedings of the workshop Proof Search in Type Theoretical Languages a satellite workshop of CADE 98, giugno 1998.

[BDMMZ98a] M. Bozzano, G. Delzanno, M. Martelli, V. Mascardi, F. Zini, "Logic Programming & Multi-Agent Systems: a Synergic Combination for Applications and Semantics", DISI, Università di Genova, Technical Report DISI-TR-98-13, 1998.

[BDMMZ98b] M. Bozzano, G. Delzanno, M. Martelli, V. Mascardi, F. Zini, "Multi-Agent Systems Development as a Software Engineering Enterprise", Accepted at PADL'99, 1998.


Semantica della Programmazione Logica

L'attività di ricerca in questo sottotema ha visto la partecipazione dei ricercatori dell'unità di Pisa.



In questo ambito è stata proposta una semantica per programmi logici basata su formule ereditarie di Harrop al prim'ordine che sono espresse in termini di derivazioni intuizioniste [LM98]. 

Articoli

[LM98] Lastres E., Moreno R., "A semantics for logic programs based on first order hereditary Harrop formulas", Joint Conferenece on Declarative Programming AGP'98, A Coruna, Spain, July 1998.


Composizionalità nei linguaggi logici

L'attività di ricerca in questo sottotema ha visto la partecipazione dei ricercatori dell'unità di Venezia.


La ricerca relativa a questo sottotema si pone nell'area della rappresentazione della conoscenza. Nella logica OLP-FOL tale rappresentazione viene divisa in due parti: una parte di definizione Td che contiene le definizione dei predicati noti ed una parte di vincoli Tc che esprime una conoscenza parziale su altri concetti.

La parte Td assume la forma di un programma logico con negazione "aperto" (Open Logic Program) mentre la parte Tc è un insieme di assiomi in una logica del primo ordine (First Order Logic).

Il problema della composizionalità di due teorie OLP-FOL nasce dalla necessità di comporre conoscenze sviluppate in ambiti diversi da diversi esperti. In [VB98] vengono introdotti due operatori su teorie OLP-FOL e viene mostrato come tali operatori possono essere utilizzati per comporre teorie anche quando entrambe le teorie definiscono uno stesso predicato.


Articoli

[VB98] S. Verbaeten and A. Bossi, "Composing complete and partial knowledge.", International Workshop on Component-based Software Development in Computational Logic (COCL), September 19, 1998 - Pisa (Italy)



Commenti e suggerimenti a: martelli@disi.unige.it
Ultimo aggiornamento: 19 dicembre 1998