The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
C Verhoef - One of the best experts on this subject based on the ideXlab platform.
-
structural Operational Semantics
Handbook of Process Algebra, 2001Co-Authors: Luca Aceto, Wan Fokkink, C VerhoefAbstract:This appendix introduces the basics of structural Operational Semantics [171], which defines a labelled transition system over a term algebra. An up-to-date overview of structural Operational Semantics is given in [3].
-
a conservative look at Operational Semantics with variable binding
Information & Computation, 1998Co-Authors: Wan Fokkink, C VerhoefAbstract:We set up a formal framework to describe transition system specifications in the style of Plotkin. This framework has the power to express many-sortedness, general binding mechanisms, and substitutions, among other notions such as negative hypotheses and unary predicates on terms. The framework is used to present a conservativity format in Operational Semantics, which states sufficient criteria to ensure that the extension of a transition system specification with new transition rules does not affect the Semantics of the original terms.
-
a congruence theorem for structured Operational Semantics with predicates and negative premises
Nordic Journal of Computing, 1995Co-Authors: C VerhoefAbstract:We proposed a syntactic format, the panth format, for structured Operational Semantics in which besides ordinary transitions also predicates, negated predicates, and negative transitions may occur such that if the rules are stratifiable, strong bisimulation equivalence is a congruence for all the operators that can be defined within the panth format. To show that this format is useful we took some examples from the literature satisfying the panth format but no formats proposed by others. The examples touch upon issues such as priorities, termination, convergence, discrete time, recursion, (infinitary) Hennessy-Milner logic, and universal quantification.
-
a congruence theorem for structured Operational Semantics with predicates and negative premises
International Conference on Concurrency Theory, 1994Co-Authors: C VerhoefAbstract:We proposed a syntactic format, the panth format, for structured Operational Semantics in which besides ordinary transitions also predicates, negated predicates, and negative transitions may occur such that if the rules are stratifiable, strong bisimulation equivalence is a congruence for all the operators that can be defined within the panth format. To show that this format is useful we took some examples from the literature satisfying the panth format but no formats proposed by others. The examples touch upon issues such as priorities, termination, convergence, discrete time, recursion, (infinitary) Hennessy-Milner logic, and universal quantification. Collation: pp. 16, ill. 2, tab. 5, ref. 25.
Slim Abdennadher - One of the best experts on this subject based on the ideXlab platform.
-
Operational Semantics and confluence of constraint propagation rules
Lecture Notes in Computer Science, 1997Co-Authors: Slim AbdennadherAbstract:Constraint Handling Rules (CHR) allow one to specify and implement both propagation and simplification for user-defined constraints. Since a propagation rule is applicable again and again, we present in this paper for the first time an Operational Semantics for CHR that avoids the termination problem with propagation rules. In previous work [AFM96], a sufficient and necessary condition for the confluence of terminating simplification rules was given inspired by results about conditional term rewriting systems. Confluence ensures that the solver will always compute the same result for a given set of constraints independent of which rules are applied. The confluence of propagation rules was an open problem. This paper shows that we can also give a sufficient and a necessary condition for confluence of terminating CHR programs with propagation rules based on the more refined Operational Semantics.
Christian Holzbaur - One of the best experts on this subject based on the ideXlab platform.
-
the refined Operational Semantics of constraint handling rules
International Conference on Logic Programming, 2004Co-Authors: Gregory J Duck, Peter J Stuckey, Maria Garcia De La Banda, Christian HolzbaurAbstract:Constraint Handling Rules (CHRs) are a high-level rule-based programming language commonly used to write constraint solvers. The theoretical Operational Semantics for CHRs is highly non-deterministic and relies on writing confluent programs to have a meaningful behaviour. Implementations of CHRs use an Operational Semantics which is considerably finer than the theoretical Operational Semantics, but is still non-deterministic (from the user’s perspective). This paper formally defines this refined Operational Semantics and proves it implements the theoretical Operational Semantics. It also shows how to create a (partial) confluence checker capable of detecting programs which are confluent under this Semantics, but not under the theoretical Operational Semantics. This supports the use of new idioms in CHR programs.
Tarmo Uustalu - One of the best experts on this subject based on the ideXlab platform.
-
trace based coinductive Operational Semantics for while
Theorem Proving in Higher Order Logics, 2009Co-Authors: Keiko Nakata, Tarmo UustaluAbstract:We present four coinductive Operational Semantics for the While language accounting for both terminating and non-terminating program runs: big-step and small-step relational Semantics and big-step and small-step functional Semantics. The Semantics employ traces (possibly infinite sequences of states) to record the states that program runs go through. The relational Semantics relate statement-state pairs to traces, whereas the functional Semantics return traces for statement-state pairs. All four Semantics are equivalent. We formalize the Semantics and their equivalence proofs in the constructive setting of Coq.
-
trace based coinductive Operational Semantics for while big step and small step relational and functional styles
2009Co-Authors: Keiko Nakata, Tarmo UustaluAbstract:We present four coinductive Operational Semantics for the While language accounting for both terminating and non-terminating program runs: big-step and small-step relational Semantics and big-step and small-step functional Semantics. The Semantics employ traces (possi- bly infinite sequences of states) to record the states that program runs go through. The relational Semantics relate statement-state pairs to traces, whereas the functional Semantics return traces for statement-state pairs. All four Semantics are equivalent. We formalize the Semantics and their equivalence proofs in the constructive setting of Coq.
Sam Staton - One of the best experts on this subject based on the ideXlab platform.
-
General Structural Operational Semantics through Categorical Logic
2008 23rd Annual IEEE Symposium on Logic in Computer Science, 2008Co-Authors: Sam StatonAbstract:Certain principles are fundamental to Operational Semantics, regardless of the languages or idioms involved. Such principles include rule-based definitions and proof techniques for congruence results. We formulate these principles in the general context of categorical logic. From this general formulation we recover precise results for particular language idioms by interpreting the logic in particular categories. For instance, results for first-order calculi, such as CCS, arise from considering the general results in the category of sets. Results for languages involving substitution and name generation, such as the pi-calculus, arise from considering the general results in categories of sheaves and group actions. As an extended example, we develop a tyft/tyxt-like rule format for open bisimulation in the pi-calculus.
-
a congruence rule format for name passing process calculi from mathematical structural Operational Semantics
Logic in Computer Science, 2006Co-Authors: Marcelo Fiore, Sam StatonAbstract:We introduce a mathematical structural Operational Semantics that yields a congruence result for bisimilarity and is suitable for investigating rule formats for name-passing systems. Indeed, we instantiate this general abstract model theory in a framework of nominal sets and extract from it a GSOS-like rule format for name-passing process calculi for which the associated notion of behavioural equivalence - given by a form of open bisimilarity - is a congruence.
