Krishnaswami N.R.,University of Birmingham |
Pradic P.,ENS Lyon |
Conference Record of the Annual ACM Symposium on Principles of Programming Languages | Year: 2015
In this paper, we show how to integrate linear types with type dependency, by extending the linear/non-linear calculus of Benton to support type dependency. Next, we give an application of this calculus by giving a proof-theoretic account of imperative programming, which requires extending the calculus with computationally irrelevant quantification, proof irrelevance, and a monad of computations. We show the soundness of our theory by giving a realizability model in the style of Nuprl, which permits us to validate not only the β-laws for each type, but also the η-laws. These extensions permit us to decompose Hoare triples into a collection of simpler type-theoretic connectives, yielding a rich equational theory for dependently-typed higherorder imperative programs. Furthermore, both the type theory and its model are relatively simple, even when all of the extensions are considered. Copyright © 2015 by the Association for Computing Machinery, Inc. (ACM).
Crubille R.,ENS Lyon |
Dal Lago U.,University of Bologna
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2014
Probabilistic applicative bisimulation is a recently introduced coinductive methodology for program equivalence in a probabilistic, higher-order, setting. In this paper, the technique is applied to a typed, call-by-value, lambda-calculus. Surprisingly, the obtained relation coincides with context equivalence, contrary to what happens when call-by-name evaluation is considered. Even more surprisingly, full-abstraction only holds in a symmetric setting. © 2014 Springer-Verlag.
Zanasi F.,ENS Lyon
Proceedings - Symposium on Logic in Computer Science | Year: 2013
We provide a characterization theorem, in the style of van Ben them and Janin-Walukiewicz, for the alternation-free fragment of the modal mu-calculus. For this purpose we introduce a variant of standard monadic second-order logic (MSO), which we call well-founded monadic second-order logic (WFMSO). When interpreted in a tree model, the second-order quantifiers of WFMSO range over subsets of conversely well-founded sub trees. The first main result of the paper states that the expressive power of WFMSO over trees exactly corresponds to that of weak MSO-Automata. Using this automata-theoretic characterization, we then show that, over the class of all transition structures, the bisimulation-invariant fragment of WFMSO is the alternation-free fragment of the modal mu-calculus. As a corollary, we find that the logics WFMSO and WMSO (weak monadic second-order logic, where second-order quantification concerns finite subsets), are incomparable in expressive power. © 2013 IEEE.
Thierry E.,ENS Lyon
Discrete Event Dynamic Systems: Theory and Applications | Year: 2015
Network Calculus theory aims at evaluating worst-case performances in communication networks. It provides methods to analyze models where the traffic and the services are constrained by some minimum and/or maximum envelopes (arrival/service curves). While new applications come forward, a challenging and inescapable issue remains open: achieving tight analyzes of networks with aggregate multiplexing. The theory offers efficient methods to bound maximum end-to-end delays or local backlogs. However as shown in a recent breakthrough paper (Schmitt et al. 2008), those bounds can be arbitrarily far from the exact worst-case values, even in seemingly simple feed-forward networks (two flows and two servers), under blind multiplexing (i.e. no information about the scheduling policies, except FIFO per flow). For now, only a network with three flows and three servers, as well as a tandem network called sink tree, have been analyzed tightly.We describe the first algorithm which computes the maximum end-to-end delay for a given flow, as well as the maximum backlog at a server, for any feed-forward network under blind multiplexing, with piecewise affine concave arrival curves and piecewise affine convex service curves. Its computational complexity may look expensive (possibly super-exponential), but we show that the problem is intrinsically difficult (NP-hard). Fortunately we show that in some cases, like tandem networks with cross-traffic interfering along intervals of servers, the complexity becomes polynomial. We also compare ourselves to the previous approaches and discuss the problems left open. © 2015 Springer Science+Business Media New York
Talon A.,ENS Lyon |
Kratochvil J.,Charles University
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2015
We describe the missing class of the hierarchy of mixed unit interval graphs, generated by the intersection graphs of closed, open and one type of half-open intervals of the real line. This class lies strictly between unit interval graphs and mixed unit interval graphs. We give a complete characterization of this new class, as well as a polynomial time algorithm to recognize graphs from this class and to produce a corresponding interval representation if one exists. © IFIP International Federation for Information Processing 2015.