Alternating tree automata
type: Item
instance of: scholarly article
title: Alternating tree automata
zbMATH Open document ID: 0595.68050
DOI: 10.1016/0304-3975(85)90077-5
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: The concept of alternation has been introduced by Chandra, Stockmeyer and Kozen as a natural extension of the concept of nondeterminism. The effect of alternation has been studied in the context of computational complexity, automata theory, algebra, dynamic logic and combinatorial games. This paper discusses the effect of alternation on several varieties of tree automata. In the case of top-down tree automata, alternation turns out to be equivalent to nondeterminism. In the case of two-way tree automata, alternation turns out to be more powerful than nondeterminism and alternating two-way tree automata define exactly RECOG, the class of recognizable tree languages. When the two-way tree automata are also equipped with a synchronized pushdown facility, then the alternating version is equivalent to the deterministic one.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3958738
zbMATH Keywords: alternation
zbMATH Keywords: nondeterminism
zbMATH Keywords: recognizable tree languages
author: Giora Slutzki
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90077-5
OpenAlex ID: W2115587183
cites work: Alternation
cites work: Tree acceptors and some of their applications
cites work: Q4954439
cites work: Bottom-up and top-down tree transformations— a comparison
cites work: Tree transducers, L systems, and two-way machines
cites work: Complexity of Boolean algebras
cites work: Q3662632
cites work: Classes of Pebble Games and Complete Problems
cites work: Parallel and two-way automata on directed ordered acyclic graphs
cites work: Probabilistic tree automata and context free languages
cites work: Q5583072
cites work: Provably Difficult Combinatorial Games
cites work: Generalized finite automata theory with an application to a decision problem of second-order logic
Recommended article: Q3813317
Recommended article: Alternating automata on infinite trees
Recommended article: Alternating two-way AC-tree automata
Recommended article: Q3323279
Recommended article: Q5418248
Recommended article: Q4036177
Recommended article: Q3306921
Recommended article: Alternating Tree Automata and Parity Games
Recommended article: Alternating register automata on finite words and trees
Recommended article: Iterative tree automata
description: scientific article; zbMATH DE number 3958738