Projekt : Nebenläufige Automatenmodelle

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)

[Forschung] [TGI] [Informatik]