waashk/acm huggingface dataset:
existential second-order logic over strings  existential second-order logic (eso) and monadic second-order logic(mso) have attracted much interest in logic and computer science. eso is a much expressive logic over successor structures than mso. however, little was known about the relationship between msoand syntatic fragments of eso. we shed light on this issue by completely characterizing this relationship for the prefix classes of eso over strings, (i.e., finite successor structures). moreover, we determine the complexity of model checking over strings, for all eso-prefix classes. let eso(  q ) denote the prefix class containing all sentences of the shape  **r**q4 , where r is a list of predicate variables, q is a first-order predicate qualifier from the prefix set  q and  4 is quantifier-free. we show that eso(  *∀ * ) and eso(  *∀∀ ) are the maximal standard eso-prefix classes contained in mso, thus expressing only regular languages. we further prove the following dichotomy theorem: an eso prefix-class either expresses only regular languages (and is thus in mso), or it expresses some np-complete languages. we also give a precise characterization of those eso-prefix classes that are equivalent to mso over strings, and of the eso- prefix classes which are closed under complementation on strings.  thomas eiter georg gottlob yuri gurevich
the asymptotic complexity of merging networks  let m(m,n) be the minimum number of comparatorsneeded in a comparator network that merges m elements  x1≤x2≤ ≤xm and n elements  y1≤y2≤ ≤yn , where  n≥m . batcher's odd-even merge yields the following upper bound:  mm,n≤1 2m+nlog 2m+on; in particular,  mn,n≤nlog 2n+on.  we prove the following lower bound that matches the upper bound above asymptotically as  n≥m-&gt;∞: mm,n≥1 2m+nlog 2m-om; in particular,  mn,n≥nlog 2n-on.  our proof technique extends to give similarily tight lower bounds for the size of monotone boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.  peter bro miltersen mike paterson jun tarui
compatible tetrahedralizations  we give some special-case tetrahedralization algorithms. we first consider the problem of finding a tetrahedralization compatible with a fixed triangulation of the boundary of a polyhedron. we then adapt our solution to the related problem of compatibly tetrahedralizing the interior and exterior of a polyhedron. we also show how to tetrahedralize the region between nested convex polyhedra with o(n log n) tetrahedra and no steiner points.  marshall bern
the complexity of the equivalence problem for straight-line programs  we look at several classes of straight-line programs and show that the equivalence problem is either undecidable or computationally intractable for all but the trivial classes. for example, there is no algorithm to determine if an arbitrary program (with positive, negative, or zero integer inputs) using only constructs x 1, x x + y, x x/y (integer division) outputs 0 for all inputs. the result holds even if we consider only programs which compute total 0/1 - functions. for programs using constructs x 0, x c, x cx, x x/c, x x + y, x x y, skip l, if p(x) then skip l, and halt,1 the equivalence problem is decidable in [equation] time (λ is a fixed positive constant and n is the maximum of the sizes of the programs). the bound cannot be reduced to a polynomial in n unless p np. in fact, we prove the following rather surprising result: the equivalence problem for programs with one input/output variable and one intermediate variable using only constructs x x + y and x x/2 is np- hard. we also show the decidability of the equivalence problem for a certain class of programs and use this result to prove the following: let in be the set of natural numbers and f be any total one-to-one function from in onto in × in. (f is called a pair generator. such functions are useful in recursive function and computability theory.) then f cannot be computed by any program using only constructs x 0, x c, x x + y, x x y, x x * y, x x/y, skip l, if p(x) then skip l, and halt.  oscar h. ibarra brian s. leininger
a framework for defining logics  the edinburgh logical framework (lf) provides a means to define (or present) logics. it is based on a general treatment of syntax, rules, and proofs by means of a typed λ-calculus with dependent types. syntax is treated in a style similar to, but more general than, martin-lo"f's system of arities. the treatment of rules and proofs focuses on his notion of a judgment. logics are represented in lf via a new principle, the judgments as types principle, whereby each judgment is identified with the type of its proofs. this allows for a smooth treatment of discharge and variable occurence conditions and leads to a uniform treatment of rules and proofs whereby rules are viewed as proofs of higher-order judgments and proof checking is reduced to type checking. the practical benefit of our treatment of formal systems is that logic-independent tools, such as proof editors and proof checkers, can be constructed.  robert harper furio honsell gordon plotkin
an inverted taxonomy of sorting algorithms  an alternative taxonomy (to that of knuth and others) of sorting algorithms is proposed. it emerges naturally out of a top-down approach to the derivation of sorting algorithms. work done in automatic program synthesis has produced interesting results about sorting algorithms that suggest this approach. in particular, all sorts are divided into two categories: hardsplit/easyjoin and easysplit/hardjoin. quicksort and merge sort, respectively, are the canonical examples in these categories. insertion sort and selection sort are seen to be instances of merge sort and quicksort, respectively, and sinking sort and bubble sort are in-place versions of insertion sort and selection sort. such an organization introduces new insights into the connections and symmetries among sorting algorithms, and is based on a higher level, more abstract, and conceptually simple basis. it is proposed as an alternative way of understanding, describing, and teaching sorting algorithms.  susan m. merritt
logics for probabilistic programming (extended abstract)  this paper introduces a logic for probabilistic programming+ prob-dl (for probabilistic dynamic logic; see section 2 for a formal definition). this logic has "dynamic" modal operators in which programs appear, as in pratt's [1976] dynamic logic dl. however the programs of prob-dl contain constructs for probabilistic branching and looping whereas dl is restricted to nondeterministic programs. the formula {a} p of prob-dl denotes "with measure ≥ , formula p holds after executing program a."  in section 3, we show that prob-dl has a complete and consistent axiomatization, (using techniques derived from parikh's [1978] completeness proof for the propositional dynamic logic).  section 4 presents a probabilistic quantified boolean logic (prob-qbf) which also has applications to probabilistic programming.  john h. reif
concurrent dynamic logic  in this paper concurrent dynamic logic (cdl) is introduced as an extension of dynamic logic tailored toward handling concurrent programs. properties of cdl are discussed, both on the propositional and first-order level, and the extension is shown to possess most of the desirable properties of dl. its relationships with the μ-calculus, game logic, dl with recursive procedures, and ptime are further explored, revealing natural connections between concurrency, recursion, and alternation.  david peleg
the orbit problem is decidable  the "accessibility problem" for linear sequential machines (harrison [7]) is the problem of deciding whether there is an input x that sends such a machine from a given state q1 to a given state q2. harrison [7] showed that this problem is reducible to the "orbit problem:" given aεqn×n does there exist iεn such that aix y.* we will call this the "orbit problem" because the question can be rephrased as: does y belong to the orbit of x under a where the "orbit of x under a" is the set {aix: i 0,1,2,...}. (a0 is the identity matrix i.) in harrison's original problem the elements of a,x, and y were members of an arbitrary "computable" field. in view of the lack of structure of such fields, we study only the rationals. shank [13] proves that the orbit problem is decidable for the rational case when n 2. the current paper establishes that for the general rational case, the problem is decidable - and in fact polynomial-time decidable.  we wish to give a brief idea of our approach to the problem.  ravindran kannan richard j. lipton
primality testing using elliptic curves  we present a primality proving algorithm---a probablistic primality test that produces short certificates of primality on prime inputs. we prove that the test runs in expected polynomial time for all but a vanishingly small fraction of the primes. as a corollary, we obtain an algorithm for generating large certified primes with distribution statistically close to uniform. under the conjecture that the gap between consecutive primes is bounded by some polynomial in their size, the test is shown to run in expected polynomial time for all primes, yielding a las vegas primality test.  our test is based on a new methodology for applying group theory to the problem of prime certification, and the application of this methodology using groups generated by elliptic curves over finite fields.  we note that our methodology and methods have been subsequently used and improved upon, most notably in the primality proving algorithm of adleman and huang using hyperelliptic curves and in practical primality provers using elliptic curves.  shafi goldwasser joe kilian
property testing and its connection to learning and approximation  in this paper, we consider the question of determining whether a function f has property p or is ε-far from any function with property p. a property testing algorithm is given a sample of the value of f on instances drawn according to some distribution. in some cases, it is also allowed to query f on instances of its choice. we study this question for different properties and establish some connections to problems in learning theory and approximation.  in particular, we focus our attention on testing graph properties. given access to a graph g in the form of being able to query whether an edge exists or not between a pair of vertices, we devise algorithms to test whether the underlying graph has properties such as being bipartite, k-colorable, or having a p-clique (clique of density p with respect to the vertex set). our graph property testing algorithms are probabilistic and make assertions that are correct with high probability, while making a number of queries that is independent of the size of the graph. moreover, the property testing algorithms can be used to efficiently (i.e., in time linear in the number of vertices) construct partitions of the graph that correspond to the property being tested, if it holds for the input graph.  oded goldreich shari goldwasser dana ron
the membership problem in aperiodic transformation monoids  the problem of testing membership in aperiodic or "group-free" transformation monoids is the natural counterpart to the well-studied membership problem in permutation groups. the class a of all finite aperiodic monoids and the class g of all finite groups are two examples of varieties, the fundamental complexity units in terms of which finite monoids are classified. the collection of all varieties v forms an infinite lattice under the inclusion ordering, with the subfamily of varieties that are contained in a forming an infinite sublattice. for each v a, the associated problem memb(v) of testing membership in transformation monoids that belong to v, is considered. remarkably, the computational complexity of each such problem turns out to look familiar. moreover, only five possibilities occur as v ranges over the whole aperiodic sublattice: with one family of np-hard exceptions whose exact status is still unresolved, any such memb(v) is either pspace-complete, np- complete, p-complete or in ac0. these results thus uncover yet another surprisingly tight link between the theory of monoids and computational complexity theory.  m. beaudry p. mckenzie d. therien
the role of term symmetry in e-completion procedures  a major portion of the work and time involved in completing an incomplete set of reductions using an e-completion procedure such as the one described by knuth and bendix or its extension to associative-commutative equational theories as described by peterson and stickel is spent calculating critical pairs and subsequently testing them for confluence and coherence. a pruning technique which removes from consideration those critical pairs that represent redundant or superfluous information can make a marked difference in the run time and efficiency of an e-completion procedure to which it is applied. in this paper, a technique is proposed for removing critical pairs from consideration at various points before, during, or after their formation. this method is based on the property of term symmetry, which will be defined and explored with respect to e-unification and e-completion procedures. informally, term symmetry exists between two terms when one can be transformed into the other through variable renaming. by identifying and eliminating various forms of term symmetry which arise between syntactic structures such as, reductions, critical pairs, subterms, and unifiers, it is possible to derive an e-completion procedure that produces the same results without processing these symmetric redundancies.  ralph w. wilkerson blayne e. mayfield
neural network for partitionable variational inequalities often in recent times industries have asked mathematicians to determine their "true" utility functions directly from the available data about used resources and about the corresponding profits in order to optimize the latter with respect to the former. the possibility of determining the utility function directly from the data is very important because in this way the exact situation of the company is described. moreover, the biggest companies divide their investments into several activities. the optimization of their utility function can lead to problems that involve separable or partitionable functions. two-layered feed- forward neural networks are able to approximate any separable function while fitting the data mantaining the separable structure with the desired approximation error. thus the theory of partitionable variational inequalities can be used in order to find the optimum of the utility function, subject to some constraints. the presence of the partitionable structure is important because it simplifies the resolution algorithms and makes them more efficient. moreover, with stronger assumptions about the function, the above results can be generalized to a larger class of utility functions: one problem of dimension n can be split into n problems of dimension one. giulia rotondo
a fixpoint semantics for nondeterministic data flow  criteria for adequacy of a data flow semantics are discussed and kahn's successful semantics for functional (deterministic) data flow is reviewed. problems arising from nondeterminism are introduced and the paper's approach to overcoming them is introduced. the approach is based on generalizing the notion of input-output relation, essentially to a partially ordered multiset of input-output histories. the brock-ackerman anomalies concerning the input- output relation model of nondeterministic data flow are reviewed, and it is indicated how the proposed approach avoids them. a new anomaly is introduced to motivate the use of multisets. a formal theory of asynchronous processes is then developed. the main result is that the operation of forming a process from a network of component processes is associative. this result shows that the approach is not subject to anomalies such as that of brock and ackerman.  john staples v. l. nguyen
skinny and fleshy failures of relative completeness  the notion of relative completeness of logics of programs was delineated almost ten years ago, in particular by wand, cook and clarke. more recently, it has been felt that cook's notion hinges on a fragile balance between the semantics of a programming language and first-order expressiveness in structures. this fragility underlies the negative results about relative completeness.  the main negative result in this area, clarke's theorem, states that for a programming language with a sufficiently rich control structure there is no effective formalism for partial-correctness that is both sound and relatively complete (in the sense of cook). a conclusion often drawn from this result is that the non-existence of an adequate cook-complete formalization of the partial-correctness theory of a programming language is an indicator of the complexity of that language. our most novel result is that this is not always the case. we exhibit a programming language whose control structure is trivial, and yet for which no cook-complete hoare logic exists. the poverty of the language is precisely what permits certain structures to be expressive, structures which would not be expressive had the program constructs been used more freely.  we also discuss the failure of relative completeness for "fleshy" programming languages, of the kind of clarke's. we point out the relevance of the lambda calculus here, from which we derive the failure of cook-completeness for a programming language orthogonal (i.e. incomparable) to clarke's, whose control-structure complexity resides to a great extent in a modest use of generic procedures. a variant of the same idea also provides an alternative proof of non-relative-completeness for (a variant of) clarke's language.  finally, we note in passing a simple proof of wand's theorem, which states the failure of local completeness (without cook's expressiveness condition) for while programs. our proof uses rudimentary facts from mathematical logic. its interest, compared with previous proofs [wan78, bt82, apt81] is that it refers to a structure whose first-order theory is not decidable. moreover, our proof shows that the failure of local completeness for while programs is not necessarily due to a tension between first-order definability and definability by program looping, as one might have been tempted to conclude from previous proofs.  d. leivant t. fernando
continuations may be unreasonable  we show that two lambda calculus terms can be observationally congruent (i.e., agree in all contexts) but their continuation-passing transforms may not be. we also show that two terms may be congruent in all untyped contexts but fail to be congruent in a calculus with call/cc operators. hence, familiar reasoning about functional terms may be unsound if the terms use continuations explicitly or access them implicitly through new operators. we then examine one method of connecting terms with their continuized form, extending the work of meyer and wand [8].  albert meyer jon g. riecke
temporal abstract interpretation  we study the abstract interpretation of temporal calculi and logics in a general syntax, semantics and abstraction independent setting. this is applied to the @@@@-calculus, a generalization of the μ-calculus with new reversal and abstraction modalities as well as a new time-symmetric trace-based semantics. the more classical set-based semantics is shown to be an abstract interpretation of the trace-based semantics which leads to the understanding of model-checking and its application to data-flow analysis as incomplete temporal abstract interpretations. soundness and incompleteness of the abstractions are discussed. the sources of incompleteness, even for finite systems, are pointed out, which leads to the identification of relatively complete sublogics, a la ctl.  patrick cousot radhia cousot
size-time complexity of boolean networks for prefix computations  the prefix problem consists of computing all the products x0x1 … xj (j = 0, … , n \\- 1), given a sequence x = (x0, x1, … , xn- ;1) of elements in a semigroup. in this paper we completely characterize the size-time complexity of computing prefixes with boolean networks, which are synchronized interconnections of boolean gates and one-bit storage devices. this complexity crucially depends upon two properties of the underlying semigroup, which we call cycle-freedom (no cycle of length greater than one in the cayley graph of the semigroup), and memory-induciveness (arbitrarily long products of semigroup elements are true functions of all their factors). a nontrivial characterization is given of non-memory-inducive semigroups as those whose recurrent subsemigroup (formed by the elements with self-loops in the cayley graph) is the direct product of a left-zero semigroup and a right-zero semigroup. denoting by s and t size and computation time, respectively, we have s = ((n/t)log(& lt;italic>n/t)) for memory- inducive non-cycle-free semigroups, and s = (n/t) for all other semigroups. we have t ε [ (log n), (n)] for all semigroups, with the exception of those whose recurrent subsemigroup is a right-zero semigroup, for which t ε [ (1), (n)]. the preceding results are also extended to the vlsi model of computation. area- time optimal circuits are obtained for both boundary and nonboundary i/o protocols.  g. bilardi f. p. preparata
generalized selection and ranking (preliminary version)  selection in a set requires time linear in the size of the set when there are no a priori constraints on the total orders possible for the set. constraints often come for free, however, with sets which arise in applications. linear time selection [bl] can be suboptimal for such problems. we therefore generalize the well known selection problem to admit constraints on the input sets, with a view toward settling the complexity issues which arise. the generalization also applies to the other quantile problems of ranking a given element in the input set and verification of the claim that a given element has a specified rank.  greg n. frederickson donald b. johnson
p-uniform circuit complexity  much complexity-theoretic work on parallelism has focused on the class nc, which is defined in terms of logspace-uniform circuits. yet p-uniform circuit complexity is in some ways a more natural setting for studying feasible parallelism. in this paper, p-uniform nc (punc) is characterized in terms of space-bounded auxpdas and alternating turing machines with bounded access to the input. the notions of general-purpose and special-purpose computation are considered, and a general- purpose parallel computer for punc is presented. it is also shown that nc = punc if all tally languages in p are in nc; this implies that the nc = punc question and the nc = p question are both instances of the aspace(s(n)) = aspace,time(s(n), &amp;l; t;italic>s(n)&amp;l; t;italic>o(1)) question. as a corollary, it follows that nc = punc implies pspace = dtime(2n o(1)).  eric w. allender
an nc parallel 3d convex hull algorithm  in this paper we present an ologn time parallel algorithm for computing the convex hullof n points in r3. this algorithm uses on1+a processors on a crew pram, for any constant 0 <δ ≤ 1\. so far, all adequately documented parallel algorithmsproposed for this problem use time at least olog  2  . in addition, the algorithm presented here is thefirst parallel algorithm for the three-dimensional convex hull problemthat is not based on the serial divide- and-conquer algorithm ofpreparata and hong, whose crucial operation is the merging of the convexhulls of two linearly separated point sets. the contributions of thispaper are therefore (i) an ologn time parallel algorithm for the three-dimensionalconvex hull problem, and (ii) a parallel algorithm for this problemthat does not follow the traditional divide-and- conquer paradigm.  nancy m. amato franco p. preparata