The Experts below are selected from a list of 25755 Experts worldwide ranked by ideXlab platform

Michele Pagani - One of the best experts on this subject based on the ideXlab platform.

  • Revisiting Call-by-value B\"ohm trees in light of their Taylor Expansion.
    arXiv: Logic in Computer Science, 2018
    Co-Authors: Emma Kerinec, Giulio Manzonetto, Michele Pagani
    Abstract:

    The call-by-value lambda calculus can be endowed with permutation rules, arising from linear logic proof-nets, having the advantage of unblocking some redexes that otherwise get stuck during the reduction. We show that such an extension allows to define a satisfying notion of Bohm(-like) tree and a theory of program approximation in the call-by-value setting. We prove that all lambda terms having the same Bohm tree are observationally equivalent, and characterize those Bohm-like trees arising as actual Bohm trees of lambda terms. We also compare this approach with Ehrhard's theory of program approximation based on the Taylor Expansion of lambda terms, translating each lambda term into a possibly infinite set of so-called resource terms. We provide sufficient and necessary conditions for a set of resource terms in order to be the Taylor Expansion of a lambda term. Finally, we show that the normal form of the Taylor Expansion of a lambda term can be computed by performing a normalized Taylor Expansion of its Bohm tree. From this it follows that two lambda terms have the same Bohm tree if and only if the normal forms of their Taylor Expansions coincide.

  • Strong Normalizability as a Finiteness Structure via the Taylor Expansion of λ -terms
    2016
    Co-Authors: Michele Pagani, Christine Tasson, Lionel Vaux
    Abstract:

    In the folklore of linear logic, a common intuition is that the structure of finiteness spaces, introduced by Ehrhard, semantically reflects the strong normalization property of cut-elimination. We make this intuition formal in the context of the non-deterministic λ-calculus by introducing a finiteness structure on resource terms, which is such that a λ-term is strongly normalizing iff the support of its Taylor Expansion is finitary. An application of our result is the existence of a normal form for the Taylor Expansion of any strongly normalizable non-deterministic λ-term.

  • Strong Normalizability as a Finiteness Structure via the Taylor Expansion of {\lambda}-terms
    arXiv: Logic in Computer Science, 2016
    Co-Authors: Michele Pagani, Christine Tasson, Lionel Vaux
    Abstract:

    In the folklore of linear logic, a common intuition is that the structure of finiteness spaces, introduced by Ehrhard, semantically reflects the strong normalization property of cut-elimination. We make this intuition formal in the context of the non-deterministic {\lambda}-calculus by introducing a finiteness structure on resource terms, which is such that a {\lambda}-term is strongly normalizing iff the support of its Taylor Expansion is finitary. An application of our result is the existence of a normal form for the Taylor Expansion of any strongly normalizable non-deterministic {\lambda}-term.

  • a characterization of the Taylor Expansion of lambda terms
    Computer Science Logic, 2013
    Co-Authors: Pierre Boudes, Michele Pagani
    Abstract:

    The Taylor Expansion of lambda-terms, as introduced by Ehrhard and Regnier, expresses a lambda-term as a series of multi-linear terms, called simple terms, which capture bounded computations. Normal forms of Taylor Expansions give a notion of infinitary normal forms, refining the notion of Bohm trees in a quantitative setting. We give the algebraic conditions over a set of normal simple terms which characterize the property of being the normal form of the Taylor Expansion of a lambda-term. From this full completeness result, we give further conditions which semantically describe normalizable and total lambda-terms.

  • CSL - A characterization of the Taylor Expansion of lambda-terms
    2013
    Co-Authors: Pierre Boudes, Michele Pagani
    Abstract:

    The Taylor Expansion of lambda-terms, as introduced by Ehrhard and Regnier, expresses a lambda-term as a series of multi-linear terms, called simple terms, which capture bounded computations. Normal forms of Taylor Expansions give a notion of infinitary normal forms, refining the notion of Bohm trees in a quantitative setting. We give the algebraic conditions over a set of normal simple terms which characterize the property of being the normal form of the Taylor Expansion of a lambda-term. From this full completeness result, we give further conditions which semantically describe normalizable and total lambda-terms.

