Riscrittura

Questa voce sugli argomenti teorie dell'informatica e logica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

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.