Browse Prior Art Database

A Decidable Class of Counter Machines with Applications to Some Number-Theoretic Problems

IP.com Disclosure Number: IPCOM000128540D
Original Publication Date: 1977-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 18 page(s) / 45K

Publishing Venue

Software Patent Institute

Related People

Eitan M. Gurari: AUTHOR [+4]

Abstract

This paper studies the class of deterministic two-way finite automata augmented by reversal-bounded counters operating on inputs over a one-letter alphabet. It is shown that this class has solvable decision questions and can be used to solve same number-theoretic problems.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 18

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Decidable Class of Counter Machines with Applications to Some Number-Theoretic Problems

by

Eitan M. Gurari and Oscar H. Ibarra

Computer Science Department

114 Lind Hall

Institute of Technology

University of Minnesota

Minneapolis, Minnesota: 55455

Technical Report 77-10

June 1977 Cover design courtesy of Ruth and Jay Leavitt A Decidable Class of Counter Machines with Applications to Some Number-Theoretic Problems* by

Eitan M. Gurar3 and Oscar H. Ibarra Department of Computer Science University of Minnesota Minneapolis, Minnesota 55455 *This~research was partially supported by the National Science Foundation under Grant No. DCR75-17090.

Abstract

This paper studies the class of deterministic two-way finite automata augmented by reversal- bounded counters operating on inputs over a one-letter alphabet. It is shown that this class has solvable decision questions and can be used to solve same number-theoretic problems.

i. Introduction

It is well known that the class of deterministic two-way finite automata augmented by a single counter has an unsolvable emptiness probleml [6]. The result holds.even. if the input alphabet is restricted to one letter. The emptiness problem is also unsolvable for deterministic two-way finite auto- mata augmented by two counters which are reversal-bounded, even if the input is restricted to come from a bounded language

(Equation Omitted)

, each ai a letter)-[3]. On the other hand, for deterministic two-way mufti-counter machines whose input and counters are reversal-bounded, all interesting decision questions are decidable
[3]. In this paper, we show that every deterministic two-way mufti-counter machine with a one- letter input alphabet whose counters are reversal-bounded can effectively be reduced to an equivalent (ordinary) finite automaton. Thus, for such machines, all interesting decision

University of Minnesota Page 1 Dec 31, 1977

Page 2 of 18

A Decidable Class of Counter Machines with Applications to Some Number-Theoretic Problems

questions are decidable. This result can be used to show the solvability o some number- theoretic problems. For example, consider a system of nonlinear Dio-phantine equations of the form D:

(Equation Omitted)

where A is a m xn integer matrix and

(Equation Omitted)

are column vectors, each

(Equation Omitted)

being a rational function of x with integer coefficients. The set of non-negative integral solutions to

(Equation Omitted)

are non-negative integers satisfying system D). In [2], it is shown that the problem of determining for a given system D whether S(D) ~ b is decidable. Here, we gave another proof by showing that the set

(Equation Omitted)

there exist

(Equation Omitted)

is in S(D)}3 can be accepted by a deterministic two-way mufti-counter machine whose counters are reversal-bounded; hence L(D) is regular. We also show that the problem, of determining whether S(D) is finite or infinite is solvable. Thr...