Browse Prior Art Database

Some Decision Problems Concerning Sequential Transducers and Checking Automata

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

Publishing Venue

Software Patent Institute

Related People

Eitan M. Gurari: AUTHOR [+4]

Abstract

Boundary points between decidability arid undecidability of various decision questions concerning two-way sequential transducers and checking automata are investigated. The results show how some unsolvable problems become solvable when certain restrictions (e. g., the machines being deterministic, reversal-bounded, etc.) are imposed. A solution to an open problem concerning cascade products of pushdown automata is also given. * This research was supported by the National Science Foundation under Grant No. DCR75-17090.

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

Page 1 of 25

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Some Decision Problems Concerning Sequential Transducers and Checking Automata

by Eitan M. Gurari and Oscar H. Ibarra

Computer Science Department

114 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455

04 Technical Report 77-15 September, 1977 Cover design courtesy of Ruth and Jay Leavitt Some Decision Problems Concerning Sequential Transducers and Checking Automata*

by

Eitan M. Gurari and Oscar H. Ibarra Department of Computer Science University of Minnesota Minneapolis, Minnesota 55455

Abstract

Boundary points between decidability arid undecidability of various decision questions concerning two-way sequential transducers and checking automata are investigated. The results show how some unsolvable problems become solvable when certain restrictions (e. g., the machines being deterministic, reversal-bounded, etc.) are imposed. A solution to an open problem concerning cascade products of pushdown automata is also given. * This research was supported by the National Science Foundation under Grant No. DCR75-17090.

Introduction

The simplest known machine which can map a language (= set of strings) into another is the deterministic one-way sequential transducer. The properties of one-way sequential transducers are well known. For example, it is a basic result that relational equivalence is decidable for deterministic sequential transducers but undecidable for the nondeterministic case [6J. The uasolvabiiity of the latter holds even if the machines operate in real time and the input (or output) alphabet is restricted to one letter j10.]. The set of output string's (i.e., transduction) defined by a nondeterministic transducer is regular jI2]. Rence, all the usual decision questions concerning one--way sequential trans-ductioas are solvable. A natural generalization of the one- way transducer is one which is allowed two-way motion on the input string. Clearly, two-way sequential transducers are much more powerful than one-way transducers (e.g., they can make duplicate copies of an input string). Two-way sequential transducers have been studied in several places. In [lj language-theoretic properties of two-way sequential transductions of regular sets and context-free languages are given, and in jI3] a grammatical characterization of deterministic two-way sequential transductions of regular sets is shown.. In a recent paper [8] (see also j5]), algebraic and grammatical characterizations of several restricted classes two-way sequen-tial transductions of full semiAFL's are presented. In this paper, we look at several decision questions concerning two-way sequential transducers. Section 1 gives some definitions and a few basic results. In particular, the relationship between two-way sequential transducers and checking automata [4 ] is established. Section 2 presents some undecidable properties of

University of Minnesota Page 1 Dec 31, 1977

Page 2...