Klaus W. Wagner

According to our database, Klaus W. Wagner authored at least 88 papers between 1973 and 2015.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2015

Weighted Boolean Formula Games.

Marios Mavronicolas, Burkhard Monien, Klaus W. Wagner

Proceedings of the Algorithms, Probability, Networks, and Games, 2015

2014

Perfect correspondences between dot-depth and polynomial-time hierarchies.

Christian Glaßer, Stephen D. Travers, Klaus W. Wagner

J. Comput. Syst. Sci., 2014

2011

Editorial.

Andrei S. Morozov, Klaus W. Wagner

Theory Comput. Syst., 2011

2008

The complexity of unions of disjoint sets.

Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner

J. Comput. Syst. Sci., 2008

The boolean hierarchy of NP-partitions.

Sven Kosub, Klaus W. Wagner

Inf. Comput., 2008

Complexity of Topological Properties of Regular omega-Languages.

Victor L. Selivanov, Klaus W. Wagner

Fundam. Informaticae, 2008

08271 Executive Summary - Topological and Game-Theoretic Aspects of Infinite Computations.

Peter Hertling, Victor L. Selivanov, Wolfgang Thomas, William W. Wadge, Klaus W. Wagner

Proceedings of the Topological and Game-Theoretic Aspects of Infinite Computations, 29.06., 2008

08271 Abstracts Collection - Topological and Game-Theoretic Aspects of Infinite Computations.

Peter Hertling, Victor L. Selivanov, Wolfgang Thomas, William W. Wadge, Klaus W. Wagner

Proceedings of the Topological and Game-Theoretic Aspects of Infinite Computations, 29.06., 2008

Complexity of Aperiodicity for Topological Properties of Regular omega-Languages.

Victor L. Selivanov, Klaus W. Wagner

Proceedings of the Logic and Theory of Algorithms, 2008

2007

The Complexity of Computing the Size of an Interval.

Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, Klaus W. Wagner

SIAM J. Comput., 2007

The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers.

Pierre McKenzie, Klaus W. Wagner

Comput. Complex., 2007

2006

Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy.

Christian Glaßer, Stephen D. Travers, Klaus W. Wagner

Proceedings of the Developments in Language Theory, 10th International Conference, 2006

2005

A reducibility for the dot-depth hierarchy.

Victor L. Selivanov, Klaus W. Wagner

Theor. Comput. Sci., 2005

Generation problems.

Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner

Theor. Comput. Sci., 2005

A Reducibility that Corresponds to Unbalanced Leaf-Language Classes

Christian Glaßer, Stephen D. Travers, Klaus W. Wagner

Electron. Colloquium Comput. Complex., 2005

2004

Arithmetic Circuits and Polynomial Replacement Systems.

Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner

SIAM J. Comput., 2004

Leaf Language Classes.

Klaus W. Wagner

Proceedings of the Machines, Computations, and Universality, 4th International Conference, 2004

2003

On the Exponentiation of Languages.

Werner Kuich, Klaus W. Wagner

Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

Theoretische Informatik - eine kompakte Einführung (2. Aufl.).

Klaus W. Wagner

Springer, ISBN: 978-3-540-01313-6, 2003

2001

On boolean lowness and boolean highness.

Steffen Reith, Klaus W. Wagner

Theor. Comput. Sci., 2001

The Complexity of Computing the Size of an Interval.

Lane A. Hemaspaandra, Sven Kosub, Klaus W. Wagner

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

2000

Characterizing Small Depth and Small Space Classes by Operators of Higher Type.

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

Chic. J. Theor. Comput. Sci., 2000

1998

Bounding Queries in the Analytic Polynomial-Time Hierarchy.

Herbert Baier, Klaus W. Wagner

Theor. Comput. Sci., 1998

The Chain Method to Separate Counting Classes.

K. Cronauer, Ulrich Hertrampf, Heribert Vollmer, Klaus W. Wagner

Theory Comput. Syst., 1998

The Analytic Polynomial Time Hierarchy.

Herbert Baier, Klaus W. Wagner

Math. Log. Q., 1998

A Note on Parallel Queries and the Symmetric-Difference Hierarchy.

Klaus W. Wagner

Inf. Process. Lett., 1998

Characterizing Small Depth and Small Space Classes by Operators of Higher Types

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

Electron. Colloquium Comput. Complex., 1998

The Boolean Hierarchy over Level 1/2 of the Straubing-Therien Hierarchy

Heinz Schmitz, Klaus W. Wagner

CoRR, 1998

