A deterministic one-counter automaton (doca) is a deterministic pushdown automaton having a one-element stack alphabet. It is easy to see that the inclusion and the nullity-of-intersection problems for doca's are undecidable. In contrast to this, the authors give a decision procedure for the equivalence of doca's and show that its time complexity is bounded above by a function exponential in about the square root of the number of states of the tested doca's. They conjecture that the equivalence is decidable for the class of all deterministic pushdown automata.

A pushdown store automaton (pda) is finite-turn if there is a uniform bound on the number of times it can switch from pushing (increasing the length of the pushdown store) to popping (decreasing the pushdown store length) during any computation on any input. The author establishes the decidability of the equivalence problem (do two machines accept the same language?) for deterministic finite-turn pda's. The significance of the result lies in the proof techniques used in establishing it and in the fact that it represents one of the major breakthroughs towards settling the long outstanding conjecture that the equivalence problem for deterministic pda's (dpda's) is decidable (the corresponding problem is known to be undecidable for nondeterministic pda's even in very restricted cases).

We present an analysis of deterministic one-counter automata in order to show that the equivalence problem for them is decidable. All our arguments and results can be translated directly into schema theoretic terms. The corollary that then follows is that equivalence is decidable for Janov schemas even when these are allowed an auxiliary counter.

Over the past 30 years, Leslie Valiant has made fundamental contributions to many aspects of theoretical computer science. His work has opened new frontiers, introduced ingenious new concepts, and presented results of great originality, depth, and beauty. Time and again, Valiant's work has literally defined or transformed the computer science research landscape.

1. Computational learning theory. Valiant's greatest single contribution may be his paper 'A theory of the learnable' (1984), which laid the foundations of computational learning theory. ... Valiant's "probably approximately correct" (PAC) model supplied beautiful foundations for the very concept of learning.
2. Complexity of enumeration. In the early 1970's, computational complexity generally dealt with the difficulty of decision problems, such as whether a graph has a perfect matching or whether a traveling salesman can find a route of at most a certain length. ... One of Valiant's most noteworthy discoveries is that counting problems are much more subtle than previous experience suggested. A counting problem asks for the number of some combinatorial objects: for example, how many perfect matchings are there in a graph? We are not just asking the decision problem of whether that number is positive, but also how large it is. If the decision problem is difficult, then the counting problem must be as well, but Valiant's surprising realization was that the converse fails. In his paper "The complexity of computing the permanent" (1979), he showed that although there is an efficient algorithm to tell whether a graph has a perfect matching, there is no efficient algorithm to count perfect matchings (unless P = NP), and in fact counting perfect matchings is as hard as any counting problem. This came as a shock to the computational complexity community, which had grown accustomed to the idea that decision problems would easily capture the key features of a problem.
3. Algebraic computation. Another key contribution to computational complexity was Valiant's theory of algebraic computation, in which he established a framework for understanding which algebraic formulas can be evaluated efficiently. ... In his paper "Completeness classes in algebra" (1979), Valiant characterized the difficulty of algebraic computation in terms of two fundamental and closely related functions from linear algebra, namely the determinant and the permanent.
4. Parallel and distributed computing. In addition to computational learning theory and computational complexity, a third broad area in which Valiant has made important contributions is the theory of parallel and distributed computing. His results here range from simple, but powerful and elegant, insights to reexamining the very foundations. An example of a simple insight is his parallel routing scheme, described in the paper "A scheme for fast parallel communication" (1982).

Rarely does one see such a striking combination of depth and breadth as in Valiant's work. He is truly a heroic figure in theoretical computer science and a role model for his courage and creativity in addressing some of the deepest unsolved problems in science.