Browse Prior Art Database

The Unsolvability of the Equivalence Problem for e-Free NGSM's with Unary Input (Output) Alphabet and Applications to Some Grammar and Graph Problems

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

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+3]

Abstract

The equivalence problem for deterministic generalized sequential machines is decidable. .(In fact, the equivalence problem is solvable for deterministic sequential transducers [1,3]). It is also obvious that the equivalence problem for complete nondeterministic generalized sequential machines is decidable. (These are machines which. output exactly one symbol per move.) However, the equivalence problem for e-free (not having the null string a as output) nondeterministic generalized sequential machines is unsolvable. This result was shown by Griffiths [4] who also observed (as a corollary) that the equivalence problem for c-finite languages [3] is undecidable. In [2], the result was used to show the unsolvability of the equivalence problem for sentential forms of context-free grammars. In this paper, we strengthen Griffiths's result. Specifically, we show that the equivalence problem for e-free nondeterministic generalized sequential machines is unsolvable even if we restrict the input/output to unary/binary (respectively, binary/unary) alphabets. This result which is somewhat surprising clearly demonstrates the complexity that nondeterminism can introduce even in very simple computing devices. Related results are also obtained. For example, it is proved that there is no algorithm to. determine for 2 right-linear grammars G1 and G2 all of whose rules are of the form A - xB or A -* x (A, B are nonterminals, x is a non-null binary terminal string) whether for each binary string y and n > 1, y is derivable in G1 in n steps if and only if y is derivable in G2 in n steps. In fact, the. result holds even if the rules [Equation ommitted] are restricted so that the length of x is 2, 3, or 6. Another result concerns directed graphs. Let [Equation ommitted] be a directed graph, where V is a finite nonempty

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

Page 1 of 23

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

The Unsolvability of the Equivalence Problem for e-Free NGSM's with Unary Input (Output) Alphabet and Applications to Some Grammar and Graph Problems

by

Oscar H. Ibarra Computer Science Department

Institute of Technology

114 Lind Hall

University of Minnesota

Minneapolis, Minnesota 55455

Technical Report 77-6

April 1977 Cover design courtesy of Ruth and Jay Leavitt

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

1. Introduction

The equivalence problem for deterministic generalized sequential machines is decidable. .(In fact, the equivalence problem is solvable for deterministic sequential transducers [1,3]). It is also obvious that the equivalence problem for complete nondeterministic generalized sequential machines is decidable. (These are machines which. output exactly one symbol per move.) However, the equivalence problem for e-free (not having the null string a as output) nondeterministic generalized sequential machines is unsolvable. This result was shown by Griffiths [4] who also observed (as a corollary) that the equivalence problem for c-finite languages [3] is undecidable. In [2], the result was used to show the unsolvability of the equivalence problem for sentential forms of context-free grammars. In this paper, we strengthen Griffiths's result. Specifically, we show that the equivalence problem for e-free nondeterministic generalized sequential machines is unsolvable even if we restrict the input/output to unary/binary (respectively, binary/unary) alphabets. This result which is somewhat surprising clearly demonstrates the complexity that nondeterminism can introduce even in very simple computing devices. Related results are also obtained. For example, it is proved that there is no algorithm to. determine for 2 right-linear grammars G1 and G2 all of whose rules are of the form A - xB or A -* x (A, B are nonterminals, x is a non-null binary terminal string) whether for each binary string y and n > 1, y is derivable in G1 in n steps if and only if y is derivable in G2 in n steps. In fact, the. result holds even if the rules

(Equation Omitted)

are restricted so that the length of x is 2, 3, or 6. Another result concerns directed graphs. Let

University of Minnesota Page 1 Dec 31, 1977

Page 2 of 23

The Unsolvability of the Equivalence Problem for e-Free NGSM's with Unary Input (Output) Alphabet and Applications to Some

Grammar and Graph Problems

(Equation Omitted)

be a directed graph, where V is a finite nonempty set of vertices, E is a finite nonempty set of ordered pairs of distinct vertices called edges, v0 is a distinguished vertex called the source vertex, and f and g are functions from E into

(Equation Omitted)

respectively. Let

1, each ai in {0,1}, there exist edges

(Equation Omitted)

such that

(Equation Omitted...