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, dato un oggetto, di applicare diverse regole, è 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.
Bibliografia Nachum Dershowitz and Jean-Pierre Jouannaud. Rewrite Systems (1990). Capitolo 6 di Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics (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
Voci correlate Lambda calcolo Mathematica
Categoria:Teoria dei linguaggi formali Categoria:Teoria della computazione Categoria:Implementazione dei linguaggi di programmazione Categoria:Logica nell'informatica