Browse Prior Art Database

Space and Time Efficient TM Simulations and Characterizations of Some Restricted Classes of Automata

IP.com Disclosure Number: IPCOM000128567D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 13 page(s) / 41K

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+5]

Abstract

In this paper we present space/time efficient Turing machine algorithms for recognizing some subclasses of deterministic context-free languages. We also give simple characterizations of multihead two-way finite automata in terms of pushdown and checking stack automata. (2) if [Equation ommitted] where [Equation ommitted] then Z is not changed. We remark that both classes of DPDA's, Le, FMS-DPDA's and SSR-DPDA's, can be put into this normal form in such a manner that the resulting machines remain in the same subclass, See [ltf,12,23] for the technique involved. The checking stack autornata(CSA's) are similar to PDA's, but once a symbol is written on the stack it cannot be erased. A CSA's stack head may, however, enter the stack, but once this has been done the CSA loses the capability to write additional sym-bols on the stack. A "simple" 2-way checking stack autornaton(S-CSA) is a CSA with an additional res-triction that once the input head turns (makes a reversal) , the machine loses the abil-ity to write an the stack (as it does when the stack head enters the stack). It can be shown that S-CSA's are equivalent to CSA's and they accept exactly the context sensi-tive languages[10]. It is open whether deterministic CSA's (DCSA) and S-DCSA's are equivalent. We assume that all S-DCSA's we are going to study in this paper are normal-ized as follows: (1) There is no a-mode writing, i.e. the input head moves for each write operation. (2) The stack grows by 1 for each stacking operation. Given a S-lJCSA it can be normalized using. similar techniques as were used with the DPDA's.

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

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Space and Time Efficient TM Simulations and Characterizations of Some Restricted Classes of Automata

Oscar H. Ibarra Sam M. Kim Louis E. Rosier

Computer Science Department Institute of Technology

1 36 Lind Hall University of Minnesota

Minneapolis, Minnesota 55455 Technical Report 83-1 January 1983

ABSTRACT

In this paper we present space/time efficient Turing machine algorithms for recognizing some subclasses of deterministic context-free languages. We also give simple characterizations of multihead two-way finite automata in terms of pushdown and checking stack automata. (2) if

(Equation Omitted)

where

(Equation Omitted)

then Z is not changed. We remark that both classes of DPDA's, Le, FMS-DPDA's and SSR- DPDA's, can be put into this normal form in such a manner that the resulting machines remain in the same subclass, See [ltf,12,23] for the technique involved. The checking stack autornata(CSA's) are similar to PDA's, but once a symbol is written on the stack it cannot be erased. A CSA's stack head may, however, enter the stack, but once this has been done the CSA loses the capability to write additional sym-bols on the stack. A "simple" 2-way checking stack autornaton(S-CSA) is a CSA with an additional res-triction that once the input head turns (makes a reversal) , the machine loses the abil-ity to write an the stack (as it does when the stack head enters the stack). It can be shown that S-CSA's are equivalent to CSA's and they accept exactly the context sensi-tive languages[10]. It is open whether deterministic CSA's (DCSA) and S-DCSA's are equivalent. We assume that all S-DCSA's we are going to study in this paper are normal-ized as follows: (1) There is no a-mode writing, i.e. the input head moves for each write operation. (2) The stack grows by 1 for each stacking operation. Given a S-lJCSA it can be normalized using. similar techniques as were used with the DPDA's.

1. A spaces and times ef6.cient simulation of FMS-3)PDA's

Following Igarashi [12J, let C W C' be a derivation, Let JCJ denote the stack height of configuration C. C; is said to be a stacking configuration in the derivation if and only if it is not followed by any configuration with stack height less than or equal to (G;) in the derivation. Suppose the machine takes t moves to get from a configuration C to C' while reading w (i.e. C 2~-C'). Then C; is a minimal stacking configuration in the derivation at

University of Minnesota Page 1 Dec 31, 1983

Page 2 of 13

Space and Time Efficient TM Simulations and Characterizations of Some Restricted Classes of Automata

-g- time t if and only if one of the following two conditions are met. (1) C; is the first stacking configuration in the derivation. (2) There is a configuration of height > JC;j between C; and the stacking configuration immediately preceding it in the derivation. Notice that during the computation C; may be a minimal stacking configuration at t...