Project : Language, Automata, and Complexity Theory

Duration: since 1975

Keywords: Sprachtheorie, Petrinetz-Sprachen, Multiset-Sprachen, Step Sequence, Automatentheorie, Berechenbarkeitstheorie, universelle Maschinen, nebenläufige Automatenmodelle, Quantenrechner, Komplexitätstheorie, Boolesche Hierarchie, polynomielle Hierarchie, Graphentheorie

Objectives: Die Theorie der formalen Sprachen und die Automatentheorie sind ein wichtiges Werkzeug der Berechenbarkeits- und der Komplexitätstheorie. Sie helfen uns, besser zu verstehen, welche Möglichkeiten verschiedene Modelle für Berechenbarkeit haben und welchen Grenzen sie unterliegen. In der Komplexitätstheorie werden ganze Klassen von Problemen, die von den verschiedenen Berechenbarkeitsmodellen gelöst werden können, bzgl. verschiedener Ressourcen untersucht, wobei insb. die Beziehungen zwischen diesen Klassen von Interesse sind.

In unterschiedlichen Teilprojekten wurden und werden am Arbeitsbereich TGI eine Vielzahl von Formalismen und Fragestellungen untersucht. Dazu gehören u.a. Struktureigenschaften formaler Sprachen, Petrinetz- und Multiset-Sprachen, universelle Maschinen, nebenläufige Automatenmodelle und Quantenrechner.

Die Modellierungsstärke von parallelen Systemen wurde an Hand von Petrinetzen und durch Sprachklassenvergleiche untersucht. Neue Sprachfamilien ergaben sich durch Variationen des streng parallelen Schaltens mehrerer Transitionen.

Um die (Abschluss-) Eigenschaften von speziellen Multiset-Sprachen genauer zu untersuchen, wurden unterschiedliche Automatenmodelle eingeführt und auf ihre Ausdrucksmächtigkeit und alternativen Charakterisierungen untersucht.

In der Komplexitätstheorie werden aktuell insb. die Boolesche und die polynomielle Hierarchie genauer untersucht. Speziell werden Probleme auf Graphen untersucht, um so mehr über die höheren Stufen der polynomiellen Hierarchie zu erfahren.

• Hierarchien rekursiver Klassen gefärbter Petrinetze (German only)
• Definition formaler Sprachen über Rekurrenzgleichungen (German only)
• Abschlusseigenschaften rationaler Mengen über kommutativen Monoiden (German only)
• Fundamental Algebraic Structures of Concurrency
• Structures of Formal Languages
• General Characterization of Language Classes and Derivation Systems
• Small Universal Turing Machines
• Parsing and Compilers
• Multiset Languages
• Problems of Quantum Computing
• Concurrent Automata Models

Publications: (seit 2008; für ältere Publikationen siehe Teilprojekte oben)

2011

Michael Köhler-Bußmeier and Frank Heitmann.
Liveness of safe object nets.
Fundamenta Informaticae, 112(1):73-87, 2011.

Michael Köhler-Bußmeier and Frank Heitmann.
Restricting generalised state machines.
In Marcin Szczuka, Ludwik Czaja, Andrzej Skowron, and Magdalena Kacprzak, editors, Proceedings of the International Workshop on Concurrency, Specification, and Programming (CS&P 2011). Biaystok University of Technology, 2011.

2010

Michael Köhler-Bußmeier and Frank Heitmann.
Complexity of LTL model-checking for safe object nets.
In B. Farwer, editor, Proceedings of the International Workshop on Logic, Agents, and Mobilitty (LAM 2010), 2010.

2009

Manfred Kudlek, Patrick Totzke, and Georg Zetzsche.
Multiset pushdown automata.
Fundamenta Informaticae, 93(1-3):221-233, 2009.

Manfred Kudlek, Patrick Totzke, and Georg Zetzsche.
Properties of multiset language classes defined by multiset pushdown automata.
Fundamenta Informaticae, 93(1-3):235-244, 2009.

Manfred Kudlek.
Some considerations on universality.
EPTCS, (1):118-122, 2009.

Ludwik Czaja and Manfred Kudlek.
Analysis and synthesis of net structures and transition graphs.
Fundamenta Informaticae, 93(1-3):97-110, 2009.

Manfred Kudlek and Patrick Totzke.
On a hierarchy of multiset automata.
In Ludwik Czaja, editor, Concurrency, Specification, and Programming. Workshop CS&P 2009, Kraków-Przegorzay, Poland. Proceedings, volume 1, pages 327-336, September 2009.  [link]

