Riscrittura

Da Wikipedia, l'enciclopedia libera.

In matematica, informatica e logica, la riscrittura è la sostituzione di un oggetto al posto di una parte di un altro oggetto, secondo una precisa regola formale. Un sistema di riscrittura è appunto costituito da un insieme di oggetti, per esempio termini, grafi o altri oggetti matematici, e un insieme finito di regole che definiscono una relazione sugli oggetti. Quando un sistema di riscrittura permette che, dato oggetto esistano diverse regole applicabili, è chiamato non deterministico e talvolta integrato da una strategia di scelta. Quest'ultimo caso è particolarmente interessante nella teoria dei linguaggi di programmazione, perché diversi linguaggi dichiarativi (funzionali o logici) sono studiati come sistemi di riscrittura di termini.

Voci correlate[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

  • Nachum Dershowitz and Jean-Pierre Jouannaud. Rewrite Systems (1990). Capitolo 6 di Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pp.243–320.
  • Term Rewriting Systems, Terese, Cambridge Tracts in Theoretical Computer Science, 2003
  • Term Rewriting and All That, Franz Baader and Tobias Nipkow, Cambridge University Press, 1998