waashk/acm huggingface dataset:
new results on deriving protocol specifications from service specifications  previous papers describe an algorithm for deriving a specification of protocol entities from a given service specification. a service specification defines a particular ordering for the execution of service primitives at the different service access points using operators for sequential, parallel and alternative executions. the derived protocol entities ensure the correct ordering by exchanging appropriate synchronization messages, between one another through the underlying communication medium.  this paper presents several new results which represent important improvements to the above protocol derivation approach. first the language restriction to finite behaviors is removed by allowing for the definition of procedures which can be called recursively. secondly, a new derivation algorithm has been developed which is much simpler than the previous one. third, the resulting protocol specifications are much more optimized than those obtained previously.  f. khendek g. von bochmann c. kant
detecting and decomposing self-overlapping curves  paint one side of a rubber disk black and the other side white; stretch the disk any way you wish in three-dimensional space, subject to the condition that from any point in space, if you look down you see either the white side of the disk or nothing at all. now make the stretched disk transparent but color its boundary black; project its boundary into a plane that lies below the disk. the resulting curve is self-overlapping. we show how to test whether a given curve is self-overlapping, and how to count how many essentially different stretchings of the disk could give rise to the same curve.  p. w. shor c. j. van wyk
an improved las vegas primality test  we present a modification of the goldwasser-kilian-atkin primality test, which, when given an input n, outputs either prime or composite, along with a certificate of correctness which may be verified in polynomial time. atkin's method computes the order of an elliptic curve whose endomorphism ring is isomorphic to the ring of integers of a given imaginary quadratic field q( \---d). once an appropriate order is found, the parameters of the curve are computed as a function of a root modulo n of the hilbert class equation for the hilbert class field of q( \---d). the modification we propose determines instead a root of the watson class equation for q( ---d) and applies a transformation to get a root of the corresponding hilbert equation. this is a substantial improvement, in that the watson equations have much smaller coefficients than do the hilbert equations.  e. kaltofen t. valente n. yui
highly continuous runge-kutta interpolants to augment the discrete runge-kutta solutlon to the mitlal valueproblem, piecewlse hermite interpolants have been used to provide acontinuous approximation with a continuous first derivative we showthat it m possible to construct mterpolants with arbltrardy manycontinuous derivatives which have the same asymptotic accuracy andbasic cost as the hermite interpol ants. we also show that theusual truncation coefficient analysis can be applied to these newinterpolants, allowing their accuracy to be examined in more detadas an illustration, we present some globally c2 interpolants foruse with a popular 4th and 5th order runge-kutta pair of dormandand prince, and we compare them theoretically and numerically withexisting interpolants. d. j. higham
algorithm 676 odrpack: software for weighted orthogonal distance regression  in this paper, we describe odrpack, a software package for the weighted orthogonal distance regression problem. this software is an implementation of the algorithm described in [2] for finding the parameters that minimize the sum of the squared weighted orthogonal distances from a set of observations to a curve or surface determined by the parameters. it can also be used to solve the ordinary nonlinear least squares problem. the weighted orthogonal distance regression procedure application to curve and surface fitting and to measurement error models in statistics. the algorithm implemented is an efficient and stable trust region (levenberg-marquardt) procedure that exploits the structure of the problem so that the computational cost per iteration is equal to that for the same type of algorithm applied to the ordinary nonlinear least squares problem. the package allows a general weighting scheme, provides for finite difference derivatives, and contains extensive error checking and report generating facilities.  paul t. boggs janet r. donaldson richaard h. byrd robert b. schnabel
a fourth-order-accurate fourier method for the helmholtz equation in three dimensions  we present fourth-order-accurate compact discretizations of the helmholtz equation on rectangular domains in two and three dimensions with any combination of dirichlet, neumann, or periodic boundary conditions. the resulting systems of linear algebraic equations have the same block- tridiagonal structure as traditional central differences and hence may be solved efficiently using the fourier method. the performance of the method for a variety of test cases, including problems with nonsmooth solutions, is presented. the method is seen to be roughly twice as fast as deferred corrections and, in many cases, results in a smaller discretization error.  ronald f. boisvert
a matlab differentiation matrix suite  a software suite consisting of 17 matlab functions for solving differential equations by the spectral collocation (i.e., pseudospectral) method is presented. it includes functions for computing derivatives of arbitrary order corresponding to chebyshev, hermite, laguerre, fourier, and sinc interpolants. auxiliary functions are included for incorporating boundary conditions, performing interpolation using barycentric formulas, and computing roots of orthogonal polynomials. it is demonstrated how to use the package for solving eigenvalue, boundary value, and initial value problems arising in the fields of special functions, quantum mechanics, nonlinear waves, and hydrodynamic stability.
a set of ada packages for high-precision calculations  the packages described here are designed to perform efficient high-accuracy calculations in cases where there can be serious loss of significance due to rounding errors. numbers are represented by a value part with a variable number of digits in the mantissa and an error estimate which is updated throughout the calculation and which gives a range of possible values for the result of the calculation. for economy and speed, intermediate results are truncated so that the least- significant digits correspond to values only a few orders of magnitude smaller than the error estimate. type definitions and the standard arithmetic operations, together with conversions to and from integers, are provided in one package. the mathematical constants π and euler's gamma are incorporated to a maximum precision of 320 digits in a package that also contains all of the standard elementary functions. separate packages contain input and output procedures and conversion to and from floating-point types.  b. g. s. doman c. j. pursglove w. m. coen
algorithm 769: fortran subroutines for approximate solution of sparse quadratic assignment problems using grasp  we describe fortran subroutines for finding approximate solutions of sparse instances of the quadratic assignment problem (qap) using a greedy randomized adaptive search procedure (grasp). the design and implementation of the code are described in detail. computational results comparing the new subroutines with a dense version of the code (algorithm 754, acm toms) show that the speedup increases with the sparsity of the data.  panos m. pardalos leonidas s. pitsoulis mauricio g. c. resende
algorithm 741; least-squares solution of a linear, bordered, block-diagonal system of equations  a package of fortran subroutines is presented for the least-squares solution of a system of overdetermined, full-rank, linear equations with single- bordered block-diagonal structure. this structure allows for a natural sequential processing, one block diagonal at a time, so that large systems can be handled even on smaller machines. orthogonal transformations in the form of householder reflections are used to factor the system. the routines make heavy use of the levels 1, 2, and 3 blas.  richard d. ray
an operational view on renewal theory  in this paper we derive a formula for the moments of the residual life in operational context, and show that the paradox of residual life holds also in a finite queueing model. in addition, we prove the renewal theorem, show that forward and backward times are independent, and state the memoryless property. as applications we point out how to derive takacs recurrence formula for the moments of the waiting time and how to base the markovian state theory on this.  wolfgang kowalk
expanders obtained from affine transformations  a bipartite graph gn = (u, v, e) is said an (n, k, δ) expander if |u| = |v| = n, |e| ≤ kn, and for any x u, |Γ< ;subscrpt>gn(x)| ≥ (1+δ(1-|x|/n)) |x|, where Γg< subscrpt>n(x) is the set of nodes in v connected to nodes in x with edges in e. in this paper we show that the problem of estimating the coefficient δ of a bipartite graph is reduced to that of estimating the eigenvalue of a matrix related to the graph. as a result we give an explicit construction of (n, 5, 1 - 5/8 2) expanders. by applying gabber and galil's construction to these expanders we obtain n-superconcentrators with 248n edges.  s jimbo a maruoka
a study of the comparative effects of various means of motion cueing during a simulated compensatory tracking task  nasa's langley research center conducted a simulation experiment to ascertain the comparative effects of motion cues (combinations of platform motion and g-seat normal acceleration cues) on compensatory tracking performance. in the experiment, a full six- degree-of-freedom yf-16 model was used as the simulated pursuit aircraft. the langley visual motion simulator (with in-house developed wash-out), and a langley developed g-seat were principal components of the simulation. the results of the experiment were examined utilizing univariate and multivariate techniques.  the statistical analyses demonstrate that the platform motion and g-seat cues provide additional information to the pilot that allows substantial reduction of lateral tracking error. also, the analyses show that the g-seat cue helps reduce vertical error. the differences in pilot control behavior make it impossible to statistically determine if the motion platform and g-seat cues have an additive effect, or whether the motion or g-seat cues can be interchanged. however, it is anticipated that additional data will overcome this problem.  burnell t. mckissick billy r. ashworth russell v. parrish dennis j. martin
indefinite integration with validation  we present an overview of two approaches to validated one-dimensional indefinite integration. the first approach is to find an inclusion of the integrand, then integrate this inclusion to obtain an inclusion of the indefinite integral. inclusions for the integrand may be obtained from taylor polynomials, tschebyscheff polynomials, or other approximating forms which have a known error term. the second approach finds an inclusion of the indefinite integral directly as a linear combination of function evaluations plus an interval-valued error term. this requires a self-validating form of a quadrature formula such as gaussian quadrature. in either approach, composite formulae improve the accuracy of the inclusion.  the result of the validated indefinite integration is an algorithm which may be represented as a character string, a subroutine in a high-level programming language such as pascal-sc or fortran, or as a collection of data. an example is given showing the application of validated indefinite integration in constructing a validated inclusion of the error function, erf(x).  george corliss gary krenz
an evaluation of some new cyclic linear multistep formulas for stiff odes  we evaluate several sets of cyclic linear multistep formulas (clmfs). one of these sets was derived by tischer and sacks-davis. three new sets of formulas have been derived and we present their characteristics.  the formulas have been evaluated by comparing the performance of four versions of a code which implements clmfs. the four versions are very similar and each version implements one of the sets of clmfs being studied. we compare the performance of these codes with that of a widely used code, lsode. one of the new sets of clmfs is not only much more efficient in solving stiff problems that have a jacobian with eigenvalues close to the imaginary axis but is almost as efficient as lsode in solving other problems. this is a significant improvement over the ony other clmf code available, stint from tendler, bickart, and picel.  p. e. tischer g. k. gupta
algorithm 674: fortran codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation  we omitted giving this article an acm algorithm number when it was first published in its entirety in the december 1988 issue of toms, vol. 14, no. 4, pp. 381--396. to correct this, we do so here, and reprint the title as a pointer to the original article.  nicholas j. higham
on the existence of equilibria in noncooperative optimal flow control  the existence of nash equilibria in noncooperative flow control in a general product-form network shared by k users is investigated. the performance objective of each user is to maximize its average throughput subject to an upper bound on its average time-delay. previous attempts to study existence of equilibria for this flow control model were not successful, partly because the time-delay constraints couple the strategy spaces of the individual users in a way that does not allow the application of standard equilibrium existence theorems from the game theory literature. to overcome this difficulty, a more general approach to study the existence of nash equilibria for decentralized control schemes is introduced. this approach is based on directly proving the existence of a fixed point of the best reply correspondence of the underlying game. for the investigated flow control model, the best reply correspondence is shown to be a function, implicitly defined by means of k interdependent linear programs. employing an appropriate definition for continuity of the set of optimal solutions of parameterized linear programs, it is shown that, under appropriate conditions, the best reply function is continuous. brouwer's theorem implies, then, that the best reply function has a fixed point.  yannis a. korilis aurel a. lazar
an approach to the k paths problem  the k paths problem asks whether it is possible to find k edge-disjoint paths joining k given pairs of vertices in a graph. we show that this problem can be solved in polynomial time for k≤5 if the input graph is k+2 -connected.  it follows from this result that under the same restriction, the subgraph homeomorphism problem is polynomial for any pattern graph with five or fewer edges.  allen cypher
an automatic continuation strategy for the solution of singularly perturbed nonlinear boundary value problems  in a recent paper, the present authors derived an automatic continuation algorithm for the solution of linear singular perturbation problems. the algorithm was incorporated into two general-purpose codes for solving boundary value problems, and it was shown to deal effectively with a large test set of linear problems. the present paper describes how the conintuation algorithm for linear problems can be extended to deal with the nonlinear case. the results of exstensive numerical testing on a set of nonlinear singular perturbation problems are given, and these clearly demonstrate the efficacy of continuation for solving such problems.
processing encrypted data  a severe problem in the processing of encrypted data is that very often, in order to perform arithmetic operations on the data, one has to convert the data back to its nonencrypted origin before performing the required operations. this paper addresses the issue of processing data that have been encrypted while the data are in an encrypted mode. it develops a new approach for encryption models that can facilitate the processing of such data. the advantages of this approach are reviewed, and a basic algorithm is developed to prove the feasibility of the approach.  niv ahituv yeheskel lapid seev neumann
an efficient representation for sparse sets  sets are a fundamental abstraction widely used in programming. many representations are possible, each offering different advantages. we describe a representation that supports constant-time implementations of clear-set, add- member, and delete-member. additionally, it supports an efficient forall iterator, allowing enumeration of all the members of a set in time proportional to the cardinality of the set.  we present detailed comparisons of the costs of operations on our representation and on a bit vector representation. additionally, we give experimental results showing the effectiveness of our representation in a practical application: construction of an interference graph for use during graph-coloring register allocation.  while this representation was developed to solve a specific problem arising in register allocation, we have found it useful throughout our work, especially when implementing efficient analysis techniques for large programs. however, the new representation is not a panacea. the operations required for a particular set should be carefully considered before this representation, or any other representation, is chosen.  preston briggs linda torczon
superimposing encrypted data  much has been written about the necessity of processing data in the encrypted form. however, no satisfactory method of processing encrypted data has been published to date. ahitub et al. [2] have analyzed the possibilities of using some special algorithms to add encrypted data. rivest et al. [10] have suggested the use of an algorithm based on homomorphic functions for processing encrypted data. the main limitation of this algorithm is that such functions can be broken by solving a set of linear equations, as noted by [2]. the public-key crytosystem described in [11] can be used to multiply encrypted data but cannot be used to add encrypted data and is therefore not appropriate for some practical applications such as bank transactions. abadi, feigenbaum and kilian [1] presented some general theorems concerning the problem of computing with encrypted data and formulated a framework to prove precise statements about what an encrypted instance hides and reveals; they also described encryption schemes for some well-known functions.  k. w. yu tong lai yu
the design of substitution-permutation networks resistant to differential and linear cryptanalysis  in this paper we examine a class of product ciphers referred to as substitution-permutation networks. we investigate the resistance of these cryptographic networks to two important attacks: differential cryptanalysis and linear cryptanalysis. in particular, we develop upper bounds on the differential characteristic probability and on the probability of a linear approximation as a function of the number of rounds of substitutions. further, it is shown that using large s-boxes with good diffusion characteristics and replacing the permutation between rounds by an appropriate linear transformation is effective in improving the cipher security in relation to these two attacks.  h. m. heys s. e. tavares
tree rebalancing in optimal time and space  a simple algorithm is given which takes an arbitrary binary search tree and rebalances it to form another of optimal shape, using time linear in the number of nodes and only a constant amount of space (beyond that used to store the initial tree). this algorithm is therefore optimal in its use of both time and space. previous algorithms were optimal in at most one of these two measures, or were not applicable to all binary search trees. when the nodes of the tree are stored in an array, a simple addition to this algorithm results in the nodes being stored in sorted order in the initial portion of the array, again using linear time and constant space.  q. f stout b. l warren
arithmetic coding revisited  over the last decade, arithmetic coding has emerged as an important compression tool. it is now the method of choice for adaptive coding on myltisymbol alphabets because of its speed, low storage requirements, and effectiveness of compression. this article describes a new implementation of arithmetic coding that incorporates several improvements over a widely used earlier version by witten, neal, and cleary, which has become a de facto standard. these improvements include fewer multiplicative operations, greatly extended range of alphabet sizes and symbol probabilities, and the use of low- precision arithmetic, permitting implementation by fast shift/add operations. we also describe a modular structure that separates the coding, modeling, and probability estimation components of a compression system. to motivate the improved coder, we consider the needs of a word-based text compression program. we report a range of experimental results using this and other models. complete source code is available.  alistair moffat radford m. neal ian h. witten
maintaining order in a linked list  we present a new representation for linked lists. this representation allows one to efficiently insert objects into the list and to quickly determine the order of list elements. the basic data structure, called an indexed 2-3 tree, allows one to do n inserts in o(nlogn) steps and to determine order in constant time. we speed up the algorithm by dividing the data structure up into log*n layers. the improved algorithm does n insertions and comparisons in o(nlog*n) steps. the paper concludes with two applications: determining ancestor relationships in a growing tree and maintaining a tree structured environment (context tree).  paul f. dietz
a family of conservative codes with block delimiters for decoding without a phase-locked loop  the family of conservative codes is a new scheme for encoding and decoding digital data for very high speed serial communication. these codes are characterized by having a constant number of transitions in each codeword and a known delimiting transition (rising or falling edge) at the end of each codeword. the conservative encoding scheme is primarily intended for binary data transmission in a single mode fiber optic network.  additional constraints imposed on the encoding are balancing each codeword, i.e., making the number of zeros and ones equal, and limiting the maximum run- lengths of the high and low level. the purpose of these is to limit the dc shift of ac-coupled receivers and thereby increase the decoding reliability and decrease the optical receiver complexity. it is shown that both constraints can be imposed simultaneously without a significant degradation in encoding efficiency.  the decoding and serial-to-parallel conversion are achieved by directly using the serial signal transitions without recovering the receiving clock explicitly with a phase-locked loop. it is possible to record information from multiple asynchronous sources without a training period.  yoram ofek
reducing the retrieval time of hashing method by using predictors  many methods for resolving collisions in hashing techniques have been proposed. they are classified into two main categories: open addressing and chaining. in this paper, other methods are presented that are intermediate between the two categories. the basic idea of our methods is the use of one or more predictors reserved per cell instead of a link field as in the chaining method. the predictors are used to maintain loose synonym chains. after describing the methods, the efficiencies are estimated theoretically and verified experimentally. in comparison with the chaining method, we prove that our methods significantly reduce the average number of probes necessary to retrieve a key without expending extra space.  seiichi nishihara katsuo ikeda