Riscrittura

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

Controllo di autorità	LCCN (EN) sh87003035 · J9U (EN, HE) 987007534479305171