TGI

• Heimatseite
• Ankündigungen
• Mitarbeiterinnen und Mitarbeiter
• Studentinnen und Studenten

Lehre

• Lehre
• Abschlussarbeiten

Forschung

• Forschung
• Publikationen

Misc

• Service
• Tools
• Petri Nets World
  

Projekt : Nebenläufige Automatenmodelle

Prof. Dr. Jantzen, Professor im Ruhestand
Prof. Dr. Kudlek, Professor
Dr. Berndt Farwer , ehemaliger Wissenschaftlicher Mitarbeiter
Dr. Heiko Rölke, ehemaliger Wissenschaftlicher Mitarbeiter
Patrick Totzke, Student
Georg Zetzsche, Student

Laufzeit: seit 2006

Schlagworte: Petrinetze, Automatenmodelle, Nebenläufigkeit

Ziele: Das Projekt baut auf der Idee auf, Petrinetze als endliche Kontrolle zur Steuerung von Automatenmodellen zu benutzen. Die Netze ersetzen dabei die ansonsten üblichen endlichen Automaten. Das besondere an den neu definierten Automaten ist, dass sie nebenläufig arbeiten können.

Als erstes Modell wurde eine nebenläufige Turingmaschine (concurrent Turing machine, CTM) definiert. Diese ist gleichmächtig zur üblichen Turingmaschine, weist aber für spezifische Probleme bessere Komplexitätsmaße auf.

Aktuell bearbeitet wird ein nebenläufiger endlicher Automat (concurrent finite automaton, CFA). CFA's ist mächtiger als endliche Automaten. CFA's können kontextsensitive Sprachen akzeptieren. Die von CFA's akzeptierten Sprachmengen sind sogar echt größer als die von Petrinetzen akzeptierten Sprachen.

Publikationen:

1. Berndt Farwer, Manfred Kudlek, Heiko Rölke
   Petri-Net-Controlled Machine Models
   (FBI-Bericht 274/06, 18 p., X 2006)
2. Berndt Farwer, Manfred Kudlek, Heiko Rölke
   Concurrent Turing Machines as Rewrite Theories
   (Proc. CS&P'2006, eds. G. Lindemann, H. Schlingloff, H.-D. Burkhard, L. Czaja, W. Penczek, A. Salwicky, A. Skowron, Z. Suraj, Humboldt-Universität zu Berlin, Informatik-Bericht Nr. 206,Vol. 3 Programming, pp. 352-363, 2006)
3. Berndt Farwer, Manfred Kudlek, Heiko Rölke
   Concurrent Turing Machines
   (FI vol. 79 (3-4), pp. 303-317, 2007)
4. Berndt Farwer, Matthias Jantzen, Manfred Kudlek, Heiko Rölke, Georg Zetzsche
   On Concurrent Finite Automata
   (Proc. CS&P'2007, ed. L. Czaja, vol. 1, pp. 180-190, 2007)
5. Matthias Jantzen, Manfred Kudlek, Georg Zetzsche
   On Languages Accepted by Concurrent Finite Automata
   (Proc. CS&P'2007, ed. L. Czaja, pp. 321-332, 2007)
6. Matthias Jantzen, Manfred Kudlek, Georg Zetzsche
   Finite Automata Controlled by Petri Nets
   (Proc. 14. Workshop AWPN, eds. S. Philippi, A. Pinl, Arbeitsbericht aus dem FB Informatik 25/2007, Univ. Koblenz-Landau, pp. 57-62, 2007)
7. Matthias Jantzen, Manfred Kudlek, Georg Zetzsche
   Concurrent Finite Automata
   (Tagungsband 17. Theorietag Automaten und Formale Sprachen, ed. M. Droste, pp. 84-88, 2007)
8. Berndt Farwer, Matthias Jantzen, Manfred Kudlek, Heiko Rölke, Georg Zetzsche
   Petri Net Controlled Finite Automata
   (FI, vol. 85 (1-4), pp. 111-121, 2008)
9. Matthias Jantzen, Manfred Kudlek, Georg Zetzsche
   Language Classes Defined by Concurrent Finite Automata
   (FI, vol. 85 (1-4), pp. 267-280, 2008)
10. Manfred Kudlek, Patrick Totzke, Georg Zetzsche
    Multiset Storage Automata
    (Proc. of CS&P'2008, eds. G. Lindemann, H.-D. Burkhard, L. Czaja, W. Penczek, A. Salwicky, H. Schlingloff, A. Skowron, Z. Suraj, Humboldt-Universität zu Berlin, Informatik-Bericht Nr. 225, vol 2, pp. 265-277, 2008)
11. Manfred Kudlek, Patrick Totzke, Georg Zetzsche
    Properties of Multiset Language Classes Defined by Multiset Storage Automata
    (Proc. of CS&P'2008, eds. G. Lindemann, H.-D. Burkhard, L. Czaja, W. Penczek, A. Salwicky, H. Schlingloff, A. Skowron, Z. Suraj, Humboldt-Universität zu Berlin, Informatik-Bericht Nr. 225, vol 2, pp. 278-288, 2008)
12. Manfred Kudlek, Georg Zetzsche
    Concurrent Finite Automata and Related Language Classes
    (Preproc. AFLAS, 4 p., 2008)
13. Manfred Kudlek, Patrick Totzke, Georg Zetzsche
    Multiset Pushdown Automata
    (FI, vol. 93 (1-3), pp. 221-233, 2009)
14. Manfred Kudlek, Patrick Totzke, Georg Zetzsche
    Properties of Multiset Language Classes Defined by Multiset Pushdown Automata
    (FI, vol 93, (1-3), pp. 235-244, 2009)
15. Manfred Kudlek, Patrick Totzke
    On a Hierarchy of Multiset Automata
    (Proc. CS{\&}P 2009, eds. L. Czaja, M. Szczuka, vol 1, pp. 327-336, 2009)