19578302
A lambda calculus of objects and method specialization
An untyped lambda calculus, extended with object primitives that reflect the capabilities of so-called delegation-based object-oriented languages, is presented. A type inference system allows static detection of errors, such as message not understood, while at the same time allowing the type of an inherited method to be specialized to the type of the inheriting object. Type soundness, in the form of a subject-reduction theorem, is proved, and examples illustrating the expressiveness of the pure calculus are presented.<<ETX>>
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.
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
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.
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.
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...
14245718
Fast and effective stripification of polygonal surface models
A fundamental algorithmic problem in computer graphics is t hat of computing a succinct encoding of a triangulation of a polygo nal surface model in order to be able to transmit and render it efficie ntly. The goal is to take a given polygonal surface model, whose fac ts are given by (possibly multiply-connected) polygons, tria ngulate its facets, and then decompose the triangulation into a small nu mber of “tristrips,” each of which has its connectivity stored im plicitly in the ordering of the data points. We develop methods that ar e effective in solving the stripification problem, both in the ory (provably good encodings) and in practice. Our methods are based o n carefully constructed search trees in the dual graph, follo wed by algorithms to decompose dual trees into tristrips. One decomp osition algorithm is provably optimal (based on dynamic programmin g), allowing us a sound basis of comparison among our other (heur istic) algorithms. We demonstrate the speed and effectivenes s of our algorithms through a battery of experiments. In comparison with the recently released STRIPE system for stripification, we find that our stripifier,FTSG, produces comparable or better quality encodings, while requiring significantly less computing time on a large variety of datasets. Further, FTSG is carefully engineered and implemented to be robust, even in the face of highly degenerate and corrupted real-world data. CR Categories: I.3.3 [Computer Graphics]: Picture/Image Generation—displaying algorithms; I.3.5 [Computer Graph ics]: Computational Geometry and Object Modeling—Geometric alg orithm, languages, and systems.
2767172
Fast rendering of irregular grids
We propose a fast algorithm for rendering general irregular grids. Our method uses a sweep-plane approach to accelerate ray casting, and can handle disconnected and nonconvex (even with holes) unstructured irregular grids with a rendering cost that decreases as the "disconnectedness" decreases. The algorithm is carefully tailored to exploit spatial coherence even if the image resolution differs substantially from the object space resolution. In this paper, we establish the practicality of our method through experimental results based on our implementation, and we also provide theoretical results, both lower and upper bounds, on the complexity of ray casting of irregular grids.
18575731
Classifying the World Anti-Doping Agency's 2005 Prohibited List Using the Chemistry Development Kit Fingerprint
We used the freely available Chemistry Development Kit (CDK) fingerprint to classify 5235 representative molecules taken from ten banned classes in the 2005 World Anti-Doping Agency’s (WADA) prohibited list, including molecules taken from the corresponding activity classes in the MDL Drug Data Report (MDDR). We used both Random Forest and k-Nearest Neighbours (kNN) algorithms to generate classifiers. The kNN classifiers withk = 1 gave a very slightly better Matthews Correlation Coefficient than the Random Forest classifiers; the latter, however, predicted fewer false positives. The performance of kNN classifiers tended to decline with increasing k. The performance of the CDK fingerprint is essentially equivalent to that of Unity 2D. Our results suggest that it will be possible to use freely available chemoinformatics tools to aid the fight against drugs in sport, while minimising the risk of wrongfully penalising innocent athletes.
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.
10071461
Separation and approximation of polyhedral objects
Given a family of disjoint polygons P<subscrpt>1</subscrpt>, P<subscrpt>2</subscrpt>,…, P<subscrpt><italic>k</italic></subscrpt> in the plane, and an integer parameter <italic>m</italic>, it is <italic>NP</italic>-complete to decide if the <italic>P<subscrpt>i</subscrpt></italic>'s can be <italic>separated</italic> by a polygonal family consisting of <italic>m</italic> edges, that is, if there exist polygons <italic>R</italic><subscrpt>1</subscrpt>, <italic>R</italic><subscrpt>2</subscrpt>,…, <italic>R<subscrpt>k</subscrpt></italic> with pairwise-disjoint boundaries such that <italic>P<subscrpt>i</subscrpt></italic> *** <italic>R<subscrpt>i</subscrpt></italic> and &Sgr;|<italic>R<subscrpt>i</subscrpt></italic>| ≤ <italic>m</italic>. In three dimensions, the problem  of separating even two <italic>nested convex</italic> polyhedra by a <italic>k</italic>-facet polyhedron is <italic>NP</italic>-complete. Many other extensions and generalizations of the polyhedral separation problem, either to families of polyhedra or to higher dimensions, are also intractable.
In this paper, we present efficient approximation algorithms for constructing separating families of near-optimal size. Our main results are as follows. In two dimensions, we give an <italic>O</italic>(<italic>n</italic> log <italic>n</italic>) time algorithm for constructing a separating family whose size is within a constant factor of an optimal separating family; <italic>n</italic> is the number of edges in the input family of polygons. In three dimensions, we can separate a convex   polyhedron from a nonconvex polyhedron with a convex polyhedral surface whose <italic>facet-complexity</italic> is <italic>O</italic>(log <italic>n</italic>, times the optimal, where <italic>n</italic> = |<italic>P</italic>|+|<italic>Q</italic>| is the complexity of the input polyhedra. Our algorithm runs in <italic>O</italic>(<italic>n</italic><supscrpt>4</supscrpt>) time, but improves to <italic>O</italic> (<italic>n</italic><supscrpt>3</supscrpt>) time if the two polyhedra are nested and convex.
Our algorithm for separating a convex polyhedron from a nonconvex polyhedron extends to higher dimensions. In <italic>d</italic> dimensions, for <italic>d</italic> ≥ 4, the facet-complexity of the approximation polyhedron is <italic>O</italic>(<italic>d</italic> log   <italic>n</italic>) times the optimal, and the algorithm runs in <italic>O</italic>(<italic>n<supscrpt>d+1</subscrpt></italic>)time. Finally, we also obtain results on separating sets of points, a family of convex polyhedra, and separation by non-polyhedral surfaces, such as spherical patches.