waashk/acm huggingface dataset:
nondeterministic linear tasks may require substantially nonlinear deterministic time in the case of sublinear work space  log-size parabolic clique problem is a version of clique problem solvable in linear time by a log-space nondeterministic turning machine. however, no deterministic machine (in a very general sense of this term) with sequential- access read-only input tape and work space n solves log-size parabolic clique problem within time n1 + τ if + 2τ < 1/2.  yuri gurevich saharon shelah
computational complexity of combinatorial surfaces  we investigate the computational problems associated with combinatorial surfaces. specifically, we present an algorithm (based on the brahana-dehn- heegaard approach) for transforming the polygonal schema of a closed triangulated surface into its canonical form in  (n log n) time, where n is the total number of vertices, edges and faces. we also give an  (n log n \\+ gn) algorithm for constructing canonical generators of the fundamental group of a surface of genus g. this is useful in constructing homeomorphisms between combinatorial surfaces.  gert vegter chee k. yap
unique decomposability of shuffled strings  a string x is said to be decomposed into strings yl,y2 ,...,yn if x is in y1 @@@@ y2 @@@@ ... @@@@ yn where @@@@ is the shuffle operator. we consider the problem of decomposing x into yl< /subscrpt>,y2,...,yn~~ such that yl,y2&amp;l; t;/subscrpt>,...,yn belong to predetermined languages l1,l2 ,...,ln, respectively. conditions under which such a decomposition is unique are presented as well as uniquely decomposable l1,l2&amp;l; t;/subscrpt>,...,ln which are of practical significance from the viewpoint of time-multiplexed communication.  kazuo iwama
independence results in computer science? (preliminary version)  although there has been considerable additional work discussing limitations of formal proof techniques for computer science ([yo-73&77], [har-76], [har&amp;ho-77;], [haj-77&79], [go-79]), these papers show only very general consequences of incompleteness: the stated results hold for all sufficiently powerful formal systems for computer science. only the work of o'donnell and of lipton directly addresses the question of just how powerful formal axioms for computer science should be, and these two authors make rather radically different suggestions.  we investigate this latter question: how powerful should a set of axioms be if it is to be adequate for computer science? in particular, in this paper we investigate the adequacy of the system of [li-78] as a formal system for computer science.  deborah joseph paul young
production trees: a compact representation of parsed programs  abstract syntax trees were devised as a compact alternative to parse trees, because parse trees are known to require excessive amounts of storage to represent parsed programs. however, the savings that abstract syntax trees actually achieve have never been precisely described because the necessary analysis has been missing. without it, one can only measure particular cases that may not adequately represent all the possible behaviors.  we introduce a data structure, production trees, that are more compact than either abstract syntax trees or parse trees. further, we develop the necessary analysis to characterize the storage requirements of parse trees, abstract syntax trees, and production trees and relate the size of all three to the size of the program's text. the analysis yields the parameters needed to characterize these storage behaviors over their entire range. we flesh out the analysis by measuring these parameters for a sample of "c" programs. for these programs, production trees were from 1/15 to 1/23 the size of the corresponding parse tree, l/2.7 the size of a (minimal) abstract syntax tree, and averaged only 2.83 times the size of the program text.  vance e. waddle
type inference in the presence of type abstraction  a number of recent programming language designs incorporate a type checking system based on the girard-reynolds polymorphic λ-calculus. this allows the construction of general purpose, reusable software without sacrificing compile-time type checking. a major factor constraining the implementation of these languages is the difficulty of automatically inferring the lengthy type information that is otherwise required if full use is made of these languages. there is no known algorithm to solve any natural and fully general formulation of this "type inference" problem. one very reasonable formulation of the problem is known to be undecidable.  here we define a restricted version of the type inference problem and present an efficient algorithm for its solution. we argue that the restriction is sufficiently weak to be unobtrusive in practice.  h.-j. boehm
almost optimal set covers in finite vc-dimension: (preliminary version)  we give a deterministic polynomial time method for finding a set cover in a set system (x,r) of vc-dimension d such that the size of our cover is at most a factor of o(dlog(dc)) from the optimal size, c. for constant vc-dimension set systems, which are common in computational geometry, our method gives an o(logc) approximation factor. this improves the previous (log |x|) bound of the greedy method and beats recent complexity-theoretic lower bounds for set covers (which don't make any assumptions about vc-dimension). we give several applications of our method to computational geometry, and we show that in some cases, such as those that arise in 3-d polytope approximation and 2-d disc covering, we can quickly find o(c)-sized covers.  herve bronnimann michael t. goodrich
dynamic typing in a statically typed language  statically typed programming languages allow earlier errorchecking, better enforcement of diciplined programming styles, and thegeneration of more efficient object code than languages where all typeconsistency checks are performed at run time. however, even instatically typed languages, there is often the need to deal with datawhose type cannot be determined at compile time. to handlesuch situations safely, we propose to add a typedynamic whose values are pairs of a valuev and a type tagt where vhas the type denoted by t. instances ofdynamic are built with an explicittagging construct and inspected with a type safetypecase construct.  this paper explores the syntax, operational semantics, and denotational semantics of a simple language that includes the typedynamic. we give examples of howdynamically typed values can be used in programming. then we discuss anoperational semantics for our language and obtain a soundness theorem. wepresent two formulations of the denotational semantics of this languageand relate them to the operational semantics. finally, we consider theimplications of polymorphism and some implementation issues.  martín abadi luca cardelli benjamin pierce gordon plotkin
the unwinding number from the oxford english dictionary we find that _to unwind_ can mean "to become free from a convoluted state". further down we find the quotation "the solution of all knots, and unwinding of all intricacies", from h. brooke (the fool of quality, 1809). while we do not promise that the unwinding number, defined below, will solve _all_ intricacies, we do show that it may help for quite a few problems.our original interest in this area came from a problem in which an early version of derive was computing the wrong answer when simplifying sin(sin-1 _z_), which should always be just _z._ for _z_ > 1, derive was getting -_z_ as the answer. this bug has of course long since been fixed.what was happening was that in order to improve internal efficiency, all the inverse trig functions were represented as arctangents. consulting an elementary book of tables, one finds the identitysin-1 _z_ = tan-1 (_z_/ 1 - _z_2). (1)in the same vein, one finds thatsin(tan-1 _w_) = _w_/ 1 + _w_2. (2)substituting equations (1) and (2) into sin(sin-1 _z_) and simplifying, we get_z_/ 1 - _z_2 1/ 1/1 - _z_2, (3)which derive quite properly refused to simplify to _z,_ because this is _not_ always equal to _z_ (see [2]).the fix in this case was to replace equation (2) withsin(tan-1 _w_) = _w_ 1/1 + _w_2. (4)which differs from the original only on the branch cut. see [7] for more discussion. this change allows the simplification of sin(sin-1 _z_) to _z._ verifying that this approach worked, and indeed trying to understand the problem to begin with, led us to attempt various definitions of a 'branch function'. this introductory problem turned out to be the tip of an iceberg of problems connected with using the principal branch of multivalued elementary functions. robert m. corless david j. jeffrey
a forward move algorithm for ll and lr parsers  a wide variety of algorithms have been suggested for the repair of syntactic errors in a computer program. since there is usually more than one possible repair for any syntax error, many algorithms employ a cost function to guide the the repair, and some [1,3,4,6], guarantee that the repair chosen will be least-cost, according to some definition. (the others, although guided by costs, do not guarantee least-cost in all cases.) fischer et al. [4,6,7] define a "locally least-cost" repair using insertions and deletions, and provide algorithms for ll and lr parsers. a locally least-cost repair is a least-cost sequence of deletions and insertions such that one more symbol in the original string will be accepted by the parser. backhouse [2,3] uses a similar definition. in both cases, the repair algorithms operate by examining a single symbol in the input at any time.  jon mauney charles n. fischer
at2 bounds for a class of vlsi problems and string matching  we present a class of boolean functions which have regional mappings, a generalization of the transitivity property defined in [12]. we prove that all transitive problems have regional mappings, as do a variety of interesting computational problems such as merging two sorted lists of arbitrary length, generalized integer multiplication and matrix-vector products. we present a general area-time lower bound for vlsi implementations of problems with regional mappings and confirm that the lower bound matches the previously known bound for transitive problems. for generalized integer multiplication, we present a custom vlsi implementation which provides a matching upper bound. the results improve at2 bounds on a number of open problems.  in related work, we consider the problem of finding occurrences of a p-bit pattern in an n-bit text string. we show that every chip capable of solving this string matching problem requires at2 = (pn). a custom vlsi design, using an idea similar to that used for generalized integer multiplication, provides a matching upper bound when n is polynomial in p.  micah adler john byers
the minimum consistent dfa problem cannot be approximated within and polynomial  the minimum consistent dfa problem is that of finding a dfa with as few states as possible that is consistent with a given sample (a finite collection of words, each labeled as to whether the dfa found should accept or reject). assuming that p np, it is shown that for any constant k, no polynomial time algorithm can be guaranteed to find a consistent dfa of size optk, where opt is the size of a smallest dfa consistent with the sample. this result holds even if the alphabet is of constant size two, and if the algorithm is allowed to produce an nfa, a regular grammar, or a regular expression that is consistent with the sample. similar hardness results are described for the problem of funding small consistent linear grammars.  l. pitt m. k. warmuth
an efficient approach to removing geometric degeneracies  our aim is to perturb the input so that an algorithm designed under the hypothesis of input non-degeneracy can execute on arbitrary instances. the deterministic scheme of [emca] was the first efficient method and was applied to two important predicates. here it is extended in a consistent manner to another two common predicates, thus making it valid for most algorithms in computational geometry. it is shown that this scheme incurs no extra algebraic complexity over the original algorithm while it increases the bit complexity by a factor roughly proportional to the dimension of the geometric space. the second contribution of this paper is a variant scheme for a restricted class of algorithms that is asymptotically optimal with respect to the algebraic as well as the bit complexity. both methods are simple to implement and require no symbolic computation. they also conform to certain criteria ensuring that the solution to the original input can be restored from the output on the perturbed input. this is immediate when the input to solution mapping obeys a continuity property and requires some case-specific work otherwise. finally we discuss extensions and limitations to our approach.  ioannis emiris john canny
ham-sandwich cuts in  rd  lo and steiger resolved the complexity question for computing a planar ham- sandwich cut by giving an optimal linear-time algorithm. we show how to generalize the ideas to every fixed dimension d > 2 by describing an algorithm that computes a ham-sandwich cut in rd in time _o(nd\\--1--a(d&amp;l; t;/italic>)), for some a(d) > 0 (going to zero as d increases). for d = 3,4, the running time is almost proportional to ed ;\\--1(n;n/2), where d(k;n) denotes the maximal number of k-sets over sets of n points in rd, and with the current best bounds, we get o(n< /italic>3/2 log2 n/log n) running time for d = 3 and o(n8/3+ε) for d=4. we also give a linear time algorithm for three dimensional ham-sandwich cuts when the three sets are suitably separated.  jiri matousek chi-yuan lo william steiger
dehn-sommerville relations, upper bound theorem, and levels in arrangements  in this note, we generalize theh-vector for simple, bounded convexpolytopes [14] to the h-matrix forsimple, bounded k-complexes. weobserve that the h-matrix isinvariant with respect to the defining linear function, and that thedehn-sommerville relations and mcmullen's upper bound theorem [13] forconvex polytopes follow from the invariance ofthe 0-th row and column ofthis matrix. the invariance of the other entries in theh-matrix should, perhaps, beinvestigated more. one new consequence is that, given any non- degeneratelinear function z, the number oflocal z-minima on thelth level of anyd-dimensional arrangement is boundedby & lt;stk>l+d-1d-1&amp;l; t;rp post="par">, with exact equality if thel-th level is bounded andsimple.  ketan mulmuley
solvability by radicals is in polynomial time  every high school student knows how to express the roots of a quadratic equation in terms of radicals; what is less well-known is that this solution was found by the babylonians a millenia and a half before christ [ne]. three thousand years elapsed before european mathematicians determined how to express the roots of cubic and quartic equations in terms of radicals, and there they stopped, for their techniques did not extend. lagrange published a treatise which discussed why the methods that worked for polynomials of degree less than five did not work for quintic polynomials [lag],  they require double exponential time. through the years other mathematicians developed alternate algorithms all of which, however, remained exponential. a major impasse was the problem of factoring polynomials, for until the recent breakthrough of lenstra, lenstra, and lovasz [l3], all earlier algorithms had exponential running time. their algorithm, which factors polynomials over the rationals in polynomial time, gave rise to a hope that some of the classical questions of galois theory might have polynomial time solutions.  galois transformed the question of solvability by radicals from a problem concerning fields to a problem about groups. what we do is to change the inquiry into several problems concerning the solvability of certain primitive groups.  susan landau gary lee miller
on the degree of polynomials that approximate symmetric boolean functions (preliminary version)  in this paper, we provide matching (up to a constant factor) upper and lower bounds on the degree of polynomials that represent symmetric boolean functions with an error 1/3. let Γ(f)=min{|2k\\-- ;n+1|:fk & lt;italic>fk\\+ 1 and 0 ≤ k ≤ n \\-- 1} where fi is the value of f on inputs with exactly i 1's. we prove that the minimum degree over all the approximating polynomials of f is ((n(n-Γ( f))).5). we apply the techniques and tools from approximation theory to derive this result.  ramamohan paturi
the future of computational complexity theory: part ii this is the final part of a 2-part column on the future of computational complexity theory. the grounds rules were that the contributors had no restrictions (except a 1-page limit). for readers interested in more formal reports, in addition to the two urls mentioned in the previous issue (ftp://ftp.cs.washington.edu/tr/1996/o3/uw-cse-96-o3-o3.ps.z and http://theory.lcs.mit.edu/-oded/toc-sp.html) i would also point to the recent "strategic directions" report (http://geisel.csl.uiuc.edu/-loui/complete.html).coming during the next few issues: the search for the perfect theory journal; thomas jefferson exposed as a theoretical computer scientist; and mitsunori ogihara's survey of dna-based computation. (the "lance fortnow in a clown suit" article promised in the previous column actually ran stand-alone last issue due to scheduling; it probably is still available at a library near you!) finally, some recent work by edith hemaspaandra, harald hempel, and myself, and of buhrman and fortnow, partially resolves one of the open questions from complexity theory column 11. e. allender j. feigenbaum j. goldsmith t. pitassi s. rudich
a closer look at iteration: the self stabilizing capability of loops  let p be an iterative program on domain d, with state s. a close look at the structure of the loop invariant of p reveals that p has a desirable self stabilizing property: if during the computation, an error causes the state to take a contaminated value s', then, under some conditions, it is possible to recover from this contamination without knowing any previous correct state. this feature contrasts with the classical error recovery mechanisms which equate error recovery with the retrieval of a previously saved correct state, and the backtracking of the computation.  ali mili
algebraic laws for nondeterminism and concurrency  since a nondeterministic and concurrent program may, in general, communicate repeatedly with its environment, its meaning cannot be presented naturally as an input/output function (as is often done in the denotational approach to semantics). in this paper, an alternative is put forth. first, a definition is given of what it is for two programs or program parts to be equivalent for all observers; then two program parts are said to be observation congruent if they are, in all program contexts, equivalent. the behavior of a program part, that is, its meaning, is defined to be its observation congruence class.  the paper demonstrates, for a sequence of simple languages expressing finite (terminating) behaviors, that in each case observation congruence can be axiomatized algebraically. moreover, with the addition of recursion and another simple extension, the algebraic language described here becomes a calculus for writing and specifying concurrent programs and for proving their properties.  matthew hennessy robin milner
conditions for exact resultants using the dixon formulation  a structural criteria on polynomial systems is developed for which the generalized dixon formulation of multivariate resultants defined by kapur, saxena and yang (1994) computes the resultant exactly. the concept of a dixon- exact support (the set of exponent vectors of terms appearing in a polynomial system) is introduced so that the dixon formulation produces the exact resultant for generic unmixed polynomial systems whose support is dixon-exact. a geometric operation, called direct-sum, on the supports is defined that preserves the property of supports being dixon-exact. generic n-degree systems and multigraded systems are shown to be a special case of generic unmixed polynomial systems whose support is dixon-exact. using a scaling techniques discussed by kapur and saxena (1997), a wide class of polynomial systems can be identified for which the dixon formulation produces exact resultants. this analysis can be used to classify terms appearing in the convex hull (also called the newton polytope) of the support of a polynomial system that can cause extraneous factors in the computation of a projection operation by the generalized dixon formulation. for the bivariate case, a complete analysis of the terms corresponding to the exponent vectors in the newton polytope of the support of a polynomial system is given vis a vis their role in producing extraneous factors in a projection operator. a necessary and sufficient condition is developed for a support to be dixon-exact. such an analysis is likely to give insights for the general case of elimination of arbitrarily many variables.  arthur d. chtcherba deepak kapur
a faster strongly polynomial minimum cost flow algorithm  we present a new strongly polynomial algorithm for the minimum cost flow problem, based on a refinement of the edmonds-karp scaling technique. our algorithm solves the uncapacitated minimum cost flow problem as a sequence of (n log n) shortest path problems on networks with n nodes and m arcs and runs in (n log n(m + n log n)) steps. using a standard transformation, this approach yields an (m log n (m + n log n)) algorithm for the capacitated minimum cost flow problem. this algorithm improves the best previous strongly polynomial algorithm due to galil and tardos, by a factor of m/n. our algorithm is even more efficient if the number of arcs with finite upper bounds, say m', is much less than m. in this case, the number of shortest path problems solved is ((m + n) log n).  james orlin
programmed grammars with multi-production core and their applications (abstract)  two-dimensional programmed grammars was introduced in [1]. in this paper, programmed grammars with multi-production core are defined. various properties of this type of grammar are studied and illustrated by examples. in addition, the time and space complexity analyses are also investigated with illustrative examples. applications to the generation of simple three-dimensional objects are also studied. the main advantages are: (1) this type of grammar provides a concise and a convenient way to generate simple three-dimensional objects in a structured fashion; (2) the derivation process can be clearly envisioned. furthermore, this type of grammar also has useful applications in region filling, robotics, pattern recognition, pictorial information systems, visual languages and artificial intelligence.  edward t. lee shangyong zhu
constructive deterministic pram simulation on a mesh-connected computer  we present a constructive deterministic simulation of a pram with n processors and m = n α shared variables, 1 < α ≤ 2, on an n-node mesh-connected computer where each node hosts a processor and a memory module. at the core of the simulation is a hierarchical memory organization scheme (hmos) that governs the distribution of the pram variables (each replicated into a number of copies) among the modules. the hmos consists of a cascade of explicit bipartite graphs whose expansion properties, combined with suitable access and routing protocols, yield a time performance that, for α < 3/2, is close to the w< rad>n bound imposed by the network's diameter, and that, for α ≥ 3/2, is a function of α never exceeding  on5/8&amp;l; t;/rm> .  andrea pietracaprina geppino pucci jop f. sibeyn