PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Lagana' M., Leoni G., Pinzani R., Sprugnoli R. Improvements in the execution of Markov algorithms. Internal note IEI-B74-45, 1974.
 
 
Abstract
(English)
No abstract available
Abstract
(Italiano)
Il concetto di Algoritmo Normale di Markov (ANM) é usato in vari campi della Matematica, tutte le volte in cui sia necessario un algoritmo formale ( cioé non numerico). Presentiamo qui una generalizzazione degli ANM, mostrando le loro relazioni con le altre formulazioni della Teoria della Computabilita; tale generalizzazione permette di formalizzare lo sviluppo di un metodo (detto degli scheletri), che viene introdotto per risolvere problemi relativi agli ANM. Il problema, in cui siamo maggiormente interessati, riguarda la lentezza intrinseca nella esecuzione di un ANM; per prima cosa introduciamo il concetto di puntatore, che permette di migliorare le prestazioni di un algoritmo di un fattore proporzionale alla lunghezza della parola alla quale l'algoritmo stesso viene applicato. Dimostriamo poi che il problema di sapere se, dato un simbolo, esso sia un puntatore per un dato algoritmo é ricorsivamente insolubile. Il metodo degli scheletri dą una soluzione interessante, anche se parziale, al problema di riconoscere i puntatori e di verificare se un certo simbolo sia in realtą un puntatore. Infine diamo alcune indicazioni su come il metodo degli scheletri possa essere usato per provare la correttezza di un algoritmo.
Subject


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional