Computer Science – Programming Languages
Scientific paper
2011-06-17
LMCS 7 (3:6) 2011
Computer Science
Programming Languages
Scientific paper
10.2168/LMCS-7(3:6)2011
Nominal abstract syntax is a popular first-order technique for encoding, and reasoning about, abstract syntax involving binders. Many of its applications involve constraint solving. The most commonly used constraint solving algorithm over nominal abstract syntax is the Urban-Pitts-Gabbay nominal unification algorithm, which is well-behaved, has a well-developed theory and is applicable in many cases. However, certain problems require a constraint solver which respects the equivariance property of nominal logic, such as Cheney's equivariant unification algorithm. This is more powerful but is more complicated and computationally hard. In this paper we present a novel algorithm for solving constraints over a simple variant of nominal abstract syntax which we call non-permutative. This constraint problem has similar complexity to equivariant unification but without many of the additional complications of the equivariant unification term language. We prove our algorithm correct, paying particular attention to issues of termination, and present an explicit translation of name-name equivariant unification problems into non-permutative constraints.
No associations
LandOfFree
Constraint solving in non-permutative nominal abstract syntax does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Constraint solving in non-permutative nominal abstract syntax, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constraint solving in non-permutative nominal abstract syntax will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-695845