Paul E. Schupp

TCS Journal 2015 Journal Article

Multipass automata and group word problems

• Tullio Ceccherini-Silberstein
• Michel Coornaert
• Francesca Fiorenzi
• Paul E. Schupp
• Nicholas W.M. Touikan

We introduce the notion of multipass automata as a generalization of pushdown automata and study the classes of languages accepted by such machines. The class of languages accepted by deterministic multipass automata is exactly the Boolean closure of the class of deterministic context-free languages while the class of languages accepted by nondeterministic multipass automata is exactly the class of poly-context-free languages, that is, languages which are the intersection of finitely many context-free languages. We illustrate the use of these automata by studying groups whose word problems are in the above classes.

TCS Journal 1998 Journal Article

On the structure of Hamiltonian cycles in Cayley graphs of finite quotients of the modular group

• Paul E. Schupp

It is a fairly longstanding conjecture that if G is any finite group with ¦G¦s > 2 and if X is any set of generators of G then the Cayley graph Γ(G: X) should have a Hamiltonian cycle. We present experimental results found by computer calculation that support the conjecture. It turns out that in the case where G is a finite quotient of the modular group the Hamiltonian cycles possess remarkable structural properties.

TCS Journal 1995 Journal Article

Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra

• David E. Muller
• Paul E. Schupp

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

Alternating automata, the weak monadic theory of trees and its complexity

• David E. Muller
• Ahmed Saoudi
• Paul E. Schupp

TCS Journal 1987 Journal Article

Alternating automata on infinite trees

• David E. Muller
• Paul E. Schupp

TCS Journal 1985 Journal Article

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

• David E. Muller
• Paul E. Schupp

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

Pushdown Automata, Graphs, Ends, Second-Order Logic, and Reachability Problems

• David E. Muller
• Paul E. Schupp

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.