Cut Elimination in Multifocused Linear Logic

We study cut elimination for a multifocused variant of full linear logic in the sequent calculus. The multifocused normal form of proofs yields problems that do not appear in a standard focused system, related to the constraints in grouping rule instances in focusing phases. We show that cut elimination can be performed in a sensible way even though the proof requires some specific lemmas to deal with multifocusing phases, and discuss the difficulties arising with cut elimination when considering normal forms of proofs in linear logic.

Quantile and Probability Curves Without Crossing

This paper proposes a method to address the longstanding problem of lack of monotonicity in estimation of conditional and structural quantile functions, also known as the quantile crossing problem. The method consists in sorting or monotone rearranging the original estimated non-monotone curve into a monotone rearranged curve. We show that the rearranged curve is closer to the true quantile curve in finite samples than the original curve, establish a functional delta method for rearrangement-related operators, and derive functional limit theory for the entire rearranged curve and its functionals. We also establish validity of the bootstrap for estimating the limit law of the the entire rearranged curve and its functionals. Our limit results are generic in that they apply to every estimator of a monotone econometric function, provided that the estimator satisfies a functional central limit theorem and the function satisfies some smoothness conditions. Consequently, our results apply to estimation of other econometric functions with monotonicity restrictions, such as demand, production, distribution, and structural distribution functions. We illustrate the results with an application to estimation of structural quantile functions using data on Vietnam veteran status and earnings.

The Minimal Volkov - Akulov - Starobinsky Supergravity

We construct a supergravity model whose scalar degrees of freedom arise from a chiral superfield and are solely a scalaron and an axion that is very heavy during the inflationary phase. The model includes a second chiral superfield $X$, which is subject however to the constraint $X^2=0$ so that it describes only a Volkov - Akulov goldstino and an auxiliary field. We also construct the dual higher - derivative model, which rests on a chiral scalar curvature superfield ${cal R}$ subject to the constraint ${cal R}^2=0$, where the goldstino dual arises from the gauge - invariant gravitino field strength as $gamma^{mn} {cal D}_m psi_n$. The final bosonic action is an $R+R^2$ theory involving an axial vector $A_m$ that only propagates a physical pseudoscalar mode.

On the Verification of a WiMax Design Using Symbolic Simulation

In top-down multi-level design methodologies, design descriptions at higher levels of abstraction are incrementally refined to the final realizations. Simulation based techniques have traditionally been used to verify that such model refinements do not change the design functionality. Unfortunately, with computer simulations it is not possible to completely check that a design transformation is correct in a reasonable amount of time, as the number of test patterns required to do so increase exponentially with the number of system state variables. In this paper, we propose a methodology for the verification of conformance of models generated at higher levels of abstraction in the design process to the design specifications. We model the system behavior using sequence of recurrence equations. We then use symbolic simulation together with equivalence checking and property checking techniques for design verification. Using our proposed method, we have verified the equivalence of three WiMax system models at different levels of design abstraction, and the correctness of various system properties on those models. Our symbolic modeling and verification experiments show that the proposed verification methodology provides performance advantage over its numerical counterpart.

On Consistency of Operational Transformation Approach

The Operational Transformation (OT) approach, used in many collaborative editors, allows a group of users to concurrently update replicas of a shared object and exchange their updates in any order. The basic idea of this approach is to transform any received update operation before its execution on a replica of the object. This transformation aims to ensure the convergence of the different replicas of the object, even though the operations are executed in different orders. However, designing transformation functions for achieving convergence is a critical and challenging issue. Indeed, the transformation functions proposed in the literature are all revealed incorrect. In this paper, we investigate the existence of transformation functions for a shared string altered by insert and delete operations. From the theoretical point of view, two properties - named TP1 and TP2 - are necessary and sufficient to ensure convergence. Using controller synthesis technique, we show that there are some transformation functions which satisfy only TP1 for the basic signatures of insert and delete operations. As a matter of fact, it is impossible to meet both properties TP1 and TP2 with these simple signatures.

Reducing Weak to Strong Bisimilarity in CCP

