Bachelor- und Masterarbeiten der FLDIT-Gruppe
  • INF-BSc-111 Bachelor-Abschluss-Modul --- INF-MSc-104 Master-Abschluss-Modul
  • 15 Credits - Bearbeitungszeit: 4 Monate
  • Themen
    • Syntax und Semantik aus bialgebraischer Sicht [50-52,?]
    • Model Checking parametrisierter Transitionssysteme [24,25,?]
    • Untersuchung und Haskell-Implementierung des coinduktiven Stromkalküls (abgeschlossen)
    • Techniken zum Beweis der Wohldefiniertheit, Produktivität und Gleichheit von Strömen (abgeschlossen)
    • Co/algebraische Minimierung von Automaten [45,46]
    • Grundlagen und Anwendungen co-logischer Programmierung (abgeschlossen)
    • Theorie und Anwendung des Konzepts der freien Theoreme über Haskell-Funktionen [13-17, tool] (in Arbeit)
    • Theorie und Anwendung des Konzepts der bidirektionalen Compilation [2,3,4,5]
    • Anwendungen monadischer Programmierung [6-9] (abgeschlossen)
    • Comonaden und ihre Anwendung in der funktionalen Programmierung [44,?] (in Arbeit)
    • Haskell-Implementierung universeller Konstruktionen der Kategorientheorie auf der Basis ausgewählter Kapitel von [10-12] (in Arbeit)
    • Co/Stetigkeit polynomialer Funktoren (Ausarbeitung des Beweises von Proposition 2.2 in [18,19])
    • Untersuchung und Haskell-Implementierung der coalgebraischen Modellierung von Mealy-Automaten und linearen Systemen [28-32] (abgeschlossen)
    • Untersuchung und Haskell-Implementierung der coalgebraischen Modellierung von nichtdeterministischen Systemen und Kripke-Strukturen [33-37]
    • Entwicklung co/algebraischer Modelle für UML und OCL auf Basis der Ansätze von [20-23] und [47-49] (abgeschlossen, kann aber mit neuem Schwerpunkt weiterbearbeitet werden)
    • Definition eines co/algebraischen Modells für XML-Bäume mit Links und Attributen, XPath-Funktionen und Baumverknüpfungen [25,?]
    • Co/algebraische Modellierung verschiedener Klassen von Petri-Netzen [26,27,?]
    • O'Haskell-Implementierung und Expander2-Anbindung eines kleinen Werkzeugkastens zur Erzeugung, Transformation und Verknüpfung elementarer 3D-Objekte [Expander2, OpenGL, delphigl] (Hier kann auf Vorarbeiten aufgebaut werden.
    • ghc-Implementierung der über klassisches Haskell hinausgehenden Konstrukte von O'Haskell, evtl. einschließlich der Tcl/Tk-Schnittstelle von O'Haskell oder einer neuen nach OpenGL
    • Haskell-Implementierung von Algorithmen der Bioinformatik und ggf. Vergleich mit Codierungen in anderen Sprachen [38-43, 1]
    • Für Nebenfach-Logistik-Studierende: Haskell-Implementierung logistischer Verfahren und ggf. Vergleich mit Codierungen in logischen Programmiersprachen, die in der FG Information Engineering des LS 1 in Zusammenarbeit mit dem Maschinenbau-Lehrstuhl FLW erstellt wurden
    • Analyse einer oder mehrerer Haskell-Bibliotheken für einen bestimmten Anwendungsbereich [53]
  • Literatur
    Zu vielen der o.g. Themen besteht die Bachelorarbeit in der Auseinandersetzung mit einem oder mehreren, dem jeweiligen Thema zugeordneten Artikeln, im Stil einer größeren Seminararbeit, ggf. ergänzt um einen Implementierungsteil und mit einem Gesamtumfang von 50 bis 60 Seiten.
    • 1 P. Padawitz, Übersetzerbau, TU Dortmund 2012
    • 2 K. Matsuda, Z. Hu, K. Nakano, M. Hamana and M. Takeichi, Bidirectionalization Transformation based on Automatic Derivation of View Complement Functions, Proc. Int. Conf. Functional Programming 2007, ACM Press, pages 47-58
    • 3 J. Voigtländer, Bidirectionalization for free!, Proc. Principles of Programming Languages 2009, SIGPLAN Notices 44, pages 165-176
    • 4 J. Voigtländer, Z. Hu, K. Matsuda, M. Wang, Combining Syntactic and Semantic Bidirectionalization, Proc. Int. Conf. Functional Programming 2010, SIGPLAN Notices 45, pages 181-192
    • 5 N. Foster, K. Matsuda, J. Voigtländer, Three Complementary Approaches to Bidirectional Programming, Spring School on Generic and Indexed Programming 2010
    • 6 T. Schrijvers, P. Stuckey, Ph. Wadler, Monadic constraint programming, Journal of Functional Programming 19 (2009), pages 663-697
    • 7 M. Erwig, S. Kollmansberger, Probabilistic functional programming in Haskell, Journal of Functional Programming 16 (2006), pages 21-34
    • 8 N. Ramsey, A. Pfeffer, Stochastic Lambda Calculus and Monads of Probability Distributions, Proc. Principles of Programming Languages 2002, SIGPLAN Notices 37, pages 154-165
    • 9 E. Kidd, Build your own probability monads, Dartmouth College, New Hampshire 2007
    • 10 R. Bird, O. de Moor, Algebra of Programming, Prentice Hall 1997
    • 11 R.F.C. Walters, Categories and Computer Science, Cambridge University Press 1992
    • 12 D.E. Rydeheard, R.M. Burstall, Computational Category Theory, Prentice Hall 1988
    • 13 J.C. Reynolds, Types, abstraction and parametric polymorphism, Proc. Information Processing 1983, Elsevier, pages 513-523
    • 14 Ph. Wadler, Theorems for free!, Proc. Functional Programming Languages and Computer Architecture 1989, ACM Press, pages 347-359
    • 15 J. Voigtländer, Concatenate, Reverse and Map Vanish For Free, Proc. Int. Conf. on Functional Programming 2002, SIGPLAN Notices 37, pages 14-25
    • 16 P. Johann, J. Voigtländer, Free Theorems in the Presence of seq, Proc. Principles of Programming Languages 2004, SIGPLAN Notices 39, pages 99-110
    • 17 J. Voigtländer, Proving Correctness via Free Theorems: The Case of the destroy/build-Rule, Proc. Partial Evaluation and Semantics-Based Program Manipulation 2008, ACM Press, pages 13-20
    • 18 M. Barr, Terminal coalgebras in well-founded set theory, Theoretical Computer Science 114 (1993), pages 299-315
    • 19 M. Barr, Terminal coalgebras for endofunctors on sets, McGill University, Montreal 1999
    • 20 S. Meng, B.K. Aichernig, Towards a Coalgebraic Semantics of UML, UNU/IIST Report 272, 2003;
      -, A Coalgebraic Calculus for Component-Based Systems, Proc. Formal Aspects of Component Software 2003, pages 27-46;
      -, Bringing class diagrams to life, Proc. Innovations in Systems and Software Engineering 6 (2010), pages 91-98
    • 21 S. Meng, L.S. Barbosa, A Coalgebraic Semantic Framework for Reasoning about UML Sequence Diagrams, Proc. IEEE Quality Software 2008, pages 17-26
    • 22 S. Meng, Z. Naixiao, L.S. Barbosa, On Semantics and Refinement of UML Statecharts: A Coalgebraic View, Proc. Software Engineering and Formal Methods 2004, pages 168-183
    • 23 L.S. Barbosa, S. Meng, Generic Components, Applied Semantics Workshop 2003, Nottingham
    • 24 R.P. Kurshan, K.L. McMillan, A Structural Induction Theorem for Processes, ACM 1989
    • 25 K.L. McMillan, Symbolic Model Checking, PhD thesis, CMU 1992
    • 26 P. Padawitz, Dialgebraic Specification and Modeling, TU Dortmund 2012
    • 27 P. Padawitz, Algebraic Model Checking and more, TU Dortmund 2011
    • 28 P. Padawitz, Swinging Types At Work, TU Dortmund 2008
    • 29 J. Rutten, Algebraic Specification and Coalgebraic Synthesis of Mealy Automata, Proc. Formal Aspects of Component Software 2005, ENTCS 160, Elsevier, pages 305-319
    • 30 H.H. Hansen, D. Costa, J. Rutten, Synthesis of Mealy Machines Using Derivatives, Proc. Coalgebraic Methods in Computer Science 2006, ENTCS 164, Elsevier, pages 27-45
    • 31 J. Rutten, Coalgebraic Foundations of Linear Systems, Proc. Algebra and Coalgebra in Computer Science 2007, LNCS 4624, Springer, pages 425-446
    • 32 M. Bonsangue, J. Rutten, A. Silva, Coalgebraic Logic and Synthesis of Mealy Machines, Proc. Foundations of Software Science and Computation Structures 2008, LNCS 4962, Springer, pages 231-245
    • 33 H.H. Hansen, J. Rutten, Symbolic Synthesis of Mealy Machines from Arithmetic Bitstream Functions, Scientific Annals of Computer Science 20 (2010), pages 97-130
    • 34 A. Silva, F. Bonchi, M. Bonsangue, J. Rutten, Generalizing the powerset construction, coalgebraically, Proc. IARCS Foundations of Software Technology and Theoretical Computer Science 2010, pages 272-283
    • 35 M. Bonsangue, J. Rutten, A. Silva, An algebra for Kripke polynomial coalgebras, Proc. IEEE Logic in Computer Science 2009, pages 49-58
    • 36 A. Silva, M. Bonsangue, J. Rutten, Kleene coalgebras, CWI Technical Report SEN-1001, 2010;
      -, Kleene Coalgebra - an overview, Nieuwsbrief van de Nederlandse Vereniging voor Theoretische Informatica 15, 2011
    • 37 F. Bonchi, M. Bonsangue, M. Boreale, J. Rutten, A. Silva, A coalgebraic perspective on linear weighted automata, Information and Computation 211 (2012), pages 77-105
    • 38 S. Rahmann, Algorithmen auf Sequenzen, TU Dortmund 2001
    • 39 P.F. Stadler, A Short Course on RNA Bioinformatics, Berlin 2009
    • 40 R. Giegerich, A Systematic Approach to Dynamic Programming in Bioinformatics, Bioinformatics 16 (2000), pages 665-677
    • 41 R. Giegerich, C. Meyer, Algebraic Dynamic Programming, Proc. Algebraic Methodology And Software Technology 2002, Springer, pages 349-364
    • 42 R. Giegerich, Introduction to Stochastic Context Free Grammars, in: J. Gorodkin, Z. Weinberg, RNA Bioinformatics, 2012
    • 43 T.L. Booth, R.A. Thompson, Applying Probability Measures to Abstract Languages, IEEE Transactions on Computers 22 (1973), pages 442-450
    • 44 Dominic Orchard
    • 45 F. Bonchi et al., Brzozowski's minimization algorithm (co)algebraically, ACM Transactions on Computational Logic, to appear
    • 46 M.A. Arbib, E.G. Manes, Machines in a Category, Journal of Pure and Applied Algebra 19 (1980), pages 9-20
    • 47 H. Reichel, An approach to object semantics based on terminal co–algebras, Mathematical Structures in Computer Science, 5 (1995), pages 129–152
    • 48 H. Tews, Coalgebraic Methods for Object–Oriented Specification, PhD thesis, TU Dresden 2002
    • 49 J. Rothe, H. Tews, B. Jacobs, The Coalgebraic Class Specification Language CCSL, Journal of Universal Computer Science 7 (2001), pages 175-193
    • 50 D. Turi, G. Plotkin, Towards a Mathematical Operational Semantics, Proc. LICS 1997
    • 51 G. Hutton, Fold and Unfold for Program Semantics, ACM SIGPLAN 1998
    • 52 J. Rutten, Processes as Terms: Non-Wellfounded Models for Bisimulation, MSCS (1992), pages 257-275
    • 53 http://www.haskell.org/haskellwiki/Applications_and_libraries
  • Bei Interesse an einem der o.g. Themen schreiben Sie bitte zwecks Vereinbarung eines Termins zur näheren Spezifikation der Arbeit eine Email an Peter Padawitz (peter.padawitz@udo.edu). Die o.g. Artikel bieten einen Einblick in das jeweilige Thema, sind aber nicht notwendig diejenigen, auf die sich die Bachelorarbeit stützt.