Logical Methods in Computer Science · 2013 · 17 citations · 19 references
ComputingComputer ScienceMathematicsFormal MethodsProgramming LanguagesTheory Of ComputationEquivalence CheckingFirst-order LogicFunctional ProgrammingModel TheoryPredicate LogicRelational Data ModelCountable ChoiceLogical RelationsNondeterminismNondeterministic ComplexityRelational ReasoningRelational SemanticsSemantic IndexingSemantic Models
Programming languages with countable nondeterministic choice are computationally interesting since countable nondeterminism arises when modeling fairness for concurrent systems. Because countable choice introduces non-continuous behaviour, it is well-known that developing semantic models for programming languages with countable nondeterminism is challenging. We present a step-indexed logical relations model of a higher-order functional programming language with countable nondeterminism and demonstrate how it can be used to reason about contextually defined may- and must-equivalence. In earlier step-indexed models, the indices have been drawn from {\omega}. Here the step-indexed relations for must-equivalence are indexed over an ordinal greater than {\omega}.
19
A foundation for actor computation
Gul Agha, Ian A. Mason, Scott F. Smith et al. · Journal of Functional Programming · 1997 · 452 citations · Full text
Relational Properties of Domains
Andrew M. Pitts · Information and Computation · 1996 · 190 citations
Countable nondeterminism and random assignment
Krzysztof R. Apt, Gordon Plotkin · Journal of the ACM · 1986 · 181 citations · Full text
Equivalence in functional languages with effects
Ian Mason, Carolyn Talcott · Journal of Functional Programming · 1991 · 169 citations · Full text