Lazy AC-Pattern Matching for Rewriting

Walid Belkhir (1, 2) , Alain Giorgetti (1, 2)

1 FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174)
2 CASSIS - Combination of approaches to the security of infinite states systems

We define a lazy pattern-matching mechanism modulo associativity and commutativity. The solutions of a pattern-matching problem are stored in a lazy list composed of a first substitution at the head and a non-evaluated object that encodes the remaining computations. We integrate the lazy AC-matching in a strategy language: rewriting rule and strategy application produce a lazy list of terms

Domaines: Logique en informatique [cs.LO]

Walid Belkhir, Alain Giorgetti. Lazy AC-Pattern Matching for Rewriting. 10th International Workshop on Reduction Strategies in Rewriting and Programming, May 2011, Novi Sad, Serbia. pp.37-51, ⟨10.4204/EPTCS.82.3⟩. ⟨hal-00756343⟩