12997315
PER models of subtyping, recursive types and higher-order polymorphism
We relate standard techniques for solving recursive domain equations to previous models with types interpreted as partial equivalence relations (per's) over a Dm lambda model. This motivates a particular choice of type functions, which leads to an extension of, such models to higher-order polymorphism. The resulting models provide natural interpretations for function spaces, records, recursively defined types, higher-order type functions, and bounded polymor-phic types Y-X <: Y. A where the bound may be of a higher kind. In particular, we may combine recursion and polymorphism in a way that allows the bound Y in VX <: Y. A to be recursive y defined. The model may also be used to interpret so-called " F-bounded polymorphism. " Together, these features allolv us to represent several forms of type and type functions that seem to arise naturally in typed object-oriented programming. 1 Introduction In type systems aimed towards object-oriented programming , several typing ideas naturally arise. The most basic are subtyping, the fact that values of one type may be treated as values of another, polymor-phism, and recursively defined types. the Powell Foundation. t s~lpported in part by an NSF PYI Award, matching funds from Digital Equipment Corporation, the Powell Foundation, and Xerox Corporation NSF grant CCR-881 4921 and the Wal-lace F. and Lucille M. Davis Faculty Scholarship. Pennksion to copy without fee all or part of this material is granted provided that tie copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of tbe publication and its date appear, and notice is given that copying is by permission of tbe Association for Computing Machinery. To copy otherwise , or to republish, requires a fee sad/or specific permission. the existing, implemented type systems for object-oriented languages have notable errors (see, [CO089]), it is important to prove the soundness of these type systems. The primary technique for doing so is by constructing a selmantic model. A class of semantic models for languages with subtyp-ing, polymorphism and recursion are developed in [Cop85, Ama91, Car89, AP90]. These models all interpret types as partial equivalence relations (per's) over suitable Dm structures obtained by the so-called " inverse limit') construction. The main contributions of this paper are to provide a general framework for understanding type recursion in these models and to extend per models to higher-order type functions and additional forms of polymorphism. Since the use of per's over …
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...
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.
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
16356321
Decision trees for geometric models
A fundamental problem in model-based computer vision is that ofidentifying which of a given set of geometric models is present in animage. Considering a “probe” to be an oracle that tells uswhether or not a model is present at a given point, we study the problemof computing efficient strategies (“decision trees”) forprobing an image, with the goal to minimize the number of probesnecessary (in the worst case) to determine which single model ispresent. We show that a <inline-equation><f><fen lp="ceil">lgk<rp post="ceil"></fen></f></inline-equation> height binary decision tree always exists for<?Pub Fmt italic>k<?Pub Fmt /italic> polygonal models (in fixedposition), provided (1) they are non-degenerate (do not shareboundaries) and (2) they share a common point of intersection. Further,we give an efficient algorithm for  constructing such decision treeswhen the models are given as a set of polygons in the plane. We showthat constructing a minimum height tree is NP-complete if either of thetwo assumptions is omitted. We provide an efficient greedy heuristicstrategy and show that, in the general case, it yields a decision treewhose height is at most <inline-equation><f><fen lp="ceil">lgn<rp post="ceil"></fen></f><?Pub Caret></inline-equation> times that of an optimal tree. Finally,we discuss some restricted cases whose special structure allows forimproved results.
60004
When can you fold a map?
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a fiat folding by a sequence of simple folds? There are several models of simple folds; the simplest one-layer simple fold rotates a portion of paper about a crease in the paper by ±180°. We first consider the analogous questions in one dimension lower--bending a segment into a flat object--which lead to interesting problems on strings. We develop efficient algorithms for the recognition of simply foldable 1D crease patterns, and reconstruction of a sequence of simple folds. Indeed, we prove that a 1D crease pattern is flat-foldable by any means precisely if it is by a sequence of one-layer simple folds. 
 
Next we explore simple foldability in two dimensions, and find a surprising contrast: "map" folding and variants are polynomial, but slight generalizations are NP-complete. Specifically, we develop a linear-time algorithm for deciding foldability of an orthogonal crease pattern on a rectangular piece of paper, and prove that it is (weakly) NP-complete to decide foldability of (1) an orthogonal crease pattern on a orthogonal piece of paper, (2) a crease pattern of axis-parallel and diagonal (45-degree) creases on a square piece of paper, and (3) crease patterns without a mountain/valley assignment.
8377397
Boundary recognition in sensor networks by topological methods
Wireless sensor networks are tightly associated with the underlying environment in which the sensors are deployed. The global topology of the network is of great importance to both sensor network applications and the implementation of networking functionalities. In this paper we study the problem of topology discovery, in particular, identifying boundaries in a sensor network. Suppose a large number of sensor nodes are scattered in a geometric region, with nearby nodes communicating with each other directly. Our goal is to find the boundary nodes by using only connectivity information. We do not assume any knowledge of the node locations or inter-distances, nor do we enforce that the communication graph follows the unit disk graph model. We propose a simple, distributed algorithm that correctly detects nodes on the boundaries and connects them into meaningful boundary cycles. We obtain as a byproduct the medial axis of the sensor field, which has applications in creating virtual coordinates for routing. We show by extensive simulation that the algorithm gives good results even for networks with low density. We also prove rigorously the correctness of the algorithm for continuous geometric domains.
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.
7295712
The minimum area spanning tree problem
Motivated by optimization problems in sensor coverage, we formulate and study the Minimum-Area Spanning Tree (MAST) problem: Given a set P of n points in the plane, find a spanning tree of P of minimum "area", where the area of a spanning tree T is the area of the union of the n - 1 disks whose diameters are the edges in T. We prove that the Euclidean minimum spanning tree of P is a constant-factor approximation for MAST. We then apply this result to obtain constant-factor approximations for the Minimum-Area Range Assignment (MARA) problem, for the Minimum-Area Connected Disk Graph (MACDG) problem, and for the Minimum-Area Tour (MAT) problem. The first problem is a variant of the power assignment problem in radio networks, the second problem is a related natural problem, and the third problem is a variant of the traveling salesman problem.