No abstract available.
Proceeding Downloads
The Ω-sequence equivalence problem for DOL systems is decidable
The following problem is shown to be decidable. Given are homomorphisms h1 and h2 from Σ* to Σ* and strings σ1 and σ2 over Σ such that hni(σi) is a proper prefix of hn+1i (σi) for i = 1, 2 and all n ≥ 0, i.e. for i = 1, 2, hi generates from σi an ...
Unique normal forms in term rewriting systems with repeated variables
A term rewriting system is a finite set of axiom schemata of the form A@@@@B where A and B are terms that contain variables. An important question for such systems is whether normal forms are unique (i.e. each term has at most one normal form). For ...
Classes of functions for computing on binary trees (Extended Abstract)
This paper constitutes part of a general investigation into abstract computability on finitely generated free algebras (term algebras). The general idea is to determine an abstract computational process appropriate for computing on term algebras, the ...
Examples of hard tautologies in the propositional calculus
We present examples of hard tautologies in propositional calculus by encoding instances of the assertions made by Ramsey's theorem. We provide evidence that these tautologies are indeed hard by
1. showing that there are no short proofs for these ...
The complexity of parameter passing in polymorphic procedures
Our subject is at the confluence of two foundational research areas: formal independence results, and higher order data types.
A central problem with polymorphism is the impact of involved polymorphic types on termination of program executions and on ...
Pushdown automata, graphs, ends, second-order logic, and reachability problems
We have discovered a very strong connection between certain areas of theoretical computer science—the theory of context-free languages and pushdown automata, tiling problems, cellular automata, and vector addition systems—and certain concepts from group ...
Fast programs for initial segments and polynomial time computation in weak models of arithmetic (Preliminary Abstract)
In this paper we study two alternative approaches for investigating whether NP complete sets have fast algorithms. One is to ask whether there are long initial segments on which such sets are easily decidable by relatively short programs. The other ...
Localized search in sorted lists
It is well known that every one of the set operations insert, delete and member can be performed in O(log n) steps, where n is the number of elements currently in the set. Here we implement these operations and a move operation for a sorted list with f ...
Convex decompositions of polyhedra
An important direction of research in computational geometry has been to find methods for decomposing complex structures into simpler components. In this paper, we examine the problem of decomposing a three-dimensional polyhedron P into a minimal ...
Digital straightness and convexity (Extended Abstract)
We define straightness and convexity of regions in a digital picture. Then it is shown that a few important properties satisfied by convex (Euclidean) regions are also satisfied by convex digital regions. We extend the definition of digital convexity of ...
A linear probing sort and its analysis(Preliminary Draft)
We present a variant of the distribution sort approach which makes use of extra storage to sort a list of n elements in an average of about (2+√)n = 3.412...n probes into a table. An accurate analysis of this technique is made by introducing a transform ...
Lower bounds for the cycle detection problem
Given a function f over a domain and an element x in the domain, the cycle detection problem is to find a repetition in the sequence of values x, f(x), f(f(x)), f3(x),. . . , if one exists. This paper investigates lower bounds on the number of function ...
Time-space-optimal string matching (Preliminary Report)
In this paper we describe a new linear-time string-matching algorithm requiring neither dynamic storage allocation nor other high-level capabilities. The algorithm can be implemented to run in linear time even on a six-head two-way finite automaton. ...
A data structure for dynamic trees
We propose a data structure to maintain a collection of vertex-disjoint trees under a sequence of two kinds of operations: a link operation that combines two trees into one by adding an edge, and a cut operation that divides one tree into two by ...
On the parallel computation for the knapsack problem
We are interested in the complexity of solving the knapsack problem with n input real numbers on a parallel computer with real arithmetic and branching operations. A processor-time tradeoff constraint is derived; in particular, it is shown that an ...
A difference in efficiency between synchronous and asynchronous systems
A system of parallel processes is said to be synchronous if all processes run using the same clock, and it is asynchronous if each process has its own independent clock. For any s, n, a particular distributed problem is defined involving system behavior ...
Distributed algorithms for synchronizing interprocess communication within real time
This paper considers a fixed (possibly infinite) set π of distributed asynchronous processes which at various times are willing to communicate with each other.
We describe probabilistic algorithms for synchronizing this communication with boolean “flag” ...
Reversal complexity of counter machines
It has long been known that deterministic 1-way counter machines recognize exactly all r.e. sets. Here we investigate counter machines with general recursive bounds on counter reversals. Our main result is that for bounds which are at least linear, ...
Space-bounded probabilistic turing machine complexity classes are closed under complement (Preliminary Version)
For tape constructible functions S(n)≥log n, if a language L is accepted by an S(n) tape bounded probabilistic Turing machine, then there is an S(n) tape bounded probabilistic Turing machine that accepts L, the complement of L.
A characterization of the class of functions computable in polynomial time on Random Access Machines
Enumeration problems constitute a major part of combinatorial mathematics.
Combinatorial mathematics expresses the solution of enumeration problems by means of solving formulas, generally based on the usual arithmetic operations [7]. These solving ...
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 ...
Measures of parallelism in alternating computation trees (Extended Abstract)
We examine three ways of restricting the size (and shape) of the accepting computation trees of alternating Turing machines.
We continue study by examining bounds on the number of leaves in the tree (Section 3), the 'width' of the tree (Section 4), and ...
LALR(k) testing is PSPACE-complete
The problem of testing whether or not an arbitrary context-free grammar is LALR(k) for a fixed integer k ≥ 1 (i.e. only the subject grammar is a problem parameter) is shown to be PSPACE-complete. The result is in contrast with testing the membership in ...
Bandwidth constrained NP-Complete problems
Bandwidth restrictions are considered on several NP-Complete problems, including the following problems:
(1) 3-Satisfiability,
(2) Independent Set and Vertex Cover,
(3) Simple Max Cut
(4) Partition into Triangles,
(5) 3-Dimensional Matching,
(6) Exact ...
The complexity of dynamic languages and dynamic optimization problems
In this paper we offer a unifying framework for dynamic problems in terms of “dynamic languages”, and we discuss the complexity of these languages. In particular, many dynamic languages derived from NP-complete languages can be shown to be polynomial ...
Low level complexity for combinatorial games
There have been numerous attempts to discuss the time complexity of problems and classify them into hierarchical classes such as P, NP, PSPACE, EXP, etc. A great number of familiar problems have been reported which are complete in NP (nondeterministic ...
An algorithm for the general Petri net reachability problem
An algorithm is presented for the general Petri net reachability problem based on a generalization of the basic reachability construction which is symmetric with respect to the initial and final marking. Sets of transition sequences described by finite ...
An efficient general purpose parallel computer
In this paper we investigate the question of what is a good way to interconnect a large number of processors. Our main result is the construction of a universal parallel machine that can simulate every reasonable parallel machine with only a small loss ...
Universal schemes for parallel communication
In this paper we isolate a combinatorial problem that, we believe, lies at the heart of this question and provide some encouragingly positive solutions to it. We show that there exists an N-processor realistic computer that can simulate arbitrary ...
New layouts for the shuffle-exchange graph(Extended Abstract)
In this extended abstract, we present several new layouts for the shuffle-exchange graph, including one which requires only 0(n2/log2n) area. The optimal layout is described and analyzed in section 3. The analysis is heavily dependent on several ...
Index Terms
- Proceedings of the thirteenth annual ACM symposium on Theory of computing
Recommendations
Acceptance Rates
Year | Submitted | Accepted | Rate |
---|---|---|---|
STOC '15 | 347 | 93 | 27% |
STOC '14 | 319 | 91 | 29% |
STOC '13 | 360 | 100 | 28% |
STOC '11 | 304 | 84 | 28% |
STOC '08 | 325 | 80 | 25% |
STOC '03 | 270 | 80 | 30% |
STOC '02 | 287 | 91 | 32% |
STOC '01 | 230 | 83 | 36% |
STOC '00 | 182 | 85 | 47% |
STOC '98 | 169 | 75 | 44% |
STOC '97 | 211 | 75 | 36% |
STOC '96 | 201 | 74 | 37% |
STOC '89 | 196 | 56 | 29% |
STOC '88 | 192 | 53 | 28% |
STOC '87 | 165 | 50 | 30% |
STOC '80 | 125 | 47 | 38% |
STOC '79 | 111 | 37 | 33% |
STOC '78 | 120 | 38 | 32% |
STOC '77 | 87 | 31 | 36% |
STOC '76 | 83 | 30 | 36% |
STOC '75 | 87 | 31 | 36% |
STOC '74 | 95 | 35 | 37% |
STOC '71 | 50 | 23 | 46% |
STOC '70 | 70 | 27 | 39% |
Overall | 4,586 | 1,469 | 32% |