This paper gives an overview of intersection type assignment for the Lambda Calculus, as well as compares in detail variants that have been defined in the past. It presents the essential intersection type assignment s...
详细信息
This paper gives an overview of intersection type assignment for the Lambda Calculus, as well as compares in detail variants that have been defined in the past. It presents the essential intersection type assignment system, that will prove to be as powerful as the well-known BCD-system. It is essential in the following sense: it is an almost syntax directed system that satisfies all major properties of the BCD-system, and the types used are the representatives of equivalence classes of types in the BCD-system. The set of typeable terms can be characterized in the same way, the system is complete with respect to the simple type semantics, and it has the principal type property.
Berry's category of dI-domains with stable functions is a relatively intricate, yet elegant, framework for semantics of programming languages. Despite over 15 years of work in the area, the exact reasons for distr...
详细信息
Berry's category of dI-domains with stable functions is a relatively intricate, yet elegant, framework for semantics of programming languages. Despite over 15 years of work in the area, the exact reasons for distributivity (Axiom d) and finitariness (Axiom I) have not been fully explicated. This paper shows that Axiom d and Axiom I are important when one works within the realm of Scott-domains. In particular, it has been shown that (i) if [D ->(s) D] has a countable basis, then D must be finitary, for any Scott-domain D;(ii) if [D ->(s) D] is bounded complete, then D must be distributive, for any finitary Scott-domain D. Therefore, the category of dI-domains is the largest cartesian closed category within omega-algebraic, bounded complete domains, with the exponential being the stable function space.
Testing plays an integral part in many areas of computer science. In relation to computational learning theory, testing can be viewed as an inverse process to learning. Testing algorithms create a set of examples for ...
详细信息
Testing plays an integral part in many areas of computer science. In relation to computational learning theory, testing can be viewed as an inverse process to learning. Testing algorithms create a set of examples for a given target concept that distinguish it from other concepts, while learning algorithms use a given set of examples to correctly infer an unknown concept. In this paper we develop a model for approximate testing of concepts, which relates to the PAC (probably almost correct) model of learning as well as other learning models. In approximate testing, a concept that passes the given tests is only required to be correct to within a given error tolerance rather than being exactly correct. We define what it means for a concept class to be approximately testable, and we investigate general properties of a concept class that make it testable or untestable. We define a new measure that is similar to the Vapnik-Chervonenkis dimension, called the testing dimension of a concept class, and show how it yields untestability results for certain concept classes. We also compare our testing model to several different learning models, and we discuss the topics of nonredundant test sets and generic test sets.
A hybrid finite-difference technique, for modelling the induction in compact isolated heterogeneous conductors by external low-frequency time-harmonic electric fields, is described. A quasi-static finite-difference ti...
详细信息
A hybrid finite-difference technique, for modelling the induction in compact isolated heterogeneous conductors by external low-frequency time-harmonic electric fields, is described. A quasi-static finite-difference time domain code is used to model the induction in a low-resolution model of the conductor. In particular, this code solves the external problem and yields the surface charge density induced on the body. Although the internal fields are also computed, the surface charge density can be interpolated onto the surface of a higher-resolution model of the conducting body. These are then used as the source terms for a scalar-potential finite-difference code capable of solving the interior problem at an enhanced resolution, yet with a similar computational load. This paper describes the theory for integrating the two techniques. It demonstrates the validity of the technique, as applied to a human body model exposed to a 60-Hz uniform electric field. Extremely good agreement is demonstrated for the low-resolution internal fields computed by the two codes. The feasibility of the interpolation procedure and associated higher-resolution internal calculations are then illustrated. (C) 1997 Academic Press.
The modular decomposition of a graph or relation has a large number of combinatorial applications. It divides the structure into a set of "prime" induced substructures, which cannot be further decomposed. Re...
详细信息
The modular decomposition of a graph or relation has a large number of combinatorial applications. It divides the structure into a set of "prime" induced substructures, which cannot be further decomposed. Recent work on graphs and k-ary relations has focused on the discovery that prime induced substructures are densely nested when they occur. Lower bounds on the "nesting density" of prime substructures in graphs are used heavily in the only known linear-time algorithm for directed graphs. We improve on the previously known lower bounds for k-ary relations, and show that no further improvement is possible. (C) 2001 Elsevier Science B.V. All rights reserved.
The Highway Capacity Manual 2010 (HCM 2010) contains computational procedures for evaluating traffic operational efficiency of urban street segments. These procedures have been implemented within several commercial so...
详细信息
The Highway Capacity Manual 2010 (HCM 2010) contains computational procedures for evaluating traffic operational efficiency of urban street segments. These procedures have been implemented within several commercial software packages and are likely used by thousands of engineers and planners across the United States. The procedures for urban street capacity analysis contain no logic for handling right turns on red (RTORs) or for handling special cases of RTORs such as shielded and free right turns. A new proposed RTOR modeling framework is described for urban streets in the HCM 2010. When significant upstream RTOR flows exist, the proposed logic is designed to generate more realistic flow profiles. Three types of experimental results are presented: they demonstrate the improved modeling accuracy of the proposed logic. First, it is shown that macroscopic flow profile shapes are now more visually sensible because they now illustrate RTOR flows moving at the appropriate times. Second, macroscopic flow profile shapes are now more consistent with microscopic vehicle trajectories. Third, a statistical analysis shows that when the proposed logic is used, HCM 2010 performance measures become more consistent with the performance measures generated by microsimulation. Finally, case study results show that when the proposed RTOR logic is not used, control delays are sometimes be inaccurate by more than 30%. Given the experimental evidence presented, it is urgent that the proposed improvements be adopted and implemented so that RTOR corridors can be accurately analyzed by the HCM 2010 procedures.
String matching is the problem of finding all occurrences of a string W[0...m - 1] of length m called a pattern, in a longer string J[0...n - 1] of length n called a text. Several string matching algorithms have been ...
详细信息
String matching is the problem of finding all occurrences of a string W[0...m - 1] of length m called a pattern, in a longer string J[0...n - 1] of length n called a text. Several string matching algorithms have been designed to solve the problem in linear time;most of them work in two steps, called pattern preprocessing and text search step. The paper addresses the definition and computation of the shift function in the pattern preprocessing step of on-line string matching algorithms. The shift function depends essentially on the order the pattern characters are compared with the corresponding text characters. We consider a family F of algorithms that do not change the character comparison order J during execution and we present a uniform definition of shift function delta(J) for such algorithms via a function imin(J). The definition allows one to compute delta(J) in O(m log log m) time in the worst case, given imin(J), but sufficient conditions to compute delta(J) in O(m) time are provided. Computing imin(J) requires O(m(2)) comparisons in general. We introduce the class of compact orders (which is the generalization of Knuth-Morris-Pratt, Boyer-Moore and Crochemore-Perrin character comparison orders) and we give algorithms to compute both function imin(J) and shift function delta(J) in O(m) time for all compact orders. We show that given the order J and the pattern W there exists a set C of equivalent orders such that the function imin(K) can be computed in linear time given imin(J) for all orders K is an element of C. Moreover, we characterize two orders in the set C that respectively minimize and maximize the values of the shift function and we show that for both those orders the shift function can be computed in linear time given imin(J).
The skills of a computational physicist are shown to be useful in the seemingly distant field of cardiac electrophysiology. The propagation of cardiac action potentials and their ability to form spiral waves are easil...
详细信息
The skills of a computational physicist are shown to be useful in the seemingly distant field of cardiac electrophysiology. The propagation of cardiac action potentials and their ability to form spiral waves are easily understood at a basic level when standard concepts from the theory of partial differential equations are applied. The design of computer simulations of action potential propagation is facilitated by adapting numerical concepts routinely applied by computational physicists. These concepts must be modified and combined with computer structures standard in computer science to handle the timescale and spatial scale problems unique to the action potential propagation problem. The resulting simulation shows how details of ion channel dynamics determine properties of the spiral wave, including its propagation speed, its period, its stability, and the size of the spiral core. (C) 2000 Academic Press.
Downwards passes on binary trees are essentially functions which pass information down a tree, from the root towards the leaves. Under certain conditions, a downwards pass is both 'efficient' (computable in a ...
详细信息
Downwards passes on binary trees are essentially functions which pass information down a tree, from the root towards the leaves. Under certain conditions, a downwards pass is both 'efficient' (computable in a functional style in parallel time proportional to the depth of the tree) and 'manipulable' (enjoying a number of distributivity properties useful in program construction);we call a downwards pass satisfying these conditions a downwards accumulation. In this paper, we show that these conditions do in fact yield a stronger conclusion: the accumulation can be computed in parallel time proportional to the logarithm of the depth of the tree, on a CREW PRAM machine.
In the framework of perfect loop nests with uniform dependences, tiling is a technique used to group elemental computation points so as to increase computation granularity and to reduce the overhead due to communicati...
详细信息
In the framework of perfect loop nests with uniform dependences, tiling is a technique used to group elemental computation points so as to increase computation granularity and to reduce the overhead due to communication time. We review existing approaches from the literature, together with the optimization criteria that are used for determining a ''good'' or ''optimal'' tiling. Then we explain the need to introduce yet another criterion for defining ''optimal tiling'' in a scalable environment. Although our criterion is more complex than previously used ones, we are able to prove a theorem on optimality, and to provide a constructive method for defining the ''optimal tiling''.
暂无评论