The theory of ends, pushdown automata, and second-order logic
type: Item
instance of: scholarly article
title: The theory of ends, pushdown automata, and second-order logic
zbMATH Open document ID: 0605.03005
DOI: 10.1016/0304-3975(85)90087-8
author: David E. Muller
author: Paul E. Schupp
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: In this carefully written paper the authors give detailed graph-theoretic proofs of several interesting finiteness results in the automata theory of ends, which deals with well behaved ways of going to infinity. Their approach is to define a broad class of graphs called ''context-free graphs''. Basically, the underlying idea is that a context-free graph is well behaved at infinity. The bottom line is that a graph is context-free iff it is the complete transition graph of some pushdown automaton. Such graphs are generalizations of Cayley graphs of context-free groups. Using Rabin's theorem on the decidability of monadic second-order theory for the infinite binary tree, such graphs have also a decidable monadic second-order theory. Solvable decision problems about tiling systems and cellular automata are discussed in great detail. Finally, the authors show that the membership problem and the inclusion problem for reachability sets of vector addition systems on a context- free graph are uniformly solvable.
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05B45
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 68Q85
zbMATH DE Number: 3976992
zbMATH Keywords: pushdown automata
zbMATH Keywords: finiteness
zbMATH Keywords: automata theory of ends
zbMATH Keywords: infinity
zbMATH Keywords: context-free graphs
zbMATH Keywords: transition graph
zbMATH Keywords: Cayley graphs of context-free groups
zbMATH Keywords: decidable monadic second-order theory
zbMATH Keywords: decision problems
zbMATH Keywords: tiling systems
zbMATH Keywords: cellular automata
zbMATH Keywords: membership problem
zbMATH Keywords: inclusion problem
zbMATH Keywords: reachability sets of vector addition systems
reviewed by: Albert A. Mullin
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90087-8
OpenAlex ID: W1971416129
cites work: Groups of cohomological dimension one
cites work: Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
cites work: The equality problem for vector addition systems is undecidable
cites work: Q4198075
cites work: Q5592246
cites work: Groups, the theory of ends, and context-free languages
cites work: Decidability of Second-Order Theories and Automata on Infinite Trees
cites work: Q5651924
description: scientific article; zbMATH DE number 3976992