2053241
Relating strands and multiset rewriting for security protocol analysis
Formal analysis of security protocols is largely based on an set of assumptions commonly referred to as the Dolev-Yao model. Two formalisms that state the basic assumptions of this model are related here: strand spaces and multiuser rewriting with existential quantification. Although it is fairly intuitive that these two languages should be equivalent in some way, a number of modifications to each system are required to obtain a meaningful equivalence. We extend the strand formalism with a way of incrementally growing bundles in order to emulate an execution of a protocol with parametric strands. We omit the initialization part of the multiset rewriting setting, which formalizes the choice of initial data, such as shared public or private keys, and which has no counterpart in the stand space setting. The correspondence between the modified formalisms directly relates the intruder theory from the multiset rewriting formalism to the penetrator strands.
3062362
Managing Digital Rights using Linear Logic
Digital music players protect songs by enforcing licenses that convey specific rights for individual songs or groups of songs. For licenses specified in industry, we show that deciding whether a license authorizes a sequence of actions is NP-complete, with a restricted version of the problem solvable efficiently using a reduction to maximum network flow. The authorization algorithm used in industry is online, deciding which rights to exercise as actions occur, but we show that all online algorithms are necessarily non-monotonic: each allows actions under one license that it does not allow under a more flexible license. In one approach to achieving monotonicity, we exhibit the unique maximal set of licenses on which there exists a monotonic online algorithm. This set of well-behaved licenses induces an approximation algorithm by replacing each license with a well-behaved license. In a second approach, we consider allowing the player to revise its past decisions about which rights to exercise while still ensuring compliance with the license. We propose an efficient algorithm based on linear logic, with linear negation used to revise past decisions. We prove our algorithm monotonic, live, and sound with respect to the semantics of licenses
16397953
Parametricity and Variants of Girard's J Operator
Abstract The Girard–Reynolds polymorphic λ -calculus is generally regarded as a calculus of parametric polymorphism in which all well-formed terms are strongly normalizing with respect to β -reductions. Girard demonstrated that the addition of a simple “non-parametric” operation, J , to the calculus allows the definition of a non-normalizing term. Since the type of J is not inhabited by any closed term, one might suspect that this may play a role in defining a non-normalizing term using it. We demonstrate that this is not the case by giving a simple variant, J′ , of J whose type is otherwise inhabited and which causes normalization to fail. It appears that impredictivity is essential to the argument; predictive variants of the polymorphic λ -calculus admit non-parametric operations without sacrificing normalization.
18708753
Unification and ML-Type Reconstruction
We study the complexity of type reconstruction for a core fragment of ML with lambda abstraction, function application, and the polymorphic let declaration. We derive exponential upper and lower bounds on recognizing the typable core ML expressions. Our primary technical tool is uniication of succinctly represented type expressions. After observing that core ML expressions, of size n, can be typed in DTIME(2 n), we exhibit two diierent families of programs whose principal types grow exponentially. We show how to exploit the expressiveness of the let-polymorphism in these constructions to derive lower bounds on deciding typability: one leads naturally to NP-hardness and the other to DTIME(2 n k)-hardness for each integer k 1. Our generic simulation of any exponential time Turing Machine by ML type reconstruction may be viewed as a nonstandard way of computing with types. Our worst-case lower bounds stand in contrast to practical experience, which suggests that commonly used algorithms for type reconstruction do not slow compilation substantially.
9031501
Design of a role-based trust-management framework
We introduce the RT framework, a family of role-based trust management languages for representing policies and credentials in distributed authorization. RT combines the strengths of role-based access control and trust-management systems and is especially suitable for attribute-based access control. Using a few simple credential forms, RT provides localized authority over roles, delegation in role definition, linked roles, and parameterized roles. RT also introduces manifold roles, which can be used to express threshold and separation-of-duty policies, and delegation of role activations. We formally define the semantics of credentials in the RT framework by presenting a translation from credentials to Datalog rules. This translation also shows that this semantics is algorithmically tractable.
215952437
Beyond proof-of-compliance: security analysis in trust management
Trust management is a form of distributed access control that allows one principal to delegate some access decisions to other principals. While the use of delegation greatly enhances flexibility an...
2490428
A maximumb-matching problem arising from median location models with applications to the roommates problem
We consider maximumb-matching problems where the nodes of the graph represent points in a metric space, and the weight of an edge is the distance between the respective pair of points. We show that if the space is either the rectilinear plane, or the metric space induced by a tree network, then theb-matching problem is the dual of the (single) median location problem with respect to the given set of points. This result does not hold for the Euclidean plane. However, we show that in this case theb-matching problem is the dual of a median location problem with respect to the given set of points, in some extended metric space. We then extend this latter result to any geodesic metric in the plane. The above results imply that the respective fractionalb-matching problems have integer optimal solutions. We use these duality results to prove the nonemptiness of the core of a cooperative game defined on the roommate problem corresponding to the above matching model. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
14267496
Recognizing polygonal parts from width measurements
Abstract Automatic recognition of parts is an important problem in many industrial applications. One model of the problem is: given a finite set of polygonal parts, use a set of “width” measurements taken by a parallel-jaw gripper to determine which part is present. We study the problem of computing efficient strategies (“grasp plans”), with the goal to minimize the number of measurements necessary in the worst case. We show that finding a minimum length grasp plan is NP -hard, and give a polynomial time approximation algorithm that is simple and produces a solution that is within a log factor from optimal.
11907078
Optimal decomposition of polygonal models into triangle strips
Motivated by applications in computer graphics, we study the problem of computing an optimal encoding in "triangle strips" of a triangulation of a polygonal surface model. The goal is to facilitate the transmission and rendering of a polygonal model by decomposing its triangulation into a minimum number of "tristrips," each of which has its connectivity stored implicitly in the ordering of the data points. While this optimization problem has been conjectured to be hard, its complexity status has been open. We prove that the tristrip decomposition problem is, in fact, NP-complete. We also propose two methods for solving the problem to optimality, one based on an integer programming formulation, one based on a branch-and-bound scheme that relies on lower bounding techniques for its efficiency. We perform an extensive set of experiments to test the efficiencies of these methods and some of their variants. These methods have been integrated also with the practical system FTSG (Fast Triangle Strip Generator), in order to utilize optimization methods on small subproblems to improve the quality of the heuristic solutions obtained by FTSG. We use experimentation to judge the quality of the improvements.
14458363
Guillotine subdivisions approximate polygonal subdivisions: a simple new method for the geometric k-MST problem
A method of mixing poly(neopentylglycol)azelate (NPGA) is disclosed which enhances its solubility in polyurethane binders for composite solid propellants. The method comprises withholding the addition of NPGA from the propellant submix and from the total propellant formulation mixing procedure until after the addition of the curing agent has taken place and reaction has taken place for a predetermined period of time with the bonding agent until a "break" in viscosity occurs. The "break" in viscosity has taken place when the other binder ingredients have reacted with the curing agent HDI (hexamethylenediisocyanate) so that immiscibility between the binder ingredients is reduced. The late NPGA addition method resulted not only in apparently complete solubilization of the NPGA but also yielded a propellant with dramatically lower end of mix viscosity (reduced by a factor of 10), superior flow characteristics, and better physical properties. Propellants made by the disclosed method of mixing have desirable lower modulus and higher tensile strength. Thus, the propellant mixed in accordance with the late NPGA addition method yields a propellant with a high tensile strength to modulus ratio. The high tensile strength to modulus ratio at low temperature is an indicator of a good propellant.
5227025
Curved PN triangles
To improve the visual quality of existing triangle-based art in realtime entertainment, such as computer games, we propose replacing flat triangles with curved patches and higher-order normal variation. At the hardware level, based only on the three vertices and three vertex normals of a given flat triangle, we substitute the geometry of a three-sided cubic Bezier patch for the triangle’s flat geometry, and a quadratically varying normal for Gouraud shading. These curved point-normal triangles, or PN triangles, require minimal or no change to existing authoring tools and hardware designs while providing a smoother, though not necessarily everywhere tangent continuous, silhouette and more organic shapes. CR Categories: I.3.5 [surface representation, splines]: I.3.6— graphics data structures