Two of the most powerful classes of programs for which interesting decision problems are known to be solvable are the class of finite-memory programs and the class of programs that characterize the Presburger, or semilinear, sets. In this paper, a new class of programs that presents solvable decision problems similar to the other two classes of programs is introduced. However, the programs in the new class are shown to be computationally more powerful (i.e., capable of defining larger sets of input-output relations).

Let Q be the class of determmistlc two-way l-counter machines accepting only bounded languages Each machine m Q has the property that m every accepting computation, the counter makes at most a fixed number of reversals It is shown that the emptiness problem for Q is decidable.When the counter is unrestricted or the machine is prowded with two reversal-bounded counters, the emptiness problem becomes undecidable.The decidability of the emptmess problem for Q is useful in proving the solvabdity of some number-theoreuc problems It can also be used to prove that the language L = {u~u21 ~ >-0} cannot be accepted by any machme in Q (u~ and u2 are &stmct symbols).The proof techmque ~s new m that it does not employ the usual "pumpmg," "counting," or "thagonal" argument.Note that L can be accepted by a deterministic two-way machine with two counters, each of which makes exactly one reversal Categories and Subject Descriptors.F. 1.1 IComputation by Abstract Devicesl: Modds of

The problem of picture segmentation is widely believed to be practically unsolvable in its more general case formulation. However, as far as the authors know no formal argumentation has yet been given to this belief related to the segmentation problem. This correspondence provides some theoretical aspects of this phenomenon.

The equivalence problem for deterministic two-way sequential transducers is a long time open problem which is known to be decidable for some restricted cases. Here, the problem is shown to be decidable also for the general case. In fact, the result holds even when the devices are allowed to make some finite number of nondeterministic moves.

Let Q be the class of deterministic two-way one-counter machines accepting only bounded languages. Each machine in Q has the property that in every accepting computation, the counter makes at most a fixed number of reversals. We show that the emptiness problem for Q is decidable. When the counter is unrestricted or when the machine is provided with two reversal-bounded counters, the emptiness problem becomes undecidable. The decidability of the emptiness problem for Q is useful in proving the solvability of some numbertheoretic problems. It can also be used to prove that the language L = {u1iu2i2|i≥0} cannot be accepted by any machine in Q (u1 and u2 are distinct symbols). The proof technique is new in that it does not employ the usual "pumping", "counting", or "diagonal" argument. Note that L can be accepted by a deterministic two-way machine with two counters, each of which makes exactly one reversal.

The complexity of the eqmvalence problem for several sunple programming languages ,s investigated.In pamcular, ~t is shown that a class of programs, called XL, has an NP-complete mequwalence problem; hence its equivalence problem is decidable in determimstw tune 2 p~N~, wherep(N) ,s a polynomtal in the sum of the stzes of the programs.This bound is a four-level exponential improvement over a previously known result A very sunple subset of XL, called SL, is also considered, and it is shown that every XL-program ~s polynomial-time reducible to an eqmvalent SL-program.Moreover, SL is minimal in the sense that all its mstrucUons are independent On the other hand, XL Is maximal m that a "slight" generalization yields a language with an undecidable eqmvalence problem.XL-programs realize precisely the relations (functions) definable by Presburger formulas.

The equivalence problem for deterministic twoway sequential transducers is a long time open problem which is known to be decidable for some restricted cases. Here, the problem is shown to be decidable also for the general case. This even when the devices are allowed to make some finite number of nondeterministic moves.

We investigate the use of path systems in automata theory and computational complexity. A new framework is developed which brings together the main constructions of path systems corresponding to machine models as well as the main algorithms for solving such path systems. Applications to resource-bounded computation are given.

It is shown that the class of relations (functions) definable by Presburger formulas is exactly the class of relations (functions) computable by finite-reversal multicounter machines.

Systems of nonlinear equations of the form D Aft = ~(x), where A is an m × n matrix of ratmnal constants and fi = (yl, , y.), 8(x) = (ol(x), , on(x)) are column vectors, are considered Each o,(x) is of the form r,(x) or lr,(x)], where r,(x) is a rational function ofx with raUonal coefficients It Is shown that the problem of determining for a given system D whether there exists a nonnegatlve integral solution (yh,, y., x) satisfying Dts deodable In fact, the problem is NP-complete when restricted to systems D m which the maximum degree of the polynomials defining the o,(x)'s is bounded by some fixed polynomial m the length of the representation of D Some recent results connecting Dmphantme equations and counter machines are briefly mentioned.KEY WORDS AND PHRASES Hdbert's tenth problem, nonhnear integer programming, Dlophantme equation, decldabthty, NP-complete, polynomial time-bounded Turmg machine, counter machine CR CATEGORIES 5 23, 5 25, 5 26, 5 27, 5 41 lntroducttonHilbert's tenth problem [7] is the problem of determining for a given polynomial p(xl ..... xn) (or a system of polynomials p,(xl .... xn), 1 _< i _< m) with integer coefficients whether it has a nonnegatlve integer solution, i.e., nonnegatlve integers cq, ..., an such that p(al ..... an) = 0 (p,(a~ ..... an) = 0 for 1 _< t _< m).Hilbert's tenth problem is undecidable for (i) (iI) polynomials of degree 4 [14, 18], polynomials in t3 unknowns [15] (it was reported m [13] that this has been reduced to 9 unknowns), and (iii) systems of quadratic polynomials [3,9].On the other hand, Hilbert's tenth problem is decidable for (iv) polynomials in 1 unknown and (v) polynomials of degree 2 [17].It is not known whether the degree 4 in (i) and the 9 unknowns in (ii) are minimal.Also, the minimal number of quadratic polynomials needed to prove the undecidability in (iii) is not known.A decision procedure for a large class of polynomials in 2 unknowns is known [3] but not yet for the general case.For 3 unknowns almost nothing is known.Pinpointing the precise boundary between decidability and undecidability of Hilbert's tenth problem with respect to the degree, the number of unknowns, and number of quadratic polynomials in the system remains an interesting research problem.A related problem which is of practical interest is that of finding special classes of polynommls (or systems of polynomials) for which Hilbert's tenth problem is decidable This paper studies one such class.Consider a system of nonhnear equations of the form D: Aft = ~(x), where A is an m X n matrix of rational constants and fi = (yl ..... yn), ~(x) = (ol(x) ..... o,~(x)) are column

@, where ri(x) is a rational function of x with rational coefficients. It is shown that the problem of determining for a given system D whether there exists a nonnegative integral solution (y1,...,yn,X) satisfying D is decidable. In fact, the problem is NP-complete when restricted to systems D in which the maximum degree of the polynomials defining the σi(x)'s is bounded by some fixed polynomial in the length of the representation of D. Some recent results connecting Diophantine equations and counter machines are briefly mentioned.