Concurrent constraint programming (ccp) is a well-established model for concurrency that singles out the fundamental aspects of asynchronous systems whose agents (or processes) evolve by posting and querying (partial) information in a global medium. Bisimilarity is a standard behavioural equivalence in concurrency theory. However, only recently a well-behaved notion of bisimilarity for ccp, and a ccp partition refinement algorithm for deciding the strong version of this equivalence have been proposed. Weak bisimiliarity is a central behavioural equivalence in process calculi and it is obtained from the strong case by taking into account only the actions that are observable in the system. Typically, the standard partition refinement can also be used for deciding weak bisimilarity simply by using Milners reduction from weak to strong bisimilarity; a technique referred to as saturation. In this paper we demonstrate that, because of its involved labeled transitions, the above-mentioned saturation technique does not work for ccp. We give an alternative reduction from weak ccp bisimilarity to the strong one that allows us to use the ccp partition refinement algorithm for deciding this equivalence.

CMB Imprints of a Pre-Inflationary Climbing Phase

We discuss the implications for cosmic microwave background (CMB) observables, of a class of pre-inflationary dynamics suggested by string models where SUSY is broken due to the presence of D-branes and orientifolds preserving incompatible portions of it. In these models the would-be inflaton is forced to emerge from the initial singularity climbing up a mild exponential potential, until it bounces against a steep exponential potential of brane SUSY breaking scenarios, and as a result the ensuing descent gives rise to an inflationary epoch that begins when the system is still well off its eventual attractor. If a pre-inflationary climbing phase of this type had occurred within 6-7 e-folds of the horizon exit for the largest observable wavelengths, displacement off the attractor and initial-state effects would conspire to suppress power in the primordial scalar spectrum, enhancing it in the tensor spectrum and typically superposing oscillations on both. We investigate these imprints on CMB observables over a range of parameters, examine their statistical significance, and provide a semi-analytic rationale for our results. It is tempting to ascribe at least part of the large-angle anomalies in the CMB to pre-inflationary dynamics of this type.

Coupling policy iteration with semi-definite relaxation to compute accurate numerical invariants in static analysis

We introduce a new domain for finding precise numerical invariants of programs by abstract interpretation. This domain, which consists of level sets of non-linear functions, generalizes the domain of linear templates introduced by Manna, Sankaranarayanan, and Sipma. In the case of quadratic templates, we use Shors semi-definite relaxation to derive computable yet precise abstractions of semantic functionals, and we show that the abstract fixpoint equation can be solved accurately by coupling policy iteration and semi-definite programming. We demonstrate the interest of our approach on a series of examples (filters, integration schemes) including a degenerate one (symplectic scheme).

A Focused Sequent Calculus Framework for Proof Search in Pure Type Systems

Basic proof-search tactics in logic and type theory can be seen as the root-first applications of rules in an appropriate sequent calculus, preferably without the redundancies generated by permutation of rules. This paper addresses the issues of defining such sequent calculi for Pure Type Systems (PTS, which were originally presented in natural deduction style) and then organizing their rules for effective proof-search. We introduce the idea of Pure Type Sequent Calculus with meta-variables (PTSCalpha), by enriching the syntax of a permutation-free sequent calculus for propositional logic due to Herbelin, which is strongly related to natural deduction and already well adapted to proof-search. The operational semantics is adapted from Herbelins and is defined by a system of local rewrite rules as in cut-elimination, using explicit substitutions. We prove confluence for this system. Restricting our attention to PTSC, a type system for the ground terms of this system, we obtain the Subject Reduction property and show that each PTSC is logically equivalent to its corresponding PTS, and the former is strongly normalising iff the latter is. We show how to make the logical rules of PTSC into a syntax-directed system PS for proof-search, by incorporating the conversion rules as in syntax-directed presentations of the PTS rules for type-checking. Finally, we consider how to use the explicitly scoped meta-variables of PTSCalpha to represent partial proof-terms, and use them to analyse interactive proof construction. This sets up a framework PE in which we are able to study proof-search strategies, type inhabitant enumeration and (higher-order) unification.

On Climbing Scalars in String Theory

In string models with brane supersymmetry breaking exponential potentials emerge at (closed-string) tree level but are not accompanied by tachyons. Potentials of this type have long been a source of embarrassment in flat space, but can have interesting implications for Cosmology. For instance, in ten dimensions the logarithmic slope |V/V| lies precisely at a critical value where the Lucchin--Matarrese attractor disappears while the scalar field is emph{forced} to climb up the potential when it emerges from the Big Bang. This type of behavior is in principle perturbative in the string coupling, persists after compactification, could have trapped scalar fields inside potential wells as a result of the cosmological evolution and could have also injected the inflationary phase of our Universe.