Tree pushdown automata
type: Item
instance of: scholarly article
title: Tree pushdown automata
zbMATH Open document ID: 0565.68080
DOI: 10.1016/0022-0000(85)90002-9
author: Karl M. Schimpf
author: Jean Gallier
published in: Journal of Computer and System Sciences
publication date: 1985-01-01T00:00:00Z
review text: The paper presents a new type of automata called tree pushdown automata. This type of automata operates in the same manner as standard bottom-up tree automata except that there is an internal memory consisting of a finite sequence of trees (called tree stack), where there is exactly one tree stack for each read head in a bottom-up tree automaton. The main result of the paper is: The class of context-free tree languages is identical with the class of languages accepted by tree pushdown automata. The method shown resemble the methods used to show the equivalence between context-free string grammars and pushdown automata. Some directions of future research are presented at the end of the paper.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3902073
zbMATH Keywords: tree pushdown automata
zbMATH Keywords: context-free tree languages
reviewed by: Gheorghe Grigoraş
MaRDI profile type: Publication
full work available at URL: 0022-0000(85)90002-9
OpenAlex ID: W1990748319
cites work: Nested Stack Automata
cites work: Optimization of LR(k) parsers
cites work: Q5545522
cites work: Tree acceptors and some of their applications
cites work: Syntactic methods in pattern recognition
cites work: Tree Systems for Syntactic Pattern Recognition
cites work: DPDA's in 'Atomic normal form' and applications to equivalence problems
cites work: Q5725062
cites work: Q3917489
cites work: Q4198075
cites work: A Class of Projective Planes
cites work: Parsing macro grammars top down
cites work: Mappings and grammars on trees
cites work: Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
cites work: Q5643969
cites work: Generalized finite automata theory with an application to a decision problem of second-order logic
description: scientific article; zbMATH DE number 3902073