CoaSt: Complexity and Structure

Complex systems and complex problems appear in all areas of applications. It is the goal of this project to analyse connections between the structure of the underlying complex problems and their algorithmic complexity. A special focus is investigating the borderline between problems with efficient solutions and those with high complexity. Of interest is here the structure of input objects as well as the inner structure of the problem itself. The problems range from algorithmic graph theory to optimisation. Of special interest are problems in the area of finance and electronic commerce.

Selected publications

T. Dietrich, D. Seese: Der Handel bei eBay.de (in German, translated title: The Trade at eBay.de); In: Handel im Fokus - Mitteilungen des Instituts für Handelsforschung an der Universität Köln, (Ed. V. Prof. Dr. Müller-Hagedorn) Volume 56, Number 1, February 2004, pp. 17 - 30, The paper is available online.

P. Hlineny, D. Seese: On Decidability of MSO Theories of Representable Matroids; Accepted at the workshop IWPEC 2004 at ALGO 2004 University of Bergen, Bergen.

D. Seese, F. Schlottmann: Large grids and local information flow as a reason for high complexity, in: Frizelle, Gerry; Richards, Huw (eds.): Tackling industrial complexity: the ideas that make a difference, Proceedings of the 2002 conference of the Manufacturing Complexity Network, University of Cambridge, 2002, pp. 193-207. Download this paper from the MCNC site: PDF (ISBN 1-902546-24-5) [PDF] [PS]

F. Schlottmann, D. Seese: The building blocks of complexity: a unified criterion and selected applications in economics and finance, April 2002, Material for a series of lectures at the School of Finance and Economics of the University of Technology in Sydney, at the School of Mathematics and Statistics of the University of Sydney and at the Sydney Financial Mathematics Workshop. http://www.qgroup.org.au/SFMW/ [PDF] [PS]

M. Kreidler, D. Seese: Monadic NP and Graph Minors, in Computer Science Logic, Proceedings of the 12th International Workshop, CSL'98, Annual Conference of the EACSL, Brno, Czech Republic, August 24-28, 1998, Eds. G. Gottlob, E. Grandjean, K. Seyr, Springer LNCS, pp 126 - 141.

M. Kreidler, D. Seese: Monadic NP and Built-in Trees, in Computer Science Logic, 10th International Workshop, CSL'96, Annual Conference of the EACSL, Utrecht, The Netherlands, September 1996, Selected Papers, Lecture Notes in Computer Science 1258, pp. 260 - 274.

D. Seese: Linear Time Computable Problems and Logical Descriptions, Proceedings of SEGRAGRA'95, Joint COMPUGRAPH/SEMAGRAPH Workshop on Graph Rewriting and Computation, Volterra (Pisa, Italy), August 28 - September 1, 1995, A. Corradini, U. Montanari (Eds.), in Electronic Notes in Theoretical Computer Science, 2, 1995, 219-232.

D. Seese: Interpretability and tree automata: a simple way to solve algorithmic problems on graphs closely related to trees, in Tree Automata and Languages, edited by M. Nivat and A. Podelski, Elsevier Science Publishers, 1992, pp. 83 - 114.

S. Arnborg, J. Lagergren, D. Seese: Easy problems for tree-decomposable graphs. Journal of Algorithms, 12, 1991, 308 - 340.

S. Arnborg, J. Lagergren, D. Seese: Problems easy for tree-decomposable graphs. Extended abstract, Proc. 15th Int. Colloq. Automata, Languages and Programming (Tampere, Finland, 1988). In: Lecture Notes in Computer Science 317, Springer-Verlag, 38 - 51, 1988.

D. Seese: The structure of models of decidable monadic theories of graphs. Annals of Pure and Applied Logic, 53, 1991, 169 - 195.

S. Arnborg, B. Courcelle, D. Seese, A. Proskurowski: An algebraic theory of graph reduction, J. ACM, Vol. 40, No. 5, 1993, pp. 1134 - 1164.

D. Seese: Linear Time Computable Problems and First Order Descriptions, Mathematical Structures in Computer Science, Vol. 6, 1996, pp. 505-526

H. Buchwald, M. Wiedmann, D. Seese: Design by Contract in Java - a roadmap to excellence in trusted components, Informatik, Nr. 2, April 2000, pp. 9-14.