Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
TCS Journal 1995 Journal Article
We give a proof that alternating tree automata can be simulated by nondeterministic tree automata which yields new complexity results and a unified proof of the theorems of Rabin, McNaughton and Safra. We also give a simple axiomatic framework for uniformizing strategies.
TCS Journal 1992 Journal Article
TCS Journal 1987 Journal Article
TCS Journal 1985 Journal Article
A class of edge-labeled graphs called context-free are defined according to their behavior at infinity. Such graphs are generalizations of Cayley graphs of context-free groups. They are also shown to be definable in a very natural way in terms of push-down automata. Using Rabin's theorem on the monadic second-order theory of the finite binary tree, these graphs are also shown to have a decidable monadic second-order theory. Questions about tiling systems and cellular automata operating on these graphs are decidable even when the analogous questions are not, when the systems operate on a two-dimensional grid.
STOC Conference 1981 Conference Paper
We have discovered a very strong connection between certain areas of theoretical computer science—the theory of context-free languages and pushdown automata, tiling problems, cellular automata, and vector addition systems—and certain concepts from group theory, topology, and second-order logic. We use these concepts to investigate a rather wide class of graphs which we call context-free graphs. Using the results obtained and Rabin's theorem that the monadic second-order theory of the infinite binary tree is decidable, we are able to show that the monadic second-order theory of any context-free graph is decidable. Cellular automata and vector addition systems are usually considered as involving the grid of integer lattice points in n-dimensional space. We show that such systems make sense on a very general class of graphs and, in contrast to the classical case, all the relevant algorithmic problems concerning such systems are solvable on context-free graphs.