Sulla riscrittura dei termini in presenza di effetti probabilistici

Nel contesto intersezionale a cavallo fra riscrittura dei termini e teoria delle probabilità, vengono presentati gli ordini probabilisticamente monotoni, una tecnica per costurire sistemi astratti di riduzione probabilistici (come definiti da Avanzini et al. [2]) a partire da sistemi astratti di riduzione. Vengono definite due varianti di questo metodo. Per entrambe, viene dimostrato che gli ordini probabilisticamente monotoni così generati sono quasi certamente terminanti forti (SAST, Strong Almost-Sure Terminating), e viene mostrato un esempio pratico di costruzione di tali ordini. Viene infine provato che esistono ordini di percorso lessicografici (LPO, Lexicographic Path Orders) che non soddisfano i prerequisiti necessari per indurre ordini probabilisticamente monotoni di alcun tipo.