introduction.tex


\section{Introduzione}
\label{introduction} In questo lavoro viene proposta una estensione del linguaggio 
\datalogc \cite{PalCirc}. \datalogc\  \`{e} un linguaggio logico basato su \datalog, la cui 
innovazione sostanziale consiste nell'aumento della potenza espressiva, tramite 
l'introduzione di una semantica basata sulla circoscrizione, un meccanismo 
deduttivo non monot\`{o}no che generalizza l'ipotesi di mondo chiuso.

Questo tipo di semantica fornisce interessanti vantaggi teorici, ma al tempo
stesso non consente che la valutazione di un programma \datalogc\ sia
affrontabile dal punto di vista pratico, a causa dell'enorme numero di
modelli minimali che un possibile algoritmo di risoluzione dovrebbe prendere
in considerazione. Nonostante questo, \datalogc\ mette in grande risalto
alcune caratteristiche che potrebbero essere utilizzate come modello per un
linguaggio di specifica per la sintesi di algoritmi basati su tecniche
algoritmiche generali.

Prenderemo soprattutto in considerazione il backtracking, una tecnica
algoritmica principalmente fondata sul principio di raffinamento di una
soluzione parziale, e su criteri di sfrondatura dell'albero di ricerca che
si viene a determinare. Si tratta della naturale evoluzione delle semplici
tecniche di enumerazione dello spazio delle soluzioni.

In questo lavoro presenteremo quindi
\SKY\
: un linguaggio che estendendo
\datalogc, permette un utilizzo pi\`{u} intelligente e trasparente delle
potenzialit\`{a} di quest'ultimo, e nel contempo si propone come potente
strumento per la specifica e la generazione di algoritmi risolutivi a
struttura sia enumerativa che tramite backtracking.

%\end{chapter*}

main.bbl
\begin{thebibliography}{Vas98}

\bibitem[BR87]{Balbin}
I.~Balbin and K.~Ramamohanarao.
\newblock A generalization of the differential approach to recursive query
  evaluation.
\newblock {\em Journal of logic programming}, 4(3):259--262, 1987.

\bibitem[CP97]{PalCirc}
M.~Cadoli and L.~Palopoli.
\newblock Circumscribing datalog: expressive power and complexity.
\newblock {\em Theoretical Computer Science}, (193):215--244, 1997.

\bibitem[GJ79]{gare-john-79}
M.~R. Garey and D.~S. Johnson.
\newblock {\em Computers and Intractability, {A} Guide to the Theory of
  {NP}-Completeness}.
\newblock W.H. Freeman and Company, San Francisco, Ca, 1979.

\bibitem[Ull91]{Ullmann}
J.~D. Ullmann.
\newblock {\em Basi di Dati e Basi di Conoscenza}, volume~I.
\newblock Ed. italiana Gruppo Editoriale Jackson, 1991.

\bibitem[Vas98]{vasile}
Domenico Vasile.
\newblock Un linguaggio logico di specifica per la sintesi di algoritmi di
  soluzione di problemi in \uppercase{NP}.
\newblock {\em Universit\`{a} della Calabria, Facolt\`{a} di Ingegneria}, 1998.

\end{thebibliography}
