waashk/acm huggingface dataset:
quickly detecting relevant program invariants  explicitly stated program invariants can help programmers by characterizing certain aspects of program execution and identifying program properties that must be preserved when modifying code. unfortunately, these invariants are usually absent from code. previous work showed how to dynamically detect invariants from program traces by looking for patterns in and relationships among variable values. a prototype implementation, daikon, accurately recovered invariants from formally-specified programs, and the invariants it detected in other programs assisted programmers in a software evolution task. however, daikon suffered from reporting too many invariants, many of which were not useful, and also failed to report some desired invariants.  this paper presents, and gives experimental evidence of the efficacy of, four approaches for increasing the relevance of invariants reported by a dynamic invariant detector. one of them --- exploiting unused polymorphism --- adds desired invariants to the output. the other three --- suppressing implied invariants, limiting which variables are compared to one another, and ignoring unchanged values --- eliminate undesired invariants from the output and also improve runtime by reducing the work done by the invariant detector.  michael d. enst adam czeisler william g. griswold david notkin
exact learning of read-k disjoint dnf and not-so- disjoint dnf  a polynomial-time algorithm is presented for exactly learning the class of read-k disjoint dnf formulas\\---boolean formulas in disjunctive normal form where each variable appears at most k) and every assignment to the variables satisfies at most one term of f. the (standard) protocol used allows the learning algorithm to query whether a given assignment of boolean variables satisfies the dnf formula to be learned (membership queries), as well as to obtain counterexamples to the correctness of its current hypothesis which can be any arbitrary dnf formula (equivalence queries). the formula output by the learning algorithm is logically equivalent to the formula to be learned. we show that this result also applies for a generalization of read-k disjoint dnf which we call read-k sat-j dnf; these are dnf formulas in which every variable appears at most k times and every assignment satisfies at most j terms.  howard aizenstein leonard pitt
symbolic parametrization of pipe and canal surfaces  a canal surface s, generated by a parametrized curve m(t), in r3 is the envelope of the set of spheres with radius r(t) centered at m(t). this concept generalizes the classical offsets (for r(t) = const) of plane curves. in this paper we develop elementary symbolic methods for generating a rational parametrization of canal surfaces generated by rational curves m(t) with rational radius variation r(t). in a pipe surface r(t) is constant.  gunter landsmann josef schicho franz winkler erik hillgarter
the union of congruent cubes in three dimensions  a {\em dihedral (trihedral) wedge} is the intersection of two (resp. t hree) half-spaces in $\reals^3$. it is called {\em $\alpha$-fat} if the angle (resp., solid angle) determined by these half-spaces is at least $\alpha>0$. if, in addition, the sum of the three face angles of a trihedral wedge is at least $\gamma >4\pi/3$, then it is called {\em $(\gamma,\alpha)$-substantially fat}. we prove that, for any fixed $\gamma>4\pi/3, \alpha>0$, the combinatorial complexity of the union of $n$ (a) $\alpha$-fat dihedral wedges, (b) $(\gamma,\alpha)$-substantially fat trihedral wedges is at most $o(n^{2+\eps})$, for any $\eps>0$, where the constants of proportionality depend on $\eps$, $\alpha$ (and $\gamma$).  we obtain as a corollary that the same upper bound holds for the combinatorial complexity of the union of $n$ (nearly) congruent cubes in $\reals^3$. these bounds are not far from being optimal.  j. pach ido safruti micha sharir
dynamic point location in general subdivisions  the dynamic planar point location problem is the task of maintaining a dynamic set s of n non-intersecting, except possibly at endpoints, line segments in the plane under the following operations:  •locate(q point): report the segment immediately above q, i.e., the first segment intersected by an upward vertical ray starting at < italic>q;   226;insert(s segment): add segment s to the collection s segments;  < ;p>•delete(s segment): remove segment s from the collection s of segments.  we present a solution which requires space o(n), has query and insertion time o(log n loglog n) and deletion time o(log2 n). a query time below o(log2 n) was previously only known for monotone subdivisions and horizontal segments and required non-linear space.  hanna baumgarten hermann jung kurt mehlhorn
the expressibility of languages and relations by word equations  classically, several properties and relations of words, such as "being a power of the same word" can be expressed by using word equations. this paper is devoted to a general study of the expressive power of word equations. as main results we prove theorems which allow us to show that certain properties of words are not expressible as components of solutions of word equations. in particular, "the primitiveness" and "the equal length" are such properties, as well as being "any word over a proper subalphabet".  juhani karhumäki filippo mignosi wojciech plandowski
ensembles reconnaissables de mots biinfinis  the purpose of automata theory is to study and classify those properties of words that may be defined by a finite structure, say a finite automaton or a finite monoid. it seems natural to consider the same problem for infinite words. this amounts to studying the asymptotic behaviour of finite automata. as is well-known, this breaks the equivalence between determinism and non- determinism of finite automata.  the study of the infinite behaviour of finite automata is based on a deep theorem due to b-&-uuml;chi and mc naughton: the recognizable sets of infinite words are the finite boolean combinations of deterministic ones (i.e. recognized by deterministic automata).  the aim of this paper is to build an analogous theorem for two-sided infinite sequences. we define a biinfinite word as the equivalence class under the shift of a two-sided infinite sequence. the recognizable sets of biinfinite words are defined in a natural way and one is led to a two-sided notion of determinism. this notion seems to be new and justifies the consideration of biinfinite words.  the main result of this paper is the extension to biinfinite words of the theorem of b-&-uuml;chi and mc naughton: the recognizable sets of biinfinite words are the finite boolean combinations of deterministic ones (theorem 3.1).  there exist three available proofs of b-&-uuml;chi-mc naughton's theorem. the original one by mc naughton [4] is hard to read. the proof given by eilenberg in his book [2] has been constructed by sch-&-uuml;tzenberger and eilenberg from mc naughton's proof; it is similar to that of rabin [5]. finally, sch-&-uuml;tzenberger gave a further proof in [6], which makes the argument more direct by using the methods of the theory of finite monoids. the proof of our main result follows closely sch-&-uuml;tzenberger's method. this method allows to reduce the two-sided case to the one-sided case, although this seems very difficult to obtain directly.  in the first section, we briefly recall the theory of the one-sided infinite behaviour of finite automata. in particular, we give sch-&-uuml;tzenberger's proof of b-&-uuml;chi-mc naughton's theorem. the elements of this proof are used in the proof of our main result. in the second section we define the notions of biinfinite word, biautomaton and deterministic biautomaton. the last section contains the proof of our main result.  maurice nivat dominique perrin
improving abstract interpretations by combining domains  in this paper we consider static analyses based on abstract interpretation of logic programs over combined domains. it is known that analyses over combined domains potentially provide more information than obtainable by performing the independent abstract interpretations. however, the construction of a combined analysis often requires redefining the basic operations for the combined domain. we demonstrate for logic programs that in practice it is possible to obtain precision in a combined analysis without redefining the basic operations. we also propose a way of performing the combination which can be more precise than the straightforward application of the classical "reduced product" approach, while keeping the original components of the basic operations. the advantage of the approach is that proofs of correctness for the new domains are not required and implementations can be reused. we illustrate our results by showing that a combined sharing analysis--- constructed from "old" proposals---compares well with other "new" proposals suggested in recent literature both from the point of view of efficiency and accuracy.  m. codish a. mulkers m. bruynooghe m. garcía de la banda m. hermenegildo
on the power of bounded concurrency ii: pushdown automata  this is the second in a series of papers on the inherent power of bounded cooperative concurrency, whereby an automaton can be in some bounded number of states that cooperate in accepting the input. in this paper, we consider pushdown automata. we are interested in differences in power of expression and in exponential (or higher) discrepancies in succinctness between variants of pda's that incorporate nondeterminism (e), pure parallelism (a), and bounded cooperative concurrency (c). technically, the results are proved for cooperating push-down automata with cooperating states, but they hold for appropriate versions of most concurrent models of computation. we exhibit exhaustive sets of upper and lower bounds on the relative succinctness of these features for three classes of languages: deterministic context-free, regular, and finite. for example, we show that c represents exponential savings in succinctness in all cases except when both e and a are present (i.e., except for alternating automata), and that e and a represent unlimited savings in succinctness in all cases.  tirza hirst david harel
simultaneous writes of parallel random access machines do not help to compute simple arithmetic functions  the ability of the strongest parallel random access machine model wram is investigated. in this model different processors may simultaneously try to write into the same cell of the common memory. it has been shown that a parallel ram without this option (pram), even with arbitrarily many processors, can almost never achieve sublogarithmic time. on the contrary, every function with a small domain like binary values in case of boolean functions can be computed by a wram in constant time. the machine makes fast table look-ups using its simultaneous write ability. the main result of this paper implies that in general this is the "only way" to perform such fast computations and that a domain of small size is necessary. otherwise simultaneous writes do not give an advantage. functions with large domains for which any change of one of the n arguments also changes the result are considered, and a logarithmic lower time bound for wrams is proved. this bound can be achieved by machines that do not perform simultaneous writes. a simple example of such a function is the sum of n natural numbers.  rudiger reischuk
practical parallel algorithms for personalized communication and integer sorting  a fundamental challenge for parallel computing is to obtain high-level, architecture independent, algorithms which efficiently execute on general- purpose parallel machines. with the emergence of message passing standards such as mpi, it has become easier to design efficient and portable parallel algorithms by making use of these communication primitives. while existing primitives allow an assortment of collective communication routines, they do not handle an important communication event when most or all processors have non-uniformly sized personalized messages to exchange with each other. we focus in this paper on the h-relation personalized communication whose efficient implementation will allow high performance implementations of a large class of algorithms. while most previous h-relation algorithms use randomization, this paper presents a new deterministic approach for h-relation personalized communication with asymptotically optimal complexity for h>p2. as an application, we present an efficient algorithm for stable integer sorting.  the algorithms presented in this paper have been coded in split-c and run on a variety of platforms, including the thinking machines cm-5, ibm sp-1 and sp-2, cray research t3d, meiko scientific cs-2, and the intel paragon. our experimental results are consistent with the theoretical analysis and illustrate the scalability and efficiency of our algorithms across different platforms. in fact, they seem to outperform all similar algorithms known to the authors on these platforms.  david a. bader david r. helman joseph jájá
simplifying array processing languages a language like apl was a masterpiece of simplification when seen through the eyes of a computer user of the seventies. the virtues of simplicity are usually held to be many.this paper firstly discusses simplicity in general, reviews some of the writing on simplicity coming from the computing world, and briefly construes the development of apl, and the later j, as being essentially efforts in simplification. possibilities for further simplification are then canvassed.firstly, simplification of the usually accepted but unfortunate naming conventions adopted by array processing languages is proposed. secondly, simplification of the arithmetic is very briefly outlined, more detailed treatment of this topic being available elsewhere. thirdly, syntactic means for having all functions and operations dyadic are treated, and the advantages of adopting such means evaluated. fourthly, the possibilities for a newly distinctive kind of function (called extractions) are described. these are considered as a kind of systematic renaming to supply arguments to functions. fifthly, and in the context of j's simplifications, the need for hyperoperators is asserted. finally, the nature of interpreters for array processing languages is reviewed, and suggestions made for facilities to be provided by such interpreters to aid the process of developing array processing code. neville holmes
computer-aided complexity classification of combinational problems  we describe a computer program that has been used to maintain a record of the known complexity results for a class of 4536 machine scheduling problems. the input of the program consists of a listing of known "easy" problems and a listing of known "hard" problems. the program employs the structure of the problem class to determine the implications of these results. the output provides a listing of essential results in the form of maximal easy and minimal hard problems as well as listings of minimal and maximal open problems, which are helpful in indicating the direction of future research. the application of the program to a restricted class of 120 single-machine problems is demonstrated. possible refinements and extensions to other research areas are suggested. it is also shown that the problem of determining the minimum number of results needed to resolve the status of all remaining open problems in a complexity classification such as ours is itself a hard problem.  b. j. lageweg j. k. lenstra e. l. lawler a. h. g. rinnooy kan
the typed polymorphic label-selective -calculus  formal calculi of record structures have recently been a focus of active research. however, scarcely anyone has studied formally the dual notion--- i.e., argument-passing to functions by keywords, and its harmonization with currying. we have. recently, we introduced the label-selective λ-calculus, a conservative extension of λ-calculus that uses a labeling of abstractions and applications to perform unordered currying. in other words, it enables some form of commutation between arguments. this improves program legibility, thanks to the presence of labels, and efficiency, thanks to argument commuting. in this paper, we propose a simply typed version of the calculus, then extend it to one with ml-like polymorphic types. for the latter calculus, we establish the existence of principal types and we give an algorithm to compute them. thanks to the fact that label-selective λ-calculus is a conservative extension of λ-calculus by adding numeric labels to stand for argument positions, its polymorphic typing provides us with a keyword argument-passing extension of ml obviating the need of records. in this context, conventional ml syntax can be seen as a restriction of the more general keyword-oriented syntax limited to using only implicit positions instead of keywords.  jacques garrigue hassan aït- kaci
np is as easy as detecting unique solutions  for all known np-complete problems the number of solutions in instances having solutions may vary over an exponentially large range. furthermore, most of the well-known ones, such as satisfiability, are parsimoniously interreducible, and these can have any number of solutions between zero and an exponentially large number. it is natural to ask whether the inherent intractability of np- complete problems is caused by this wide variation. in this paper we give a negative answer to this using randomized reductions. we show that the problems of distinguishing between instances of sat having zero or one solution, or finding solutions to instances of sat having unique solutions, are as hard as sat itself. several corollaries about the difficulty of specific problems follow. for example if the parity of the number of solutions of sat can be computed in rp then np = rp. some further problems can be shown to be hard for np or dp via randomized reductions.  l g valiant v v vazirani
deciding linear-trigonometric problems  in this paper, we present a decision procedure for certain linear- trigonometric problems for the reals and integers formalized in a suitable first-order language. the inputs are restricted to formulas, where all but one of the quantified variables occur linearly and at most one occurs both linearly and in a specific trigonometric function. moreover we may allow in addition the integer-part operation in formulas. besides ordinary quantifiers, we allow also counting quantifiers. furthermore we also determine the qualitative structure of the connected components of the satisfaction set of the mixed linear-trigonometric variable. we also consider the decision of these problems in subfields of the real algebraic numbers.  hirokazu anai volker weispfenning
fast algorithms for n-dimensional restrictions of hard problems  let m be a parallel ram with p processors and arithmetic operations addition and subtraction recognizing l nn in t steps. then l can be recognized by a (sequential!) linear search algorithm (lsa) in (n(log(n) + t \\+ log(p))) steps. thus many n-dimensional restrictions of np-complete problems (binary programming, traveling salesman problem, etc.) and even that of the uniquely optimum traveling salesman problem, which is Δp2-com plete, can be solved in polynomial time by an lsa. this result generalizes the construction of a polynomial lsa for the n-dimensional restriction of the knapsack problem previously shown by the author, and destroys the hope of proving nonpolynomial lower bounds for any problem which can be recognized by a pram as above with 2poly(n) processors in poly(n) time.  f meyer auf der heide
an information-theoretic approach to time bounds for on-line computation (preliminary version)  static, descriptional complexity (program size) [16, 9] can be used to obtain lower bounds on dynamic, computational complexity (such as running time). we describe and discuss this "information-theoretic approach" in the following section. paul introduced it in [13], to obtain restricted lower bounds on the time complexity of sorting. we use the approach here to obtain lower time bounds for on-line simulation of one abstract storage unit by another. a major goal of our work is to promote the approach.  wolfgang j. paul joel i. seiferas janos simon
the complexity of the equivalence problem for commutative semigroups and symmetric vector addition systems  this paper shows that the equivalence problems for commutative semigroups and symmetric vector addition systems are decidable in space cnlogn for some fixed constant c, solving an open question by cardoza, lipton, mayr, and meyer. from the exponential-space completeness of the word problems, it follows that our upper bound is nearly optimal.  d t huynh
an analytic model for parallel gaussian elimination on a binary n-cube architecture  this paper summarizes an analytical technique which predicts the time required to execute a given parallel program, with given data, on a given parallel architecture. for illustration purposes, the particular parallel program chosen is parallel gaussian elimination and the particular parallel architecture chosen is a binary n-cube. the analytical technique is based upon a product-form queuing network model which is solved using an iterative method. the technique is validated by comparing performance predictions produced by the model against actual hypercube measurements.  v. a. f. almeida l. w. dowdy m. r. leuze
approximating shortest paths on a convex polytope in three dimensions  given a convex polytope p withn faces in r3, points s,t∈6p, and a parameter 0<e& lt;/g>≤1, we present an algorithm that constructs a path on6p from s tot whose length is at most1+edps,t, where dps,t is the length of the shortest path betweens andt on 6p. the algorithm runs in onlog1/e+1/e3 time, and is relatively simple. the running time ison+1/e3 if we only want the approximate shortest pathdistance and not the path itself. we also present an extension of thealgorithm that computes approximate shortest path distances from a givensource point on 6p to all vertices ofp.  pankaj k. agarwal sariel har-peled micha sharir kasturi r. varadarajan
efficient low-contention parallel algorithms  the queue-read, queue- write (qrqw) pram model [gmr94] permits concurrent reading and writing, but at a cost proportional to the number of readers/writers to a memory location in a given step. the qrqw model reflects the contention properties of most parallel machines more accurately than either the well-studied crcw or erew models: the crcw model does not adequately penalize algorithms with high contention to shared memory locations, while the erew model is too strict in its insistence on zero contention at each step. of primary practical and theoretical interest, then, is the design of fast and efficient qrqw algorithms for problems for which all previous algorithms either suffer from high contention, fail to be fast, or fail to be work-optimal.  this paper describes low-contention, fast, work-optimal qrqw pram algorithms for the fundamental problems of finding a random permutation, parallel hashing, load balancing, and sorting. there is no known fast, work-optimal erew algorithm known for finding a random permutation or for parallel hashing. for load balancing, we improve upon the erew result whenever the ratio of the maximum to the average load is not too large. we show that the logarithmic dependence of the qrqw running time on this ratio is inherent by providing a matching lower bound.  we demonstrate the performance advantage of a qrqw random permutation algorithm, compared with the popular erew algorithm, by implementing and running both algorithms on the maspar mp-1.  finally, we extend the work-time framework for the design of parallel algorithms to account for contention, and relate it to the qrqw pram model. we use our qrqw load balancing algorithm, as well as the qrqw linear compaction algorithm in [gmr94], to provide automatic tools for processor allocation---an issue that needs to be handled when translating an algorithm from its work- time presentation into the explicit pram description.  phillip b. gibbons yossi matias vijaya ramachandran