Distributed Pushdown Automata Systems: Computational Power

  • Erzsébet Csuhaj-Varjú
  • Victor Mitrana
  • György Vaszil
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


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.


Computation Mode Input String Step Move Language Class Reading Head 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    M.H. ter Beek, E. Csuhaj-Varjú, V. Mitrana, Teams of pushdown automata, submitted.Google Scholar
  2. 2.
    E. Csuhaj-Varjú, J. Dassow, On cooperating distributed grammar systems, J. Inform. Process. Cybern., EIK, 26 (1990), 49–63.zbMATHGoogle Scholar
  3. 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
  4. 4.
    E. Csuhaj-Varjú, C. Martín-Vide, V. Mitrana, Gy. Vaszil, Parallel communicating pushdown automata systems, Intern. J. Found. Comp. Sci., 11:4 (2000), 633–650.zbMATHGoogle Scholar
  5. 5.
    J. Dassow, Gh. Pâaun, G. Rozenberg, Grammar systems, in vol. 2 of [12].Google Scholar
  6. 6.
    J. Dassow, V. Mitrana, “Stack cooperation in multi-stack pushdown automata”, J. Comput. System Sci. 58 (1999), 611–621.zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    O. H. Ibarra, One two-way multihead automata, J. Comput. System Sci. 7 (1973), 28–36.zbMATHMathSciNetGoogle Scholar
  8. 8.
    C. Martín-Vide, V. Mitrana, Some undecidable problems for parallel communicating finite automata systems, Inform. Proc. Letters, 77:5–6 (2001), 239–245.zbMATHCrossRefGoogle Scholar
  9. 9.
    C. Martín-Vide, V. Mitrana, Parallel communicating automata systems. A survey. Invited article in Korean Journal of Computational and Applied Mathematics, 7:2 (2000), 237–257.zbMATHGoogle Scholar
  10. 10.
    C. Martín-Vide, A. Mateescu, V. Mitrana, Parallel finite automata systems communicating by states, Intern. J. Found. Comp. Sci., 13:5 (2002), 733–749.zbMATHCrossRefGoogle Scholar
  11. 11.
    Gh. Pâun, L. Sântean, Parallel communicating grammar systems: the regular case, Ann. Univ. Bucharest, Ser. Matem.-Inform. 38 (1989), 55–63.zbMATHGoogle Scholar
  12. 12.
    G. Rozenberg, A. Salomaa, Handbook of Formal Languages, Springer-Verlag, Berlin, vol. 1–3, 1997.zbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Erzsébet Csuhaj-Varjú
    • 1
  • Victor Mitrana
    • 2
    • 3
  • György Vaszil
    • 1
  1. 1.Computer and Automation Research InstituteHungarian Academy of SciencesBudapestHungary
  2. 2.Faculty of Mathematics and Computer ScienceUniversity of BucharestBucharestRomania
  3. 3.Research Group in Mathematical LinguisticsRovira i Virgili UniversityTarragonaSpain

Personalised recommendations