Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A Useful Device for Showing the Solvability of Some Decision Problem

IP.com Disclosure Number: IPCOM000128526D
Original Publication Date: 1975-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 13 page(s) / 32K

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+4]

Abstract

We look at a restricted model of a multihead pushdown automaton and use some of its properties to show the existence of algorithms for some decision problems concerning code sets and vector addition systems.

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

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Useful Device for Showing the Solvability of Some Decision Problem;

by Oscar H. Ibarra and Chul E. Kim

04Q 13 Department of Computer Science Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 . Technical ~teport # 75-13 n.._ r._ Cover courtesy of Ruth and Jay Leavitt

A Useful Device for Showing the Solvability of Some Decision Problems by

Oscar H. Ibarra and Chul E. Kim Department of Computer Science University of Minnesota Minneapolis, Minnesota 55455 This research was supported by the National Science Foundation Grant DCR72-03728-A01.

Abstract

We look at a restricted model of a multihead pushdown automaton and use some of its properties to show the existence of algorithms for some decision problems concerning code sets and vector addition systems.

1. Introduction

It is well known that the emptiness problem for context-free languages is decidable [1]. This result has been used to show the solvability of other decision problems in language theory. For example, a recent paper of Greibach [3] uses this result to prove the existence of an algorithm for deciding for two n-tuples of non-null code words

(Equation Omitted)

whether there are indices

(Equation Omitted)

She shows that the set of such

(Equation Omitted)

is a one-counter language, hence, context-free. 11 lk In this paper, we look at a restricted class of multihead pushdown automata and utilize some of its properties (e.g., solvable emptiness problem) to prove the existence of algorithms for some decision problems. We show that if

(Equation Omitted)

are n-dimensional vectors of integers with v0 non-negative, then the

(Equation Omitted)

University of Minnesota Page 1 Dec 31, 1975

Page 2 of 13

A Useful Device for Showing the Solvability of Some Decision Problem

is non-negative

and.the s,.im of the coordinates

(Equation Omitted)

(Equation Omitted)

is a semilinear set as defined

1 in [1,2]. Hence, the membership and equivalence problems for such sets are solvable.l If in the definition of P3(v0,vl,...,vm) the requirement on v0 + vi +...+ vi is replaced by

(Equation Omitted)

is a non-

1 j 1 J negative vector", then the set is called a reachability set. Robin has shown that the equivalence problem for such sets is uridecidable [8]. Another problem for which we have an algorithm is that of deciding for two n-tuples of non-null code words

(Equation Omitted)

whether there are indices

(Equation Omitted)

such that

(Equation Omitted)

is a permutation

of (jl,...,jk). However, if, instead of a permutation, we require that

(Equation Omitted)

then the problem becomes the Post correspondence problem which is known to be undecidable
[10]. Finally, a generalization of the problem considered in [3] is also shown to be decidable.,

1 'Solvable' and 'decidable' are used interchangeably in the paper..

2. Multihead Pushdown Automata and Semilinear Sets

The automata that we shall be concerned with are the (one-...