Probabilistic Type-2 Operators and "Almost"-Classes.

Ronald V. Book, Heribert Vollmer, Klaus W. Wagner

Comput. Complex., 1998

1997

On Operators of Higher Types.

Heribert Vollmer, Klaus W. Wagner

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

Measure One Results in Computational Complexity Theory.

Heribert Vollmer, Klaus W. Wagner

Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

1996

Recursion Theoretic Characterizations of Complexity Classes of Counting Functions.

Heribert Vollmer, Klaus W. Wagner

Theor. Comput. Sci., 1996

On Balanced Versus Unbalanced Computation Trees.

Ulrich Hertrampf, Heribert Vollmer, Klaus W. Wagner

Math. Syst. Theory, 1996

On the Power of DNA-Computing.

Diana Rooß, Klaus W. Wagner

Inf. Comput., 1996

On Type-2 Probabilistic Quantifiers.

Ronald V. Book, Heribert Vollmer, Klaus W. Wagner

Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995

Complexity Classes of Optimization Functions

Heribert Vollmer, Klaus W. Wagner

Inf. Comput., August, 1995

On the Power of Number-Theoretic Operations with Respect to Counting.

Ulrich Hertrampf, Heribert Vollmer, Klaus W. Wagner

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

An Observation on Probability Versus Randomness with Applications to Complexity Classes.

Ronald V. Book, Jack H. Lutz, Klaus W. Wagner

Math. Syst. Theory, 1994

Einführung in die theoretische Informatik - Grundlagen und Modelle.

Klaus W. Wagner

Springer, ISBN: 978-3-540-58139-0, 1994

1993

Counting Hierarchies: Polynomial Time and Constant Depth Circuits.

Eric Allender, Klaus W. Wagner

Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

The Complexity of Finding Middle Elements.

Heribert Vollmer, Klaus W. Wagner

Int. J. Found. Comput. Sci., 1993

The Alternation Hierarchy for Sublogarithmic Space: An Exciting Race to STACS'93 (Editorial Note).

Klaus W. Wagner

Proceedings of the STACS 93, 1993

On the Power of Polynomial Time Bit-Reductions (Extended Abstract).

Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

On the Power of Polynomial Bit-Reductions

Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner

Universität Trier, Mathematik/Informatik, Forschungsbericht, 1992

The Correlation between the Complexities of the Nonhierarchical and Hierarchical Versions of Graph Problems.

Thomas Lengauer, Klaus W. Wagner

J. Comput. Syst. Sci., 1992

On the Power of One-Way Synchronized Alternating Machines with Small Space.

Juraj Hromkovic, Katsushi Inoue, Branislav Rovan, Anna Slobodová, Itsuo Takanami, Klaus W. Wagner

Int. J. Found. Comput. Sci., 1992

On Complexity Classes and Algorithmically Random Languages (Extended Abstract).

Ronald V. Book, Jack H. Lutz, Klaus W. Wagner

Proceedings of the STACS 92, 1992

1990

The Binary Network Flow Problem is Logspace Complete for P.

Thomas Lengauer, Klaus W. Wagner

Theor. Comput. Sci., 1990

Bounded Query Classes.

Klaus W. Wagner

SIAM J. Comput., 1990

Counting Hierarchies: Polynomial Time and Constant.

Eric Allender, Klaus W. Wagner

Bull. EATCS, 1990

Vector Language: Simple Description of Hard Instances (Extended Abstract).

Miroslaw Kowaluk, Klaus W. Wagner

Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

Interactive Proof Systems: Provers, Rounds, and Error Bounds.

Ulrich Hertrampf, Klaus W. Wagner

Proceedings of the Computer Science Logic, 4th Workshop, 1990

1989

The Boolean Hierarchy II: Applications.

Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung

SIAM J. Comput., 1989

1988

The Boolean Hierarchy I: Structural Properties.

Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung

SIAM J. Comput., 1988

The computational complexity of graph problems with succinct multigraph representation.

Marek Karpinski, Klaus W. Wagner

ZOR Methods Model. Oper. Res., 1988

Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries.

Uwe Schöning, Klaus W. Wagner

Proceedings of the STACS 88, 1988

On Restricting the Access to an NP-Oracle.

Klaus W. Wagner

Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

Bounded query computations.

Klaus W. Wagner

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

More Complicated Questions About Maxima and Minima, and Some Closures of NP.

Klaus W. Wagner

Theor. Comput. Sci., 1987

Uniform Simulations of Nondeterministic Real Time Multitape Turing Machines.

