Lazy AC-Pattern Matching for Rewriting
Open Access
- 24 April 2012
- journal article
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 82, 37-51
- https://doi.org/10.4204/eptcs.82.3
Abstract
Extended version of hal-00642515 written in 2012International audienceWe 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 termThis publication has 11 references indexed in Scilit:
- A ρ-calculus of explicit constraint applicationHigher-Order and Symbolic Computation, 2007
- Towards a Strategy Language for MaudeElectronic Notes in Theoretical Computer Science, 2005
- Single Elementary Associative-Commutative MatchingJournal of Automated Reasoning, 2002
- Stratego: A Language for Program Transformation Based on Rewriting Strategies System Description of Stratego 0.5Lecture Notes in Computer Science, 2001
- REWRITING WITH STRATEGIES IN $\mathsf{ELAN}$: A FUNCTIONAL SEMANTICSInternational Journal of Foundations of Computer Science, 2001
- Promoting rewriting to a programming language: a compiler for non-deterministic rewrite programs in associative-commutative theoriesJournal of Functional Programming, 2001
- Fast matching in combinations of regular equational theoriesElectronic Notes in Theoretical Computer Science, 1996
- Associative-commutative matching via bipartite graph matchingThe Computer Journal, 1995
- Complexity of matching problemsLecture Notes in Computer Science, 1985
- Orderings for term-rewriting systemsTheoretical Computer Science, 1982