Emmanuel Boutillon - One of the best experts on this subject based on the ideXlab platform.

  • HLDVT - Retiming arithmetic datapaths using Timed Taylor Expansion Diagrams
    2010 IEEE International High Level Design Validation and Test Workshop (HLDVT), 2010
    Co-Authors: D. Gomez-prado, Dusung Kim, Maciej Ciesielski, Emmanuel Boutillon
    Abstract:

    This paper describes an extension to the Taylor Expansion Diagrams (TED), called Timed TEDs, which makes it possible to represent sequential arithmetic datapaths. Timed TEDs enable register and clock period minimization while performing factorizations and common sub expression eliminations in the data flow graph (DFG). Specifically, timed TEDs allow a wider range of retiming options as the computations in the DFG can be modified while performing retiming. In this paper we discuss the formalism of timed TEDs and the restrictions it imposes on the TED variable ordering.

  • Data-Flow Transformations using Taylor Expansion Diagrams
    2007 Design Automation & Test in Europe Conference & Exhibition, 2007
    Co-Authors: M. Ciesielski, D. Gomez-prado, S. Askar, J. Guillot, Emmanuel Boutillon
    Abstract:

    An original technique to transform functional representation of the design into a structural representation in form of a data flow graph (DFG) is described. A canonical, word-level data structure, Taylor Expansion diagram (TED), is used as a vehicle to effect this transformation. The problem is formulated as that of applying a sequence of decomposition cuts to a TED that transforms it into a DFG optimized for a particular objective. A systematic approach to arrive at such a decomposition is described. Experimental results show that such constructed DFG provides a better starting point for architectural synthesis than those extracted directly from HDL specifications

  • Efficient factorization of DSP transforms using Taylor Expansion diagrams
    2006
    Co-Authors: Jérémie Guillot, D. Gomez-prado, Maciej Ciesielski, Emmanuel Boutillon, Qian Ren, Serkan Askar
    Abstract:

    This paper describes an efficient method to perform factorization of DSP transforms based on Taylor Expansion Diagram (TED). It is shown that TED can efficiently represent and manipulate mathematical expressions. We demonstrate that it enables efficient factorization of arithmetic expressions of DSP transforms, resulting in a simplification of the computation.

  • Variable ordering for Taylor Expansion diagrams
    2005
    Co-Authors: D. Gomez-prado, Maciej Ciesielski, Serkan Askar, Quian Ren, Emmanuel Boutillon
    Abstract:

    This paper presents an algorithm for variable ordering for Taylor Expansion Diagrams (TEDs). First we prove that the function implemented by the TED is independent of the order of its variables, and then that swapping of two adjacent variables in a TED is a local permutation similar to that in BDD. These two properties allow us to construct an algorithm to swap variables locally without affecting the entire TED. The proposed algorithm can be used to perform dynamic reordering, such as sifting or window permutation. We also propose a static ordering that can help reduce the permutation space and speed up the search of an optimal variable order for TEDs.

Lionel Vaux - One of the best experts on this subject based on the ideXlab platform.

  • Normalizing the Taylor Expansion of non-deterministic λ-terms, via parallel reduction of resource vectors
    Logical Methods in Computer Science, 2019
    Co-Authors: Lionel Vaux
    Abstract:

    It has been known since Ehrhard and Regnier's seminal work on the Taylor Expansion of $\lambda$-terms that this operation commutes with normalization: the Expansion of a $\lambda$-term is always normalizable and its normal form is the Expansion of the B\"ohm tree of the term. We generalize this result to the non-uniform setting of the algebraic $\lambda$-calculus, i.e. $\lambda$-calculus extended with linear combinations of terms. This requires us to tackle two difficulties: foremost is the fact that Ehrhard and Regnier's techniques rely heavily on the uniform, deterministic nature of the ordinary $\lambda$-calculus, and thus cannot be adapted; second is the absence of any satisfactory generic extension of the notion of B\"ohm tree in presence of quantitative non-determinism, which is reflected by the fact that the Taylor Expansion of an algebraic $\lambda$-term is not always normalizable. Our solution is to provide a fine grained study of the dynamics of $\beta$-reduction under Taylor Expansion, by introducing a notion of reduction on resource vectors, i.e. infinite linear combinations of resource $\lambda$-terms. The latter form the multilinear fragment of the differential $\lambda$-calculus, and resource vectors are the target of the Taylor Expansion of $\lambda$-terms. We show the reduction of resource vectors contains the image of any $\beta$-reduction step, from which we deduce that Taylor Expansion and normalization commute on the nose. We moreover identify a class of algebraic $\lambda$-terms, encompassing both normalizable algebraic $\lambda$-terms and arbitrary ordinary $\lambda$-terms: the Expansion of these is always normalizable, which guides the definition of a generalization of B\"ohm trees to this setting.

  • Taylor Expansion, β-reduction and normalization
    2017
    Co-Authors: Lionel Vaux
    Abstract:

    We introduce a notion of reduction on resource vectors, i.e. infinite linear combinations of resource λ-terms. The latter form the multilinear fragment of the differential λ-calculus introduced by Ehrhard and Regnier, and resource vectors are the target of the Taylor Expansion of λ-terms. We show that the reduction of resource vectors contains the image, through Taylor Expansion, of β-reduction in the algebraic λ-calculus, i.e. λ-calculus extended with weighted sums: in particular , Taylor Expansion and normalization commute. We moreover exhibit a class of algebraic λ-terms, having a normalizable Taylor Expansion, subsuming both arbitrary pure λ-terms, and normalizable algebraic λ-terms. For these, we prove the commutation of Taylor Expansion and normalization in a more denotational sense, mimicking the Böhm tree construction.

  • CSL - Taylor Expansion, lambda-Reduction and Normalization
    2017
    Co-Authors: Lionel Vaux
    Abstract:

    We introduce a notion of reduction on resource vectors, i.e. infinite linear combinations of resource lambda-terms. The latter form the multilinear fragment of the differential lambda-calculus introduced by Ehrhard and Regnier, and resource vectors are the target of the Taylor Expansion of lambda-terms. We show that the reduction of resource vectors contains the image, through Taylor Expansion, of beta-reduction in the algebraic lambda-calculus, i.e. lambda-calculus extended with weighted sums: in particular, Taylor Expansion and normalization commute. We moreover exhibit a class of algebraic lambda-terms, having a normalizable Taylor Expansion, subsuming both arbitrary pure lambda-terms, and normalizable algebraic lambda-terms. For these, we prove the commutation of Taylor Expansion and normalization in a more denotational sense, mimicking the Bohm tree construction.

  • Strong Normalizability as a Finiteness Structure via the Taylor Expansion of λ -terms
    2016
    Co-Authors: Michele Pagani, Christine Tasson, Lionel Vaux
    Abstract:

    In the folklore of linear logic, a common intuition is that the structure of finiteness spaces, introduced by Ehrhard, semantically reflects the strong normalization property of cut-elimination. We make this intuition formal in the context of the non-deterministic λ-calculus by introducing a finiteness structure on resource terms, which is such that a λ-term is strongly normalizing iff the support of its Taylor Expansion is finitary. An application of our result is the existence of a normal form for the Taylor Expansion of any strongly normalizable non-deterministic λ-term.

  • Strong Normalizability as a Finiteness Structure via the Taylor Expansion of {\lambda}-terms
    arXiv: Logic in Computer Science, 2016
    Co-Authors: Michele Pagani, Christine Tasson, Lionel Vaux
    Abstract:

    In the folklore of linear logic, a common intuition is that the structure of finiteness spaces, introduced by Ehrhard, semantically reflects the strong normalization property of cut-elimination. We make this intuition formal in the context of the non-deterministic {\lambda}-calculus by introducing a finiteness structure on resource terms, which is such that a {\lambda}-term is strongly normalizing iff the support of its Taylor Expansion is finitary. An application of our result is the existence of a normal form for the Taylor Expansion of any strongly normalizable non-deterministic {\lambda}-term.

