50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Publications 1997


Konferenzbeiträge

  • U. Egly, K. Genther
    Structuring of Computer-Generated Proofs by Cut Introduction
    Proc. 5. Kut Gödel Colloquium Computational Logic and Proof Theory KGC, Springer Lecture Notes in Computer Science, 1289, 1997, 140-152
  • R. Reischuk
    Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise
    Proc. 3. Int. Conference on Computing and Combinatorics COCOON, Springer Lecture Notes in Computer, 1276, 1997, 72-81
  • R. Reischuk, M. Liskiewicz
    Computational Limitations of Stochastic Turing Machines and Arthur-Merlin Games with Small Space Bounds
    Proc. 22. Int. Symposium on Mathematical Foundations of Computer Science MFCS, Springer Lecture Notes in Computer, 1295, 1997, 91-107
  • M. Liskiewicz
    Interactive Proof Systems with Public Coin: Lower Space Bounds and Hierarchies of Complexity Classes
    Proc. 14. Symposium on Theoretical Aspects of Computer Science, Springer Lecture Notes in Computer Science, 1200, 1997, 129-140
  • T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger, T. Zeugmann
    Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries
    Proc. 8. Int. Workshop on Algorithmic Learning Theory - ALT'97, (M. Li and A. Maruoka, Eds.), Lecture Notes in Artificial Intelligence 1316, 1997, 260 - 276

Zeitschriftenbeiträge

  • R.Reischuk, C. Schindelhauer
    An Average Complexity Measure that Yields Tight Hierarchies
    Computational Complexity 6, 1997, 133-173
  • C.H. Smith, R. Wiehagen, T. Zeugmann
    Classifying Predicates and Languages
    International Journal of Foundations of Computer Science 8, 1, 1997, 15 - 41

Monografien, Editorium, Buchbeiträge

  • M. Liskiewicz, R. Reischuk
    Computing with Sublogarithmic Space
    Complexity Theory Respective II, L. Hemaspandra, A. Selman (Eds.), 1997, 197-224
  • G. Buntrock
    Wachsende Kontextsensitive Sprachen
    Komplexitätstheorie -- Maschinen und Operatoren, H. Vollmer (Hg.), Cuvillier Verlag, 1997, 111-126
  • R. Reischuk, M. Morvan, (Eds.)
    Proceedings of the 14. GI-AFCET Symposium on Theoretical Aspects of Computer Science STACS '97, Lübeck, Februar/März 1997
    Springer Lecture Notes in Computer Science 1200
  • D. Barrington, N. Nisan, R. Reischuk, I. Wegener, (Eds.)
    Complexity of Boolean Functions Dagstuhl-Seminar-Report 172, 1997, 10.-14.3.97 (9711)
  • T. Zeugmann (Guest Editor)
    Algorithmic Learning Theory
    6th Int. Workshop ALT'95, Fukuoka, Japan, October 1995, (Special Issue in Theoretical Computer Science 185, 1, 1997)

Forschungsberichte

  • A. Jakoby
    On the Average Circuit Complexity of Semigroups
    Dagstuhl-Seminar: Complexity of Boolean Functions, Dagstuhl-Seminar-Report 172, 14
  • A. Jakoby, C. Schindelhauer, R. Reischuk
    Lower Bounds in Average Circuit Complexity
    Dagstuhl-Seminar: Complexity of Boolean Functions, Dagstuhl-Seminar-Report 172, 14-15
  • R. Reischuk
    The Strong Fault Tolerance of Threshold Circuits is Weak
    Dagstuhl-Seminar: Complexity of Boolean Functions, Dagstuhl-Seminar-Report 172, 21
  • A. Jakoby, M. Liskiewicz, R. Reischuk
    Labelled-Delay Scheduling
    Dagstuhl-Seminar, Scheduling in Computer and Manufacturing Systems, Dagstuhl-Seminar-Report 180, 25
  • J. Case, S. Jain, S. Lange, T. Zeugmann
    Incremental Concept Learning for Bounded Data Mining
    DOI Technical Report DOI-TR-136, Department of Informatics, Kyushu University, April 1997
  • R. Reischuk, T. Zeugmann
    Learning One-Variable Pattern Languages in Linear Average Time
    DOI Technical Report DOI-TR-140, Department of Informatics, Kyushu University, September 1997