2010

Journal Articles

  1. Ulrich Hertrampf and Christoph Minnameier
    Resource bounded frequency computations with three errors
    Algorithmica. 56(3):342–363. 2010.
    DOI

2009

Book Chapters

  1. Volker Diekert and Ulrich Hertrampf
    Komplexität der Geographie
    Informatik als Dialog zwischen Theorie und Anwendung: Festschrift für Volker Claus zum 65. Geburtstag, Chapter 11, pages 119–132. Vieweg+Teubner, 2009.
    PDF
    DOI

2008

Book Chapters

  1. Ulrich Hertrampf and Christoph Minnameier
    Resource bounded frequency computations with three errors
    Computing and combinatorics, volume 5092 of Lecture Notes in Computer Science, pages 72–81. Springer, 2008.
    DOI

2005

Journal Articles

  1. Holger Austinat , Volker Diekert , Ulrich Hertrampf and Holger Petersen
    Regular Frequency Computations
    Theoretical Computer Science. 330(1):15–21. 2005.
    PDF
    DOI

2003

Journal Articles

  1. Holger Austinat , Volker Diekert and Ulrich Hertrampf
    A Structural Property of Regular Frequency Computations
    Theoretical Computer Science. 292(1):33–43. 2003.
    PS
    DOI

2000

Journal Articles

  1. Ulrich Hertrampf
    Algebraic acceptance mechanisms for polynomial time machines
    SIGACT News. 31(2):22–33. 2000.
    DOI
  2. Ulrich Hertrampf
    Quantencomputer
    Informatik-Spektrum. 23(5):322–324. 2000.
    DOI
  3. Ulrich Hertrampf , Steffen Reith and Heribert Vollmer
    A note on closure properties of logspace MOD classes
    Information Processing Letters. 75(3):91–93. 2000.
    DOI

Conference Articles

  1. Holger Austinat , Volker Diekert , Ulrich Hertrampf and Holger Petersen
    On Regular Frequency Computations
    Proc. RIMS Symposium on Algebraic Systems, Formal Languages and Computation, Kyoto, Japan, pages 35–42. 2000.

1999

Book Chapters

  1. Ulrich Hertrampf
    Generalized Regular Counting Classes
    Mathematical foundations of computer science 1999 (Szklarska Poreba), volume 1672 of Lecture Notes in Computer Science, pages 419–429. Springer, 1999.
    DOI

1998

Journal Articles

  1. K. Cronauer , U. Hertrampf , H. Vollmer and K. W. Wagner
    The Chain Method to Separate Counting Classes
    Theory Computing Systems. 31(1):93–108. 1998.
    DOI

Book Chapters

  1. Ulrich Hertrampf
    The Inherent Dimension of Bounded Counting Classes
    Computing and combinatorics (Taipei, 1998), volume 1449 of Lecture Notes in Computer Science, pages 157–166. Springer, 1998.
    DOI

1997

Book Chapters

  1. Ulrich Hertrampf
    Acceptance by Transformation Monoids (with an Application to Local Self Reductions)
    Twelfth Annual IEEE Conference on Computational Complexity (Ulm, 1997), pages 213–224. IEEE Computer Society, 1997.
    DOI
  2. Ulrich Hertrampf
    Polynomial Time Machines Equipped with Word Problems over Algebraic Structures as their Acceptance Criteria
    Fundamentals of computation theory (Kraków, 1997), volume 1279 of Lecture Notes in Computer Science, pages 233–244. Springer, 1997.
    DOI
  3. Ulrich Hertrampf
    The Shapes of Trees
    Computing and combinatorics (Shanghai, 1997), volume 1276 of Lecture Notes in Computer Science, pages 412–421. Springer, 1997.
    DOI

1996

Journal Articles

  1. U. Hertrampf , H. Vollmer and K. W. Wagner
    On Balanced vs. Unbalanced Computation Trees
    Math. Systems Theory. 29(4):411–421. 1996.
    DOI

1995

Conference Articles

  1. Ulrich Hertrampf
    Classes of Bounded Counting Type and their Inclusion Relations
    STACS 95 (Munich, 1995), volume 900 of Lecture Notes in Computer Science, pages 60–70. Springer, 1995.
    DOI
  2. Ulrich Hertrampf , Heribert Vollmer and Klaus W. Wagner
    On the Power of Number-Theoretic Operations with Respect to Counting
    Structure in Complexity Theory Conference, pages 299–314. 1995.
    WWW

1994

Journal Articles

  1. Eric Allender and Ulrich Hertrampf
    Depth Reduction for Circuits of Unbounded Fan-In
    Information and Computation. 112(2):217–238. 1994.
    DOI

