waashk/acm huggingface dataset:
on -automata and temporal logic  we study here the use of different representation for infinitary regular languages in extended temporal logic. we focus on three different kinds of acceptance conditions for finite automata on infinite words, due to buchi, streett, and emerson and lei (el), and we study their computational properties. our finding is that buchi, streett, and el automata span a spectrum of succinctness. el automata are exponentially more succinct than buchi automata, and complementation of el automata is doubly exponential. streett automata are of intermediate complexity. while translating from streett automata to buchi automata involves an exponential blow-up, so does the translation from el automata to streett automata. furthermore, even though streett automata are exponentially more succinct than buchi automata, complementation of streett automata is only exponential. as a result, we show that the decision problem for etlel, where temporal connectives are represented by el automata, is expspace-complete, and the decision problem for etl s , where temporal connectives are represented by streett automata, is pspace- complete.  s. safra m. y. vardi
the complexity of propositional linear temporal logics  the complexity of satisfiability and determination of truth in a particular finite structure are considered for different propositional linear temporal logics. it is shown that these problems are np-complete for the logic with f and are pspace- complete for the logics with f, x, with u, with u, s, x operators and for the extended logic with regular operators given by wolper.  a. p. sistla e. m. clarke
strongly equivalent logic programs  a logic program p1 is said to be equivalent to a logic program p2 in the sense of the answer set semantics if p and p2 have the same answer sets. we are interested in the following stronger condition: for every logic program, p, p1, ∪ p has the same answer sets as p2 ∪ p. the study of strong equivalence is important, because we learn from it how one can simplify a part of a logic program without looking at the rest of it. the main theorem shows that the verification of strong equivalence can be accomplished by cheching the equivalence of formulas in a monotonic logic, called the logic of here-and- there, which is intermediate between classical logic and intuitionistic logic.
fooling a two-way automaton or one pushdown store is better than one counter for two way machines (preliminary version)  we define a language l and show that is cannot be recognized by any two way deterministic counter machine. it is done by fooling any given such machine; i.e. showing that if it accepts l' @@@@ l, then l'-l @@@@ . for this purpose, an argument stronger than the well known crossing sequence argument needs to be introduced. since l is accepted by a two-way deterministic pushdown automaton, we consequently show that one pushdown stack is more powerful than one counter for deterministic two-way machines.  pavol d zvi galil
a randomized art-gallery algorithm for sensor placement  this paper descirbes a placement strategy to compute a set of "good" locations where visual sensing will be most effective. throughout this paper it is assumed that a {\em polygonal 2-d map} of a workspace is given as input. this polygonal map --- also known as a {\em floor plan} of {\em layout} --- is used to compute a set of locations where expensive sensing tasks (such as 3-d image acquisition) could be executed. a map-building robot, for example, can visit these locations in order to build a full 3-d model of the workspace.  the sensor placement strategy relies on a randomized algorithm that solves a variant of the {\em art-gallery problem}-\cite{oro87, she92, urr97} : find the minimum set of guards inside a polygonal workspace from which the entire workspace boundary is visibe. to better take into account the limitations of physical sensors, the algorithm computes a set of guards that satisfies incidence and range constraints. although the computed set of guards is not guaranteed to have minimum size, the algorithm does compute with high probability a set whose size is at most a factor $\big0{ (n + h) \cot \log(c \ (n + h) )$ from the optimal size$c$, where $n$ is the number of edges in the input polygonal map and $n$ the number of obstacles in its interior (holes).  h. gonzalez-banos
denotational abstract interpretation of logic programs  logic- programming languages are based on a principle of separation "logic" and "control.". this means that they can be given simple model-theoretic semantics without regard to any particular execution mechanism (or proof procedure, viewing execution as theorem proving). although the separation is desirable from a semantical point of view, it makes sound, efficient implementation of logic-programming languages difficult. the lack of "control information" in programs calls for complex data-flow analysis techniques to guide execution. since data-flow analysis furthermore finds extensive use in error-finding and transformation tools, there is a need for a simple and powerful theory of data-flow analysis of logic programs.  this paper offers such a theory, based on f. nielson's extension of p. cousot and r. cousot's abstract interpretation. we present a denotational definition of the semantics of definite logic programs. this definition is of interest in its own right because of its compactness. stepwise we develop the definition into a generic data-flow analysis that encompasses a large class of data-flow analyses based on the sld execution model. we exemplify one instance of the definition by developing a provably correct groundness analysis to predict how variables may be bound to ground terms during execution. we also discuss implementation issues and related work.  kim marriott harald søndergaard neil d. jones
new lower bounds for parallel computation  lower bounds are proven on the parallel-time complexity of several basic functions on the most powerful concurrent-read concurrent-write pram with unlimited shared memory and unlimited power of individual processors (denoted by priority(∞)):  it is proved that with a number of processors polynomial in n, (log n) time is needed for addition, multiplication or bitwise or of n numbers, when each number has n' bits. hence even the bit complexity (i.e., the time complexity as a function of the total number of bits in the input) is logarithmic in this case. this improves a beautiful result of meyer auf der heide and wigderson [22]. they proved a log n lower bound using ramsey-type techniques. using ramsey theory, it is possible to get an upper bound on the number of bits in the inputs used. however, for the case of polynomially many processors, this upper bound is more than a polynomial in n.  an (log n) lower bound is given for priority(∞) with no(1) processors on a function with inputs from {0, 1}, namely for the function (x1, … , xn,) = nl\\- 1 xl ai where a is fixed and xi ε {0, 1}.  finally, by a new efficient simulation of priority(∞) by unbounded fan-in circuits, that with less than exponential number of processors, it is proven a priority(∞) cannot compute parity in constant time, and with no(1) processors (@@@@log n) time is needed. the simulation technique is of independent interest since it can serve as a general tool to translate circuit lower bounds into pram lower bounds.  further, the lower bounds in (1) and (2) remain valid for probabilistic or nondeterministic concurrent- read concurrent-write prams.  ming li yaacov yesha
the polynomial-time hierarchy and sparse oracles  questions about the polynomial-time hierarchy are studied. in particular, the questions, "does the polynomial-time hierarchy collapse?" and "is the union of the hierarchy equal to pspace?" are considered, along with others comparing the union of the hierarchy with certain probabilistic classes. in each case it is shown that the answer is "yes" if and only if for every sparse set s, the answer is "yes" when the classes are relativized to s if and only if there exists a sparse set s such that the answer is "yes" when the classes are relativized to s. thus, in each case the question is answered if it is answered for any arbitrary sparse oracle set.  long and selman first proved that the polynomial-time hierarchy collapses if and only if for every sparse set s, the hierarchy relative to s collapses. this result is re-proved here by a different technique.  jose l. balcázar ronald v. book uwe schöning
finite state verifiers ii: zero knowledge  the zero knowledge properties of interactive proof systems (ipss) are studied in the case that the verifier is a 2-way probabilistic finite state automaton (2pfa). the following results are proved:  (1) there is a language l such that l has an ips with 2pfa verifiers but l has no zero knowledge ips with 2pfa verifiers.  (2) consider the class of 2pfa's that are sweeping and that halt in polynomial expected time. there is a language l such that l has a zero knowledge ips with respect to this class of verifiers, and l cannot be recognized by any verifier in the class on its own.  a new definition of zero knowledge is introduced. this definition captures a concept of "zero knowledge" for ipss that are used for language recognition.  cynthia dwork larry stockmeyer
counting problems in genomics  the past decade has seen the emergence of an overwhelming amount of genome data and the desperate need to catalog, organize, analyze, and interpret it. this "tsunami of information", as gene myers, jr. of celera genomics calls it, is continuously being fed by the masses of raw genome data erupting from the successful genome projects of various organisms, especially humans. it has forced the creation of the interdisciplinary field of genomics --- the union between computer science and biology, in which programmers acknowledge biology as an information science and biologists admit that there is too much data for them to fairly and efficiently sift through alone.  andrea christoforou
verifying secrets and relative secrecy  systems that authenticate a user based on a shared secret (such as a password or pin) normally allow anyone to query whether the secret is a given value. for example, an atm machine allows one to ask whether a string is the secret pin of a (lost or stolen) atm card. yet such queries are prohibited in any model whose programs satisfy an information-flow property like noninterference. but there is complexity-based justification for allowing these queries. a type system is given that provides the access control needed to prove that no well-typed program can leak secrets in polynomial time, or even leak them with nonnegligible probability if secrets are of sufficient length and randomly chosen. however, there are well-typed deterministic programs in a synchronous concurrent model capable of leaking secrets in linear time.  dennis volpano geoffrey smith
implementation of the typed call-by-value -calculus using a stack of regions  we present a translation scheme for the polymorphically typed call- by-value λ-calculus. all runtime values, including function closures, are put into regions. the store consists of a stack of regions. region inference and effect inference are used to infer where regions can be allocated and de-allocated. recursive functions are handled using a limited form of polymorphic recursion. the translation is proved correct with respect to a store semantics, which models as a region- based run-time system. experimental results suggest that regions tend to be small, that region allocation is frequent and that overall memory demands are usually modest, even without garbage collection.  mads tofte jean- pierre talpin
load balancing requires (log*n) expected time  in order to obtain very fast parallel algorithms, it is almost always necessary to have some sort of load balancing procedure, so that processors which have finished their required tasks can help processors which have not. if the overloaded processors are not helped, then the expected time of the entire algorithm suffers. in general, we would like to distribute the remaining work as evenly as possible among the processors, or more formally, given at most n independent tasks distributed in an arbitrary way among n processors, we would like to redistribute the tasks so that each processor contains o(1) tasks. we show here that even on the strongest randomized crcw pram model, for a simple random distribution tasks load balancing requires (log* n) expected time. gil, matias, and vishkin [9] give an o(log* n) expected time randomized algorithm which solves the load balancing problem in the worst case, so the lower bound is tight.  by reduction we show that both padded sort [12], and linear approximate compaction [13] require (log* n) expected time. we note that our basic technique is one of the few parallel lower bound techniques known which only require 0/1 inputs. we also note that the bounds given in this paper do not place any restriction on the instruction set of the machine, the amount of information which can be stored in a memory cell, or on the number of memory cells.  philip d. mackenzie
logics with counting and local properties  the expressive power of first-order logic over finite structures is limited in two ways: it lacks a recursion mechanism, and it cannot count. overcoming the first limitation has been a subject of extensive study. a number of fixpoint logics have been introduced. and shown to be subsumed by an infinitary logic lw ;∞w . this logic is easier to analyze than fixpoint logics, and it still lacks counting power, as it has a 0-1 law. on the counting side, there is no analog of ~~lw∞w . there are a number of logics with counting power, usually introduced via generalized quantifiers. most known expressivityy bounds are based on the fact that counting extensions of first-order logic preserve the locality properties. this article has three main goals. first, we introduce a new logic l*& lt;/sup>∞w&amp;l; t;/inf> (c) that plays the same role for counting aslw&amp;l; t;/sup>∞w< ;/inf> does for recursion---it subsumes a number of extensions of first-order logic with counting, and has nice properties that make it easy to study. second, we give simple direct proof thatlw< /g>∞w (c) expresses only local properties: those that depend on the properties of small neighborhoods, but cannot grasp a structure as a whole. this is a general way of saying that a logic lacks a recursion mechanism. third, we consider a finer analysis of locality of counting logics. in particular, we address the question of how local a logic is, that is, how big are those neighborhoods that local properties depend on. we get a uniform answer for a variety of logics between first-order and  l*∞& lt;g>w (c). this is done by introducing a new form of locality that captures the tightest condition that the duplicator needs to maintain in order to win a game. we also use this technique to give bounds on outputs of  l*& lt;/sup>∞w&amp;l; t;/inf> (c)-definable queries.  leonid libkin
e -approximations with minimum packing constraint violation (extended abstract)  we present efficient new randomized and deterministic methods for transforming optimal solutions for a type of relaxed integer linear program into provably good solutions for the corresponding np-hard discrete optimization problem. without any constraint violation, the ε-approximation problem for many problems of this type is itself np-hard. our methods provide polynomial-time ε-approximations while attempting to minimize the packing constraint violation.  our methods lead to the first known approximation algorithms with provable performance guarantees for the s-median problem, the tree prunning problem, and the generalized assignment problem. these important problems have numerous applications to data compression, vector quantization, memory-based learning, computer graphics, image processing, clustering, regression, network location, scheduling, and communication. we provide evidence via reductions that our approximation algorithms are nearly optimal in terms of the packing constraint violation. we also discuss some recent applications of our techniques to scheduling problems.  jyh-han lin jeffrey scott vitter
comparison of two-dimensional fft methods on the hypercube  complex two-dimensional ffts up to size 256 x 256 points are implemented on the intel ipsc/system 286 hypercube with emphasis on comparing the effects of data mapping, data transposition or communication needs, and the use of distributed ffts. two new implementations of the 2d-fft include the local- distributed method which performs local ffts in one direction followed by distributed ffts in the other direction, and a vector-radix implementation that is derived from decimating the dft in two-dimensions instead of one. in addition, the transpose-split method involving local ffts in both directions with an intervening matrix transposition and the block 2d-fft involving distributed fft butterflies in both directions are implemented and compared with the other two methods. timing results show that on the intel ipsc/system 286, there is hardly any difference between the methods, with the only differences arising from the efficiency or inefficiency of communication. since the intel cannot overlap communication and computation, this forces the user to buffer data. in some of the methods, this causes processor blocking during communication. issues of vectorization, communication strategies, data storage and buffering requirements are investigated. a model is given that compares vectorization and communication complexity. while timing results show that the transpose- split method is in general slightly faster, our model shows that the block method and vector-radix method have the potential to be faster if the communication difficulties were taken care of. therefore if communication could be "hidden" within computation, the latter two methods can become useful with the block method vectorizing the best and the vector-radix method having 25% fewer multiplications than row-column 2d-fft methods. finally the local-distributed method is a good hybrid method requiring no transposing and can be useful in certain circumstances. this paper provides some general guidelines in evaluating parallel distributed 2d-fft implementations and concludes that while different methods may be best suited for different systems, better implementation techniques as well as faster algorithms still perform better when communication become more efficient.  c. y. chu
on the distribution of independent formulae of number theory  it follows by godel's incompleteness theorem [6] that any effective sound system of logic for elementary arithmetic must be incomplete. we show that in any effective sound system of logic for elementary arithmetic, there exist valid unprovable formulae that are quite small relative to the complexity of the logical system. also, such formulae are quite dense. in fact, the situation is about as bad as it could possibly be. that is , no infinite axiom system for elementary arithmetic can be much more compact than a listing of all the valid formulae. the unprovable formulae we construct express predicates in the classes &amp;sgr;2 and π 2 of the kleene arithmetic hierarchy [12]. the construction yields a set of short formulae, at least one of which must be valid and unprovable, but the construction does not tell us which one is valid and unprovable. we also construct small valid unprovable formulae expressing a relation in the class π 1 of the kleene arithmetic hierarchy. these latter formulae are not as small. we do not know how small the independent formulae corresponding to the class π 1 are. the constructions are based on the concept of a restricted oracle, first introduced in [10] and further developed in [11]. the proofs make use of the recent result of matijasevic [9] concerning the relationship between recursively enumerable sets and diophantine equations.  david a. plaisted
on kilbury's modification of earley's algorithm  we improve on j. kilbury's proposal to interchange "predictor" and "scanner" in earley's parser. this modification of earley's parser can trivially be combined with those suggested by s. graham, m. harrison, and w. ruzzo, leading to smaller parse tables and almost the power of lookahead 1. along these lines we can also obtain earley-parsers having partial lookahead r ≥ 1, without storing right contexts. parse trees with shared structure can be stored in the parse tables directly, rather than constructing the trees from "dotted rules."  hans leiss
the future of computational complexity theory: part i as you probably already know, there is an active discussion going on---in forums ranging from lunch- table conversations to workshops on "strategic directions" to formal reports \---regarding the future of theoretical computer science. since your complexity columnist does not know the answer, i've asked a number of people to contribute their comments on the narrower issue of the future of complexity theory. the only ground rule was a loose 1-page limit; each contributor could choose what aspect(s) of the future to address, and the way in which to address them. the first installment of contributions appears in this issue, and one or two more installments will appear among the next few issues.also coming during the next few issues: the search for the perfect theory journal, and (for the sharp-eyed) lance fortnow dons a clown suit. finally, let me mention that work of russell impagliazzo resolves one of the open questions from complexity theory column 11. christos h. papadimitriou oded goldreich avi wigderson alexander a. razborov michael sipser
a type system for dynamic web documents  many interactive web services use the cgi interface for communication with clients. they will dynamically create html documents that are presented to the client who then resumes the interaction by submitting data through incorporated form fields. this protocol is difficult to statically type-check if the dynamic documents are created by arbitrary script code using printf- like statements. previous proposals have suggested using static document templates which trades flexibility for safety. we propose a notion of typed, higher-order templates that simultaneously achieve flexibility and safety. our type system is based on a flow analysis of which we prove soundness. we present an efficient runtime implementation that respects the semantics of only well-typed programs. this work is fully implemented as part of the system for defining interactive web services.  anders sandholm michael i. schwartzbach
on the theory of average case complexity  this paper takes the next step in developing the theory of average case complexity initiated by leonid a. levin. previous works [levin 84, gurevich 87, venkatesan and levin 88] have focused on the existence of complete problems. we widen the scope to other basic questions in computational complexity. our results include:  the equivalence of search and decision problems in the context of average case complexity;  an initial analysis of the structure of distributional-np under reductions which preserve average polynomial-time;  a proof that if all distributional-np is in average polynomial-time then non- deterministic exponential-time equals deterministic exponential time (i.e., a collapse in the worst case hierarchy);  definitions and basic theorems regarding other complexity classes such as average log- space.  s. ben-david b. chor o. goldreich