Structural operational semantic specifications come in different styles: small-step and big-step. A problem with the big-step style is that specifying divergence and abrupt termination gives rise to annoying duplication. We present a novel approach to representing divergence and abrupt termination in big-step semantics using status flags. This avoids the duplication problem, and uses fewer rules and premises for representing divergence than previous approaches in the literature.
Moggi @cite_31 suggested monads as a means to obtain modularity in denotational semantics @cite_6 . In a similar vein, Modular SOS @cite_23 provides a means to obtain modularity in operational semantics. The flag-based approach to divergence presented here is a variant of the abrupt termination technique used in @cite_23 . That article represents abrupt termination as emitted signals. In a small-step semantics, this enables the encoding of abrupt termination by introducing a top-level handler that matches on emitted signals: if the handler observes an emitted signal, the program abruptly terminates. Exceptions as emitted signals could also be used for expressing abrupt termination in big-step semantics. However, this would entail wrapping each premise in a handler, thereby cluttering rules. Subsequent work @cite_27 observed that encoding abrupt termination as a stateful flag instead scales better to big-step rules by avoiding such explicit handlers. Flag-based divergence was used in @cite_42 for giving a semantics for the untyped @math -calculus. The first author's thesis [Cpt. 4 and 5] BachPoulsen2016xtss describes a rule format for which small-step and pretty-big-step rules are provably equivalent using flag-based abrupt termination and divergence.
@cite_42 @cite_6 @cite_27 @cite_23 @cite_31
2169488840 2884913901 1990062016 2228116382
Big-step semantics for languages with abrupt termination and or divergence suffer from a serious duplication problem, addressed by the novel 'pretty-big-step' style presented by Chargueraud at ESOP'13. Such rules are less concise than corresponding small-step rules, but they have the same advantages as big-step rules for program correctness proofs. Here, we show how to automatically derive pretty-big-step rules directly from small-step rules by 'refocusing'. This gives the best of both worlds: we only need to write the relatively concise small-step specifications, but our reasoning can be big-step as well as small-step. The use of strictness annotations to derive small-step congruence rules gives further conciseness. This paper addresses the semantics of weighted argumentation graphs that are bipolar, i.e. contain both attacks and supports for arguments. It builds on previous work by Amgoud, Ben-Naim et. al. We study the various characteristics of acceptability semantics that have been introduced in these works, and introduce the notion of a modular acceptability semantics. A semantics is modular if it cleanly separates aggregation of attacking and supporting arguments (for a given argument @math ) from the computation of their influence on @math 's initial weight. We show that the various semantics for bipolar argumentation graphs from the literature may be analysed as a composition of an aggregation function with an influence function. Based on this modular framework, we prove general convergence and divergence theorems. We demonstrate that all well-behaved modular acceptability semantics converge for all acyclic graphs and that no sum-based semantics can converge for all graphs. In particular, we show divergence of Euler-based semantics () for certain cyclic graphs. Further, we provide the first semantics for bipolar weighted graphs that converges for all graphs. We look at the operational semantics of languages with interactive I O through the glasses of constructive type theory. Following on from our earlier work on coinductive trace-based semantics for While [17], we define several big-step semantics for Whil e with interactive I O, based on resumptions and termination-sensitive weak bisimilarity. These require nesting inductive definitions in coinductive definitions, which is interesting both mathe matically and from the point-of-view of implementation in a proof assistant. After first defining a basic semantics of statements in terms o f resumptions with explicit internal actions (delays), we introduce a semantics in terms of delay-free resumptions that essentially removes finite sequences of delays on the fly from those resumptions th at are responsive. Finally, we also look at a semantics in terms of delay-free resumptions supplemented with a silent divergence option. This semantics hinges on decisions between convergence and divergence and is only equivalent to the basic one classically. We have fully formalized our development in Coq. This paper focuses on low complexity successive cancellation list (SCL) decoding of polar codes. In particular, using the fact that splitting may be unnecessary when the reliability of decoding the unfrozen bit is sufficiently high, a novel splitting rule is proposed. Based on this rule, it is conjectured that, if the correct path survives at some stage, it tends to survive till termination without splitting with high probability. On the other hand, the incorrect paths are more likely to split at the following stages. Motivated by these observations, a simple counter that counts the successive number of stages without splitting is introduced for each decoding path to facilitate the identification of correct and incorrect paths. Specifically, any path with counter value larger than a predefined threshold @math is deemed to be the correct path, which will survive at the decoding stage, while other paths with counter value smaller than the threshold will be pruned, thereby reducing the decoding complexity. Furthermore, it is proved that there exists a unique unfrozen bit @math , after which the successive cancellation decoder achieves the same error performance as the maximum likelihood decoder if all the prior unfrozen bits are correctly decoded, which enables further complexity reduction. Simulation results demonstrate that the proposed low complexity SCL decoder attains performance similar to that of the conventional SCL decoder, while achieving substantial complexity reduction.