Conference Articles

  1. Ulrich Hertrampf
    Complexity Classes Defined via k-valued Functions
    Structure in Complexity Theory Conference, pages 224–234. 1994.
  2. Ulrich Hertrampf
    Complexity Classes with Finite Acceptance Type
    STACS 94 (Caen, 1994), volume 775 of Lecture Notes in Computer Science, pages 543–553. Springer, 1994.
    DOI

1993

Journal Articles

  1. Eric Allender , Richard Beigel , Ulrich Hertrampf and Steven Homer
    Almost-everywhere Complexity Hierarchies for Nondeterministic Time
    Theoretical Computer Science. 115(2):225–241. 1993.
    DOI

Conference Articles

  1. Ulrich Hertrampf , Clemens Lautemann , Thomas Schwentick , Heribert Vollmer and Klaus W. Wagner
    On the Power of Polynomial Time Bit-Reductions
    Proceedings of the Eighth Annual Structure in Complexity Theory Conference (San Diego, CA, 1993), pages 200–207. IEEE Comput. Soc. Press, 1993.
    DOI

1992

Journal Articles

  1. Gerhard Buntrock , Carsten Damm , Ulrich Hertrampf and Christoph Meinel
    Structure and Importance of Logspace-MOD-Classes
    Math. Systems Theory. 25(3):223–237. 1992.
    DOI

Conference Articles

  1. Ulrich Hertrampf
    Locally Definable Acceptance Types for Polynomial Time Machines
    STACS 92 (Cachan, 1992), volume 577 of Lecture Notes in Computer Science, pages 199–207. Springer, 1992.
    DOI
  2. Ulrich Hertrampf
    Locally Definable Acceptance Types — The Three-Valued Case
    LATIN ’92 (São Paulo, 1992), volume 583 of Lecture Notes in Computer Science, pages 262–271. Springer, 1992.
    DOI

1991

Conference Articles

  1. Ulrich Hertrampf and Klaus Wagner
    Interactive Proof Systems: Provers, Rounds, and Error Bounds
    Computer science logic (Heidelberg, 1990), volume 533 of Lecture Notes in Computer Science, pages 261–273. Springer, 1991.
    DOI

Book Chapters

  1. Gerhard Buntrock , Carsten Damm , Ulrich Hertrampf and Christoph Meinel
    Structure and importance of logspace-mod-classes
    STACS 91 (Hamburg, 1991), volume 480 of Lecture Notes in Computer Science, pages 360–371. Springer, 1991.
    DOI

1990

Journal Articles

  1. Ulrich Hertrampf
    Relations among MOD-classes
    Theoretical Computer Science. 74(3):325–328. Elsevier Science Publishers Ltd., 1990.
    DOI

Conference Articles

  1. Eric Allender , Richard Beigel , Ulrich Hertrampf and Steven Homer
    A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time
    STACS 90 (Rouen, 1990), volume 415 of Lecture Notes in Computer Science, pages 1–11. Springer, 1990.
    DOI
  2. Richard Beigel , John Gill and Ulrich Hertrampf
    Counting Classes: Thresholds, Parity, Mods, and Fewness
    STACS 90 (Rouen, 1990), volume 415 of Lecture Notes in Computer Science, pages 49–57. Springer, 1990.
    DOI

Book Chapters

  1. Eric Allender and Ulrich Hertrampf
    On the Power of Uniform Families of Constant Depth Threshold Circuits
    Mathematical foundations of computer science (Banská Bystrica, 1990), volume 452 of Lecture Notes in Computer Science, pages 158–164. Springer, 1990.
    DOI

News

[Apr’18] The paper “The isomorphism problem for finite extensions of free groups is in PSPACE” by Géraud Sénizergues and Armin Weiß was accepted at ICALP 2018.

[Apr’18] The paper “On the Complexity of the Cayley Semigroup Membership Problem” by Lukas Fleischer was accepted at CCC 2018.

[Jan’18] On March 24-29, 2019 Volker Diekert, Markus Lohrey, Olga Kharlampovich and Alexei Miasnikov will organize the Schloss Dagstuhl Seminar “Algorithmic Problems in Group Theory”.

[Dec’17] The paper “The Intersection Problem for Finite Monoids” by Lukas Fleischer and Manfred Kufleitner was accepted at STACS 2018.

[Jun’17] At the 12th International Computer Science Symposium in Russia (CSR), Lukas Fleischer and Manfred Kufleitner received a Best Paper Award for their publication “Green’s Relations in Finite Transformation Semigroups”, and Armin Weiss received a Best Paper Award for “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ which is joint work with Alexei Miasnikov and Svetla Vassileva.