Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T10:57:23.938Z Has data issue: false hasContentIssue false

Two-level nominal sets and semantic nominal terms: an extension of nominal set theory for handling meta-variables

Published online by Cambridge University Press:  27 May 2011

MURDOCH J. GABBAY*
Affiliation:
School of Mathematical and Computer Sciences, Heriot-Watt University, Edinburgh, Scotland
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Nominal sets are a sets-based first-order denotation for variables in logic and programming. In this paper we extend nominal sets to two-level nominal sets. These preserve much of the behaviour of nominal sets, including notions of variable and abstraction, but they include a denotation for both variables and meta-variables. Meta-variables are interpreted as infinite lists of distinct variable symbols. We use two-level sets to define, amongst other things, a denotation for meta-variable abstraction, and nominal style datatypes of syntax-with-binding with meta-variables. We discuss the connections between this and nominal terms and prove a soundness result.

Information

Type
Paper
Copyright
Copyright © Cambridge University Press 2011