|
Il titolo completo è, in realtà: Sistemi di Riscrittura e Quasi-Interpretazioni: alcune questioni di Complessità Computazionale È stato un progetto condotto come tesi di laurea specialistica (a.a. 2005/2006, III sessione) in cui si è valutato l'impiego di alcune tecniche formali per la valutazione di alcune classi di complessità computazionale estensionale. Le tecniche di analisi erano una composizione di: sistemi di riscrittura al prim'ordine, sistemi di riscrittura all'ordine superiore, procedure di traduzione da sistemi all'ordine superiore verso sistemi al prim'ordine, quasi-interpretazioni e recursive-path orderings. Le classi di computazione interessate erano: PSPACE, LinExpSPACE, LinDoubleExpSPACE, LinSPACE, PTIME, LinExpTIME, LinDoubleExpTIME.
La tesi partiva da una tecnica nota per caratterizzare classi di complessità computazionale, sviluppata da Bonfante, Marion e Moyen e basata su sistemi di riscrittura al prim'ordine e quasi-interpretazioni, e dalla convinzione comune che tali tecniche potessero essere elevate a sistemi di riscrittura all'ordine superiore semplicemente applicando una delle trasformazioni note da sistemi all'ordine superiore verso sistemi al prim'ordine. Con questo lavoro abbiamo sperimentato due tecniche di traduzione: una dovuta a Delia Kesner, e l'altra nota col nome di defunzionalizzazione, sviluppata da Reynolds. Abbiamo mostrato come l'applicazione di queste tecniche di traduzione apportano gravi problemi alla successiva analisi della complessità computazionale, rendendo questa "composizione" inefficace.
Aggiungi questa pagina al tuo Social Network preferito
|
Un messagio di benvenuto a Stefania e a tutte le persone nuove!!! Continuate a scriverci e a seguirci!!!
Ciao ragazzi....bellissimo sito e bellissima iniziativa.....ho anche io questo "ospite sgradito" in testa!...1bacione grande grande e in bocca al lupo a tutti quanti!!!!!!
Grazie Nadia, l'esame dei seni petrosi li ha fatti a Milano tuo figlio o tutto a Pisa? Grazie
Grazie valeria,farò sapere ora devo trovare un buon medico Ciao
ciao e scusami se ti rispondo solo ora.. allora a me hanno dato per quasi due mesi il nicetile, 3 volte al giorno,l'expose, il b-total ( o qualcosa di simile ) e il laroxyl. siccome il mio corpo n...