Browse Prior Art Database

A Note on Semilinear Sets and Bounded-Reversal Tl`ultihead Pushdown Automata

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

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+3]

Abstract

It is shoTm tbat a bounded language is recognizable by a bounded--reversal multihead pushdovrn automaton if and only if it satisfies the semj.linear proverty. Related results are also presented. This research was supported by the National Science Foundation Grant GJ--3561 .

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

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Note on Semilinear Sets and Bounded-Reversal Tl`ultihead Pushdown Automata*

By Oscar H. Ibarra

40015Computer, Information, and Control Sciences Institute of Technology University of Minnesota Minneapolis, Minnesota Technica~.rC',fo rt"74-t3 'lay, 197 This research was supported by the Pxational Science Foundation Grant GJ-35615.

Cover courtesy of Ruth and Jay Leavitt A Note on Semilinear Sets anti Bounded-Reversal MUltihead hushdocm Automata

by

Oscar F3. Tbarra

Department of Computei; Informati:6n;~and~:Contral Sciences University of Minnesota

Abstract

It is shoTm tbat a bounded language is recognizable by a bounded--reversal multihead pushdovrn automaton if and only if it satisfies the semj.linear proverty. Related results are also presented. This research was supported by the National Science Foundation Grant GJ--3561 .

.1. Introduction

The class of tcno-way multihead aushdotm automata tv?aose 'heads can only reverse directions b~.~ at most a fixed number is investigated. It is shown that~a bounded language-is accepted by. an automaton is this class if and only if 3t satisfies the semilinear property, an extension of the. result fox the one-head case reported 3n [4): This note derives its motivation from a recent paper of Suiiborough {7) c~7ho showed a similar result for bounded-reversal multi-head finite automata. , v An - example is given of a non=bounded language- vhich does not satisfy the semilinear property that is recognizable b7 a one-nay two-head--finite automaton and by a one-reversal one-head pushdocm automaton;, thus shotri.ng that the re- , stilts above are not valid..for.iion-bounded. languages. A restricted class of one-way multihead nushdown automata is then presented whose corresponding languages are shown to satisfy the semilinear property.

The class of tcno-way multihead aushdotm automata tv?aose 'heads can only reverse directions b~.~ at most a fixed number is investigated. It is shown that~a bounded language-is accepted by. an automaton is this class if and only if 3t satisfies the semilinear property, an extension of the. result fox the one-head case reported 3n [4): This note derives its motivation from a recent paper of Suiiborough {7) c~7ho showed a similar result for bounded-reversal multi-head finite automata. , v An - example is given of a non=bounded language- vhich does not satisfy the semilinear property that is recognizable b7 a one-nay two-head--finite automaton and by a one-reversal one-head pushdocm automaton;, thus shotri.ng that the re- , stilts above

University of Minnesota Page 1 Dec 31, 1974

Page 2 of 8

A Note on Semilinear Sets and Bounded-Reversal Tl`ultihead Pushdown Automata

are not valid..for.iion-bounded. languages. A restricted class of one-way multihead nushdown automata is then presented whose corresponding languages are shown to satisfy the semilinear property.

2. Preliminaries

Let E be a finite set -of symbols .an...