CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store⋆⋆⋆

Benedek Nagy; Friedrich Otto

RAIRO - Theoretical Informatics and Applications (2012)

  • Volume: 45, Issue: 4, page 413-448
  • ISSN: 0988-3754

Abstract

top
We study cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are equipped with an external pushdown store. In this way we obtain an automata-theoretical characterization for the class of word languages that are linearizations of context-free trace languages.

How to cite

top

Nagy, Benedek, and Otto, Friedrich. "CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store⋆⋆⋆." RAIRO - Theoretical Informatics and Applications 45.4 (2012): 413-448. <http://eudml.org/doc/222042>.

@article{Nagy2012,
abstract = {We study cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are equipped with an external pushdown store. In this way we obtain an automata-theoretical characterization for the class of word languages that are linearizations of context-free trace languages.},
author = {Nagy, Benedek, Otto, Friedrich},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Restarting automaton; cooperating distributed system; external pushdown; context-free trace language; restarting automaton},
language = {eng},
month = {1},
number = {4},
pages = {413-448},
publisher = {EDP Sciences},
title = {CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store⋆⋆⋆},
url = {http://eudml.org/doc/222042},
volume = {45},
year = {2012},
}

TY - JOUR
AU - Nagy, Benedek
AU - Otto, Friedrich
TI - CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store⋆⋆⋆
JO - RAIRO - Theoretical Informatics and Applications
DA - 2012/1//
PB - EDP Sciences
VL - 45
IS - 4
SP - 413
EP - 448
AB - We study cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are equipped with an external pushdown store. In this way we obtain an automata-theoretical characterization for the class of word languages that are linearizations of context-free trace languages.
LA - eng
KW - Restarting automaton; cooperating distributed system; external pushdown; context-free trace language; restarting automaton
UR - http://eudml.org/doc/222042
ER -

References

