The theory of ends, pushdown automata, and second-order logic.

*(English)*Zbl 0605.03005In 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.

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.

Reviewer: A.A.Mullin

##### MSC:

03B25 | Decidability of theories and sets of sentences |

03D10 | Turing machines and related notions |

68R10 | Graph theory (including graph drawing) in computer science |

05B45 | Combinatorial aspects of tessellation and tiling problems |

68Q80 | Cellular automata (computational aspects) |

68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |

##### Keywords:

pushdown automata; finiteness; automata theory of ends; infinity; context-free graphs; transition graph; Cayley graphs of context-free groups; decidable monadic second-order theory; decision problems; tiling systems; cellular automata; membership problem; inclusion problem; reachability sets of vector addition systems
PDF
BibTeX
XML
Cite

\textit{D. E. Muller} and \textit{P. E. Schupp}, Theor. Comput. Sci. 37, 51--75 (1985; Zbl 0605.03005)

Full Text:
DOI

##### References:

[1] | Cohen, D.E., Groups of cohomological dimension one, () · Zbl 0231.20018 |

[2] | Elgot, C.C.; Rabin, M.O., Decidability and undecidability of extensions of the second-order theory of successor, J. symbolic logic, 31, 169-181, (1966) · Zbl 0144.24501 |

[3] | Hack, M., The equality problem for vector addition systems is undecidable, Theoret. comput. sci., 2, 77-96, (1978) · Zbl 0357.68038 |

[4] | Harrison, M.A., Introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058 |

[5] | Hopcroft, J.E.; Ullman, J.D., Introduction to automation theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701 |

[6] | Muller, D.E.; Schupp, P.E., Pushdown automata, ends, second-order logic and reachability problems, (), 46-54 |

[7] | Muller, D.E.; Schupp, P.E., Groups, the theory of ends and context-free languages, J. comput. system sci., 26, 3, 295-310, (1983) · Zbl 0537.20011 |

[8] | Rabin, M., Decidability of second-order theories and automata on infinite trees, Trans. amer. math. soc., 141, 1-35, (1969) · Zbl 0221.02031 |

[9] | Stallings, J., Group theory and three-dimensional manifolds, (1971), Yale University Press New Haven, CT · Zbl 0241.57001 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.