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

Controlled -Pushdown Automata

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

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+3]

Abstract

A device called controlled pushdown automaton (CPA) is introduced and special classes of it are shown to characterize the families of simple matrix languages (SML's) and right-linear simple matrix languages (RLSML's). Other special classes are shown to define, respectively, the smallest full AFL containing the MIL' s and the smallest full API, containing the Rz,SM1L s . Closure properties of the families of sets defined by different classes of CPA s are presented and their relation to other families of languages discussed. Hierarchy theorems and other related results are also obtained. In particular, it is shown that the smallest full AFL containing the homornarphic replications of the context-free languages is not principal.

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

Page 1 of 25

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Controlled -Pushdown Automata

by Oscar H. Ibarra

0400057,

READING ROOM _. .'CRMPUTERs SCIENCE DEPARTMENT A! E..U.N.WF--RatTY Department of Computer Science University of Minnesota Minneapolis, Minnesota 55455

Technical Report 72--7 June, Controlled Pushdown Automata by Oscar H. Ibarra

Abstract

A device called controlled pushdown automaton (CPA) is introduced and special classes of it are shown to characterize the families of simple matrix languages (SML's) and right-linear simple matrix languages (RLSML's). Other special classes are shown to define, respectively, the smallest full AFL containing the MIL' s and the smallest full API, containing the Rz,SM1L s . Closure properties of the families of sets defined by different classes of CPA s are presented and their relation to other families of languages discussed. Hierarchy theorems and other related results are also obtained. In particular, it is shown that the smallest full AFL containing the homornarphic replications of the context-free languages is not principal.

Tntroduction

A controlled pushdown automaton (CPA) is a one-way pushdown automaton [2] which is equipped with a read-only control tape and an associated control tape head. The control tape can contain. strings of the form

(Equation Omitted)

where each yi is a string not containing q% and $. Depending on the state, input, rightmost symbol of the pushdown tape, and the symbol scanned by the,. control tape head, the CPA may change state, rewrite the rightmost symbol of the pushdown tape by some string whose length is uniquely specified by the symbol under the control tape'headp and move the control. tape head one symbol to the right, or it may change state and simultaneously reinitialize the pushdown tape and reset the, control tape head to the first -, to its left. The main results of this paper are the characterizations of some known families of languages in terms of special classes of CPA's. The paper is divided into four sections. Section i introduces CPA and special forms of it:

(Equation Omitted)

which makes at most k resets on any substring

(Equation Omitted)

University of Minnesota Page 1 Dec 31, 1972

Page 2 of 25

Controlled -Pushdown Automata

of the control tape.

(Equation Omitted)

whose control tape can only contain strings of the farm

(Equation Omitted)

is essentially a k-CPA without the pushdown tape, and a k-SOFA is a k-CFA whose control tape is restricted to strings of the form pyl$. 1-CPA's and 1-SCPA's are equivalent, and they define exactly the family of context-free languages [2]. Similarly, 1-CFA's and 1-SCFA's define the family of regular sets [10]. A k-SCFA is equivalent to a k-turn checking automaton introduced in
[13], and the family of k-CFA's is equivalent to a particular family of acceptors introduced in [4]. Section 1 concludes with a result which shows that every recursively enumerable set [1] can be accepted by a modified 2-SCPA i...