top
  1. I. Aalbersberg and G. Rozenberg, Theory of traces. Theoret. Comput. Sci.60 (1988) 1–82.  Zbl0652.68017
  2. J. Autebert, J. Berstel and L. Boasson, Context-free languages and pushdown automata, in Handbook of Formal Languages, Word, Language, Grammar, edited by G. Rozenberg and A. Salomaa. 1 (1997) 111–174.  
  3. J. Berstel, Transductions and Context-Free Languages, Leitfäden der angewandten Mathematik und Mechanik38 (1979).  
  4. A. Bertoni, G. Mauri and N. Sabadini, Membership problems for regular and context-free trace languages. Inform. Comput.82 (1989) 135–150.  Zbl0682.68040
  5. H. Bordihn, M. Holzer and M. Kutrib, Input reversals and iterated pushdown automata: a new characterization of Khabbaz geometric hierarchy of languages, in Proc. of DLT 2004, edited by C.S. Calude, E. Calude and M.J. Dinneen. Lect. Notes Comput. Sci.3340 (2004) 102–113.  Zbl1117.68394
  6. P. Cartier and D. Foata, Problèmes Combinatoires de Commutation et Réarrangements. Lect. Notes Comput. Sci.85 (1969).  Zbl0186.30101
  7. E. Csuhaj-Varjú, J. Dassow, J. Kelemen and G. Păun, Grammar Systems. A Grammatical Approach to Distribution and Cooperation, edited by Gordon and Breach. London (1994).  Zbl0925.68286
  8. E. Csuhaj-Varjú, C. Martín-Vide and V. Mitrana, Multiset automata, in Multiset Processing, edited by C.S. Calude, G. Păun, G. Rozenberg and A. Salomaa. Lect. Notes Comput. Sci.2235 (2001) 69–83.  Zbl1052.68071
  9. V. Diekert and G. Rozenberg Eds., The Book of Traces. World Scientific, Singapore (1995).  
  10. B. Genest, H. Gimbert, A. Muscholl and I. Walukiewicz, Optimal Zielonka-type construction of deterministic asynchronous automata, in Proc. of ICALP 2010, Part. II, edited by S. Abramsky, C. Gavoille, C. Kircher, F. Meyer auf der Heide and P.G. Spirakis. Lect. Notes Comput. Sci.6199 (2010) 52–63.  
  11. M. Harrison, Introduction to Formal Language Theory. Addison-Wesley, Reading, MA (1978).  Zbl0411.68058
  12. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979).  Zbl0426.68001
  13. P. Jančar, F. Mráz, M. Plátek and J. Vogel, Restarting automata, in Proc. of FCT 1995, edited by H. Reichel. Lect. Notes Comput. Sci.965 (1995) 283–292.  
  14. P. Jančar, F. Moller and Z. Sawa, Simulation problems for one-counter machines, in Proc. of SOFSEM’99, edited by J. Pavelka, G. Tel and M. Bartošek. Lect. Notes Comput. Sci.1725 (1999) 404–413.  Zbl0963.68094
  15. M. Kudlek, P. Totzke and G. Zetzsche, Multiset pushdown automata. Fund. Inform.93 (2009) 221–233.  Zbl1191.68392
  16. M. Kutrib, H. Messerschmidt and F. Otto, On stateless two-pushdown automata and restarting automata, in Proc. of AFL 2008, edited by E. Csuhaj-Varjú and Z. Ésik. Hungarian Academy of Sciences (2008) 257–268.  Zbl1207.68193
  17. M. Kutrib, H. Messerschmidt and F. Otto, On stateless two-pushdown automata and restarting automata. Int. J. Found. Comput. Sci.21 (2010) 781–798.  Zbl1207.68193
  18. A. Mazurkiewicz, Concurrent program schemes and their interpretations, DAIMI Rep. PB. Aarhus University, Aarhus 78 (1977).  
  19. H. Messerschmidt and F. Otto, Cooperating distributed systems of restarting automata. Int. J. Found. Comput. Sci.18 (2007) 1333–1342.  Zbl1183.68347
  20. H. Messerschmidt and F. Otto, On deterministic CD-systems of restarting automata. Int. J. Found. Comput. Sci.20 (2009) 185–209.  Zbl1170.68505
  21. B. Nagy and F. Otto, CD-systems of stateless deterministic R(1)-automata accept all rational trace languages, in Proc. of LATA 2010, edited by A.H. Dediu, H. Fernau and C. Martin-Vide. Lect. Notes Comput. Sci.6031 (2010) 463–474.  Zbl1284.68363
  22. B. Nagy and F. Otto, On CD-systems of stateless deterministic R-automata with window size one. Kasseler Informatikschriften, Fachbereich Elektrotechnik/Informatik, Universität Kassel (2010).  Zbl1279.68167URIhttps://kobra.bibliothek.uni-kassel.de/handle/urn:nbn:de:hebis:34-2010042732682
  23. B. Nagy and F. Otto, An automata-theoretical characterization of context-free trace languages, in Proc. of SOFSEM 2011: Theory and Practice of Computer Science, edited by I. Černá, T. Gyimóthy, J. Hromkovič, K. Jefferey, R. Královič, M. Vukolič and S. Wolf. Lect. Notes Comput. Sci.6543 (2011) 406–417.  Zbl1298.68152
  24. B. Nagy and F. Otto, Finite-state acceptors with translucent letters, in Proc. of BILC 2011: AI Methods for Interdisciplinary Research in Language and Biology, edited by G. Bel-Enguix, V. Dahl and A.O. De La Puente. SciTePress, Portugal (2011) 3–13.  
  25. F. Otto, Restarting automata, in Recent Advances in Formal Languages and Applications, Studies in Computational Intelligence, edited by Z. Ésik, C. Martin-Vide and V. Mitrana. 25 (2006) 269–303.  
  26. W. Zielonka, Note on finite asynchronous automata. RAIRO–Inf. Theor. Appl.21 (1987) 99–135.  Zbl0623.68055

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.