Yan Shi - One of the best experts on this subject based on the ideXlab platform.

Laurent Regnier - One of the best experts on this subject based on the ideXlab platform.

  • Uniformity and the Taylor Expansion of ordinary lambda-terms
    Theoretical Computer Science, 2008
    Co-Authors: Thomas Ehrhard, Laurent Regnier
    Abstract:

    We define the complete Taylor Expansion of an ordinary lambda-term as an infinite linear combination --- with rational coefficients --- of terms of a resource calculus similar to Boudol's resource lambda-calculus. In this calculus, all applications are (multi-)linear in the algebraic sense, i.e. commute with linear combination of the function or the argument. We study the collective behaviour of the beta-reducts of the terms occurring in the Taylor Expansion of any ordinary lambda-term, using a uniformity property that they enjoy.

  • Uniformity and the Taylor Expansion of ordinary lambda-terms
    Theoretical Computer Science, 2007
    Co-Authors: Thomas Ehrhard, Laurent Regnier
    Abstract:

    We define the complete Taylor Expansion of an ordinary lambda-term as an infinite linear combination-with rational coefficients-of terms of a resource calculus similar to Boudol's lambda-calculus with multiplicities (or with resources). In our resource calculus, all applications are (multi)linear in the algebraic sense, i.e. commute with linear combinations of the function or the argument. We study the collective behaviour of the beta-reducts of the terms occurring in the Taylor Expansion of any ordinary lambda-term, using, in a surprisingly crucial way, a uniformity property that they enjoy. As a corollary, we obtain (the main part of) a proof that this Taylor Expansion commutes with Bohm tree computation, syntactically.

  • bohm trees krivine s machine and the Taylor Expansion of lambda terms
    Conference on Computability in Europe, 2006
    Co-Authors: Thomas Ehrhard, Laurent Regnier
    Abstract:

    We introduce and study a version of Krivine's machine which provides a precise information about how much of its argument is needed for performing a computation. This information is expressed as a term of a resource lambda-calculus introduced by the authors in a recent article; this calculus can be seen as a fragment of the differential lambda-calculus. We use this machine to show that Taylor Expansion of lambda-terms (an operation mapping lambda-terms to generally infinite linear combinations of resource lambda-terms) commutes with Bohm tree computation.

  • Böhm trees, Krivine machine and the Taylor Expansion of ordinary lambda-terms
    2006
    Co-Authors: Thomas Ehrhard, Laurent Regnier
    Abstract:

    We introduce and study a version of Krivine's machine which provides a precise information about how much of its argument is needed for performing a computation. This information is expressed as a term of a resource lambda-calculus introduced by the authors in a recent article; this calculus can be seen as a fragment of the differential lambda-calculus. We use this machine to show that Taylor Expansion of lambda-terms (an operation mapping lambda-terms to generally infinite linear combinations of resource lambda-terms) commutes with Boehm tree computation.