Manfred Kudlek.
On closure properties of sentential form language classes of words.
In Ludwik Czaja, editor, Concurrency, Specification, and Programming. Workshop CS&P 2009, Kraków-Przegorzay, Poland. Proceedings, volume 1, pages 315-326, September 2009.  [link]

Manfred Kudlek and Ludwik Czaja.
On synthesis and analysis of net structures and transition graphs.
In Ludwik Czaja, editor, Concurrency, Specification, and Programming. Workshop CS&P 2009, Kraków-Przegorzay, Poland. Proceedings, volume 1, pages 127-133, September 2009.  [link]

Georg Zetzsche.
Erasing in Petri net languages and matrix grammars.
In Volker Diekert and Dirk Nowotka, editors, Developments in Language Theory, 13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Proceedings, volume 5583 of Lecture Notes in Computer Science, pages 490-501, 2009.

Georg Zetzsche.
A note on Hack's Conjecture, Parikh images of matrix languages and multiset grammars.
Bericht des Fachbereichs Informatik FBI-HH-B-289/09, Universität Hamburg, Department Informatik, Vogt-Kölln Str. 30, D-22527 Hamburg, Germany, 2009.  [pdf]

2008

Berndt Farwer, Matthias Jantzen, Manfred Kudlek, Heiko Rölke, and Georg Zetzsche.
Petri net controlled finite automata.
Fundamenta Informaticae, 85(1-4):111-121, 2008.

Frank A. Heitmann.
Steinerbäume im Erreichbarkeitsgraphen von Petrinetzen.
Baccalaureats-arbeit, Universität Hamburg, Department Informatik, Vogt-Kölln Str. 30, D-22527 Hamburg, March 2008.

Matthias Jantzen, Manfred Kudlek, and Georg Zetzsche.
Language classes defined by concurrent finite automata.
Fundamenta Informaticae, 85(1-4):267-280, 2008.

Matthias Jantzen and Georg Zetzsche.
Labeled step sequences in Petri nets.
In Kees M. van Hee and Rüdiger Valk, editors, Applications and Theory of Petri Nets, 29th International Conference, PETRI NETS 2008, Xi'an, China, June 23-27, 2008. Proceedings, volume 5062 of Lecture Notes in Computer Science, pages 270-287, Berlin, Heidelberg, New York, 2008. Springer-Verlag.

Michael Köhler-Bußmeier and Frank Heitmann.
On the expressiveness of communication channels for object nets.
In G. Lindemann, H.-D. Burkhard, L. Czaja, W. Penczek, A. Salwicki, H. Schlingloff, A. Skowron, and Z. Suraj, editors, Proceedings of the International Workshop on Concurrency, Specification, and Programming CS&P 2008 (Volume 2), pages 253-264. Humboldt-Universität zu Berlin, Informatik-Berichte 225, 2008.  [link]

Manfred Kudlek, Patrick Totzke, and Georg Zetzsche.
Multiset storage automata.
In H.-D. Burkhard, Ludwik Czaja, G. Lindemann, and A. Skowron, editors, Proceedings of the Workshop CS&P'2008, volume 2, pages 265-277, September 2008.  [pdf]  [link]

Manfred Kudlek, Patrick Totzke, and Georg Zetzsche.
Properties of multiset language classes defined by multiset storage automata.
In H.-D. Burkhard, Ludwik Czaja, G. Lindemann, and A. Skowron, editors, Proceedings of the Workshop CS&P'2008, volume 2, pages 278-288, September 2008.  [pdf]  [link]

Manfred Kudlek and Benedek Nagy.
Distances of formal languages.
Pure Mathematics and Applications - PU.MA, 17(3-4):349-357, 2008.  [link]

Manfred Kudlek and Ludwik Czaja.
Synthesis and analysis of net structures and transition graphs.
In H.-D. Burkhard, Ludwik Czaja, G. Lindemann, and A. Skowron, editors, Proceedings of the Workshop CS&P'2008, volume 1, pages 93-107, September 2008.  [link]

Manfred Kudlek.
Some considerations on universality.
In Turlough Neary, Damien Woods, Anthony Karel Seda, and Niall Murphy, editors, Complexity of Simple Programs, CSP 2008, Cork, Ireland. Proceedings, pages 149-156. Cork University Press, December 2008.