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 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 ommitted] respectively. Let 1, each ai in {0,1}, there exist edges [Equation ommitted] such that [Equation ommitted] It is shown that it is recursively unsolvable.to 1 determine for aribitary directed graphs [Equation ommitted] The proofs are facilitated by considering a more general type of [Equation ommitted] machine which we now define. Definition. Ane-free nondeterministic generalized sequential machine with accepting states (EFNGSMA) over EX A is -a 6-tuple [Equation ommitted] where K, E, and A are finite nonempty sets called the state set, input alphabet and output alphabet, respectively. 6 is a function from K x E into the finite subsets of [Equation ommitted] is the initial state, and F c K is a .set of accepting states. If F = K (i.e., all states are accepting), M is called simply an EFNGSM. In this case, F(= K) is not included in the specification. The function d is extended to K x E+ as follows: For q in [Equation ommitted] Ifor some [Equation ommitted] For x in E+, let [Equation ommitted] in [Equation ommitted] relation [Equation ommitted] is called an EFNGSMA (respectively, EFNGSM) relation over Ex A if we can find an EFNGSMA (respectively, EFNGSM) M such that R(M) = R. For convenience, we will sometimes represent an [Equation ommitted] by a directed labeled graph where the nodes represent states and the labeled for some Edges represent transitions. If [Equation ommitted] contains [Equation ommitted] then there is an edge from node q to node p with label [Equation ommitted]. Forexample, Figure 1 shows an EFNGSMA where [Equation ommitted] is the initial state, and [Equation ommitted]

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...