Browse Prior Art Database

A Note on Stack Automata

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

Publishing Venue

Software Patent Institute

Related People

James S. Seck: AUTHOR [+3]

Abstract

The model of a stack automaton is modified in such a way that it may write in the interior of its stack but with the provision that if it does so all symbols above the symbol being rewritten must simultaneously be erased.. It is shown that this extra freedom does not add to the computational power of the stack automaton in the following cases: one-way nondeterministic, two-way nondeterministic, and two-way deterministic. It is conjectured that the modification does add power in the one-way deterministic case.

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

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Note on Stack Automata'

by James S. Seck

Department of Computer . Science University of Minnesota Minneapolis, Minnesota' 55455

Technical Report 72-9 June, A Note on Stack Automat.a

by

James S. Seck

Abstract

The model of a stack automaton is modified in such a way that it may write in the interior of its stack but with the provision that if it does so all symbols above the symbol being rewritten must simultaneously be erased.. It is shown that this extra freedom does not add to the computational power of the stack automaton in the following cases: one-way nondeterministic, two-way nondeterministic, and two-way deterministic. It is conjectured that the modification does add power in the one-way deterministic case.

Introduction

Knuth and Bigelow [21 have described a programming language based on the original definition of a stack automaton by Ginsburg, Greibach, and Harrison [1]. The semantics of that language required that if the program. tried to execute a write statement inside the stack, the program would halt and reject the input. Another natural semantic definition would have the program performing the write instruction, but at the sarie time losing the contents of the stack above the symbol being rewritten. This is easily accomplished by just moving a pointer which marks the top of the stack. The model of the stack automaton is modified to reflect this added capability, and it is shown in this note that, except possibly for the one-way deterministic case, the computing power remains the same.

The Modified Model

We briefly describe the model of a stack automaton as presented in [21 and then introduce the desired modification. A (two"way nondeterministic) stack automaton is a 7-tuple,

(Equation Omitted)

where K is a finite nonempty set of states, is a finite nonempty set of inRut symbols which includes the symbols

(Equation Omitted)

is a finite nonempty set of stack

University of Minnesota Page 1 Dec 31, 1972

Page 2 of 7

A Note on Stack Automata

(Equation Omitted)

is the start symbol and marks the left end of the stack, qO is the start state, F is the set of final states, and 6 is a mapping from K x t x r into -the finite subsets of

(Equation Omitted)

The stack automaton has two tapes; an input tape of the form aoal...a n where a 0 = i~, a n and a i c'E for 1 < i < n-1, and a storage tape of the form

(Equation Omitted)

where

(Equation Omitted)

configuration of a stack automaton with input a a is a 4-tuple of the form

(Equation Omitted)

where

(Equation Omitted)

is the current state, AO ... A m is the current stack content with the input .head scanning ai, and the stack head scanning Ai. -3-

(1) The significance of

(Equation Omitted)

is that if G is in a configuration,

(Equation Omitted)

with

(Equation Omitted)

, then S may enter the new configuration,

(Equation Omitted)

provided that

(Equation Omitted)

(Equation Omitted)

University of Minnesota Page 2 Dec 31, 1972...