Distributed Pushdown Automata Systems: Computational Power
- 300 Downloads
We introduce distributed pushdown automata systems consisting of several pushdown automata which work in turn on the input string placed on a common one-way input tape. The work of the components is based on protocols and strategies similar to those that cooperating distributed grammar systems use. We investigate the computational power of these mechanisms under different protocols for activating components and two ways of accepting the input string: with empty stacks or with final states which means that all components have empty stacks or are in final states, respectively, when the input string was completely read.
KeywordsComputation Mode Input String Step Move Language Class Reading Head
Unable to display preview. Download preview PDF.
- 1.M.H. ter Beek, E. Csuhaj-Varjú, V. Mitrana, Teams of pushdown automata, submitted.Google Scholar
- 3.E. Csuhaj-Varjú, J. Dassow, J. Kelemen, Gh. Päun, Grammar Systems. A grammatical approach to distribution and cooperation, Gordon and Breach, 1994.Google Scholar
- 5.J. Dassow, Gh. Pâaun, G. Rozenberg, Grammar systems, in vol. 2 of .Google Scholar