A Rule-Based Framework for Solving Regular Context Sequence Constraints

Abstract. We propose a framework for solving equational and membership constraints for terms built over individual, sequence, function, and context variables and flexible arity symbols. Each membership constraint couples a variable with a regular expression on terms or contexts. There can be several membership constraints with the same constrained variable, and expressions may contain variables themselves. A membership constraint is satisfied if an instance of the constrained variable belongs to the language generated by the corresponding instance of the regular expression. We identify sufficient syntactic restrictions that allow us to use matching techniques for solving such constraints, describe a complete algorithm, and discuss applications.