STOC

The following problem is shown to be decidable. Given are homomorphisms h₁ and h₂ from Σ* to Σ* and strings σ₁ and σ₂ over Σ such that hⁿ_i(σ_i) is a proper prefix of hⁿ⁺¹_i (σ_i) for i = 1, 2 and all n ≥ 0, i.e. for i = 1, 2, h_i generates from σ_i an ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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)), f³(x),. . . , if one exists. This paper investigates lower bounds on the number of function ...

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. ...

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 ...

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 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 ...

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” ...

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, ...

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.

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 ...

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 ...

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 ...

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 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 ...

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 ...

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 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 ...

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 ...

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 ...

In this extended abstract, we present several new layouts for the shuffle-exchange graph, including one which requires only 0(n²/log²n) area. The optimal layout is described and analyzed in section 3. The analysis is heavily dependent on several ...