Paper Info
Title
Recording the use of memory in right-boundary grammars and push-down automata
Abstract
Within the framework of coordinated pair systems a push-down automaton A is formalized as an ordered pair (G1, G2) of grammars, where G1 is a right-linear grammar modelling the finite state control of A and the reading of the input of A, and G2 is a right-boundary grammar modelling the push-down store of A. In this paper we present a systematic investigation into the use of memory of right-boundary grammars. Various methods of recording the use of memory are introduced. The results presented concern regularity properties of each of the methods and the interrelationships of the records obtained by different methods. Finally the translation of these results to the level of push-down automata (coordinated pair systems) is discussed.
Year
DOI
Venue
1988
10.1007/BF00263585
Acta Inf.
Keywords
Field
DocType
Information System,Operating System,Data Structure,Communication Network,Information Theory
Tree-adjoining grammar,Deterministic context-free grammar,Context-sensitive grammar,Embedded pushdown automaton,Formal language,L-attributed grammar,Context-free grammar,Programming language,Computer science,Synchronous context-free grammar
Journal
Volume
Issue
ISSN
25
2
0001-5903
Citations 
PageRank 
References 
0
0.34
2
Authors
3
Name
Order
Citations
PageRank
A. Ehrenfeucht11823497.83
H. J. Hoogeboom2153.70
G. Rozenberg339645.34