Franz-Josef Brandenburg, Andreas Brandstädt, Klaus W. Wagner

Math. Syst. Theory, 1987

The Difference and Truth-Table Hierarchies for NP.

Johannes Köbler, Uwe Schöning, Klaus W. Wagner

RAIRO Theor. Informatics Appl., 1987

Do There Exist Languages With an Arbitrarily Small Amount of Context-Sensitivity.

Klaus W. Wagner

Proceedings of the Computation Theory and Logic, In Memory of Dieter Rödding, 1987

1986

Some Observations on the Connection Between Counting an Recursion.

Klaus W. Wagner

Theor. Comput. Sci., 1986

On the Intersection of the Class of Linear Context-Free Languages and the Class of Single-Reset Languages.

Klaus W. Wagner

Inf. Process. Lett., 1986

A characterization of the minimalbasis of the torus.

Rainer Bodendiek, Klaus W. Wagner

Comb., 1986

The Complexity of Combinatorial Problems with Succinct Input Representation.

Klaus W. Wagner

Acta Informatica, 1986

1985

Two-Way Automata with More than one Storage Medium.

Jörg Vogel, Klaus W. Wagner

Theor. Comput. Sci., 1985

On some minimal graphs of the torus.

Rainer Bodendiek, Klaus W. Wagner

J. Graph Theory, 1985

Zur Einbettbarkeit von Graphen in den Torus.

Rainer Bodendiek, Klaus W. Wagner

Eur. J. Comb., 1985

1984

Monotonic Coverings of Finite Sets.

Klaus W. Wagner

J. Inf. Process. Cybern., 1984

1983

Reversal-Bounded and Visit-Bounded Realtime Computations.

Andreas Brandstädt, Klaus W. Wagner

Proceedings of the Fundamentals of Computation Theory, 1983

1982

Eine Bemerkung zu einer Arbeit von Monien über Kopfzahl-Hierarchien für Zweiweg-Automaten.

Dietrich Meinhardt, Klaus W. Wagner

J. Inf. Process. Cybern., 1982

1979

On omega-Regular Sets

Klaus W. Wagner

Inf. Control., November, 1979

Bounded Recursion and Complexity Classes.

Klaus W. Wagner

Proceedings of the Mathematical Foundations of Computer Science 1979, 1979

1978

Rekursive Folgenmengen I.

Ludwig Staiger, Klaus W. Wagner

Math. Log. Q., 1978

1977

Arithmetische und Bairesche Operatoren.

Klaus W. Wagner

Math. Log. Q., 1977

Eine topologische Charakterisierung einiger Klassen regulärer Folgenmengen.

Klaus W. Wagner

J. Inf. Process. Cybern., 1977

Complexity Hierarchies of Oracles.

Klaus W. Wagner, Gerd Wechsung

Proceedings of the Mathematical Foundations of Computer Science 1977, 1977

Recursive omega-Languages.

Klaus W. Wagner, Ludwig Staiger

Proceedings of the Fundamentals of Computation Theory, 1977

1976

Arithmetische Operatoren.

Klaus W. Wagner

Math. Log. Q., 1976

Eine Axiomatisierung der Theorie der regulären Folgenmengen.

Klaus W. Wagner

J. Inf. Process. Cybern., 1976

1975

Akzeptierbarkeitsgrade regulärer Folgemengen.

Klaus W. Wagner

J. Inf. Process. Cybern., 1975

A Hierarchy of Regular Sequence Sets.

Klaus W. Wagner

Proceedings of the Mathematical Foundations of Computer Science 1975, 1975

1974

Zellulare Berechenbarkeit von Funktionen über n-dimensionalen Zeichensystemen.

Klaus W. Wagner

J. Inf. Process. Cybern., 1974

Automatentheoretische und automatenfreie Charakterisierungen topologischer Klassen regulärer Folgenmengen.

Ludwig Staiger, Klaus W. Wagner

J. Inf. Process. Cybern., 1974

Finite Automata Acceptation of Infinite Sequences.

Klaus W. Wagner, Ludwig Staiger

Proceedings of the Mathematical Foundations of Computer Science, 1974

1973

Universelle Turingmaschinen mit n-dimensionalem Band.

Klaus W. Wagner

J. Inf. Process. Cybern., 1973

Die Modellierung der Arbeit von Turingmaschinen mit n-dimensionalem Band durch Turingmaschinen mit eindimensionalem Band.

Klaus W. Wagner

J. Inf. Process. Cybern., 1973