6372262
Algorithmic aspects of type inference with subtypes
We study the complexity of type inference for programming languages with subtypes. There are three language variations that effect the problem: (i) basic functions may have polymorphic or more limited types, (ii) the subtype hierarchy may be fixed or vary as a result of subtype declarations within a program, and (iii) the subtype hierarchy may be an arbitrary partial order or may have a more restricted form, such as a tree or lattice. The naive algorithm for infering a most general polymorphic type, undervariable subtype hypotheses, requires deterministic exponential time. If we fix the subtype ordering, this upper bound grows to nondeterministic exponential time. We show that it is NP-hard to decide whether a lambda term has a type with respect to a fixed subtype hierarchy (involving only atomic type names). This lower bound applies to monomorphic or polymorphic languages. We give PSPACE upper bounds for deciding polymorphic typability if the subtype hierarchy has a lattice structure or the subtype hierarchy varies arbitrarily. We also give a polynomial time algorithm for the limited case where there are of no function constants and the type hierarchy is either variable or any fixed lattice.
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...
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.
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
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.
16824358
On Minimum-Area Hulls
Abstract. We study some minimum-area hull problems that generalize the notion of convex hull to star-shaped and monotone hulls. Specifically, we consider the minimum-area star-shaped hull problem: Given an n -vertex simple polygon P , find a minimum-area, star-shaped polygon P* containing P . This problem arises in lattice packings of translates of multiple, nonidentical shapes in material layout problems (e.g., in clothing manufacture), and has been recently posed by Daniels and Milenkovic. We consider two versions of the problem: the restricted version, in which the vertices of P* are constrained to be vertices of P , and the unrestricted version, in which the vertices of P* can be anywhere in the plane. We prove that the restricted problem falls in the class of ``3sum-hard'' (sometimes called ``n2 -hard'') problems, which are suspected to admit no solutions in o(n2) time. Further, we give an O(n2) time algorithm, improving the previous bound of O(n5) . We also show that the unrestricted problem can be solved in O(n2 p(n)) time, where p(n) is the time needed to find the roots of two equations in two unknowns, each a polynomial of degree O(n) . We also consider the case in which P* is required to be monotone, with respect to an unspecified direction; we refer to this as the minimum-area monotone hull problem. We give a matching lower and upper bound of Θ(n log n) time for computing P* in the restricted version, and an upper bound of O(n q(n)) time in the unrestricted version, where q(n) is the time needed to find the roots of two polynomial equations in two unknowns with degrees 2 and O(n) .
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.
31663632
MACiE: a database of enzyme reaction mechanisms
SUMMARY
MACiE (mechanism, annotation and classification in enzymes) is a publicly available web-based database, held in CMLReact (an XML application), that aims to help our understanding of the evolution of enzyme catalytic mechanisms and also to create a classification system which reflects the actual chemical mechanism (catalytic steps) of an enzyme reaction, not only the overall reaction.


AVAILABILITY
http://www-mitchell.ch.cam.ac.uk/macie/.
28274388
Query-Sensitive Ray Shooting
Ray (segment) shooting is the problem of determining the first intersection between a ray (directed line segment) and a collection of polygonal or polyhedral obstacles. In order to process queries efficiently, the set of obstacle polyhedra is usually preprocessed into a data structure. In this paper we propose a query-sensitive data structure for ray shooting, which means that the performance of our data structure depends on the local geometry of obstacles near the query segment. We measure the complexity of the local geometry near the segment by a parameter called the simple cover complexity, denoted by scc(s) for a segment s. Our data structure consists of a subdivision that partitions the space into a collection of polyhedral cells, each of O(1) complexity. We answer a segment shooting query by wallking along the segment through the subdivision. Our first result is that, for any fixed dimension d, there exists a simple hierarchical subdivision in which no query segment s intersects more than O(scc(s)) cells. Our second result shows that in two dimensions such a subdivision of size O(n) can be constructed in time O(nlogn), where n is the total number of vertices in all the obstacles.
11557966
An algorithmic study of manufacturing paperclips and other folded structures
We study algorithmic aspects of bending wires and sheet metal into a specified structure. Problems of this type are closely related to the question of deciding whether a simple non-self-intersecting wire structure (a carpenter's ruler) can be straightened, a problem that was open for several years and has only recently been solved in the affirmative. If we impose some of the constraints that are imposed by the manufacturing process, we obtain quite different results. In particular, we study the variant of the carpenter's ruler problem in which there is a restriction that only one joint can be modified at a time. For a linkage that does not self-intersect or self-touch, the recent results of Connelly et al. and Streinu imply that it can always be straightened, modifying one joint at a time. However, we show that for a linkage with even a single vertex degeneracy, it becomes NP-hard to decide if it can be straightened while altering only one joint at a time. If we add the restriction that each joint can be altered at most once, we show that the problem is NP-complete even without vertex degeneracies. In the special case, arising in wire forming manufacturing, that each joint can be altered at most once, and must be done sequentially from one or both ends of the linkage, we give an efficient algorithm to determine if a linkage can be straightened.