Projekt : Generatoren durchschnitts- und twistabgeschlossener Trios

Laufzeit: seit 09/1996

Schlagworte: Zählerautomaten; Sprachen, formale; AFL-Theorie; Twist- und Durchschnittsabschluss

Ziele:

Durchschnittsabgeschlossene Trios bilden eine echte Hierarchie unendlich vieler Haupt-Trios mit Generatoren bezüglich der Trio-Operationen. Sie können einen einzigen Generator nur dann besitzen, wenn zu den Trio-Operationen noch eine weitere hinzugenommen werden darf. In dem Projekt wurde gezeigt, dass die einstellige twist-Operation in Fällen komplizierter Generatoren die zweistellige Durchschnittsoperation ersetzen kann! Bei 'blinden' und 'umkehrbeschränkten' Zählerautomaten kann dies nicht gelingen, denn diese Familien sind twist-abgeschlossen. Man erhält die neue und feinere Hierarchie der Familien (b, r)-BRBC von Zählersprachen, die von Zählerautomaten mit b 'blinden' und r 'umkehrbeschränkten' Zählern akzeptiert werden. Die neuen Ergebnisse konnten unter Anwendung der linearen Algebra erreicht werden. Sie wurden auf der STACS'2001 in Dresden vorgetragen und in internationaler Zeitschrift nach weiterer Überarbeitung im Jahr 2003 publiziert.

Publikationen:

2003

Matthias Jantzen and Alexy Kurganskyy.
Refining the hierarchy of Blind Multicounter languages and Twist-Closed Trios.
Information and Computation, 185(2):159-181, 2003.

2001

Matthias Jantzen and Alexy Kurganskyy.
Refining the hierarchy of blind multicounter languages.
Bericht des Fachbereichs Informatik FBI-HH-B- 229/01, Universität Hamburg, Fachbereich Informatik, Vogt-Kölln Str. 30, D-22527 Hamburg, 2001.

Matthias Jantzen and Alexy Kurganskyy.
Refining the hierarchy of blind multicounter languages.
In Afonso Ferreira and Horst Reichel, editors, Proceedings of the18th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2001, Dresden, Germany, February 15-17, 2001), volume 2010 of Lecture Notes in Computer Science, pages 376-387, Berlin, Heidelberg, New York, 2001. Springer-Verlag.

1998

Matthias Jantzen.
Hierarchies of principal twist-closed trios.
In Michel Morvan, Christoph Meinel, and Daniel Krob, editors, Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 98, Paris, France, February 25-27, 1998), volume 1373 of Lecture Notes in Computer Science, pages 344-355, Berlin, Heidelberg, New York, 1998. Springer-Verlag.