Klaus W. Wagner

According to our database1, Klaus W. Wagner
  • authored at least 103 papers between 1973 and 2015.
  • has a "Dijkstra number"2 of three.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2015
Weighted Boolean Formula Games.
Proceedings of the Algorithms, Probability, Networks, and Games, 2015

2014
Perfect correspondences between dot-depth and polynomial-time hierarchies.
J. Comput. Syst. Sci., 2014

2011
Editorial.
Theory Comput. Syst., 2011

2008
The complexity of unions of disjoint sets.
J. Comput. Syst. Sci., 2008

The boolean hierarchy of NP-partitions.
Inf. Comput., 2008

Complexity of Topological Properties of Regular omega-Languages.
Fundam. Inform., 2008

Complexity of Topological Properties of Regular omega-Languages.
Proceedings of the Developments in Language Theory, 12th International Conference, 2008

08271 Executive Summary - Topological and Game-Theoretic Aspects of Infinite Computations.
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.
Proceedings of the Topological and Game-Theoretic Aspects of Infinite Computations, 29.06., 2008

Complexity of Aperiodicity for Topological Properties of Regular omega-Languages.
Proceedings of the Logic and Theory of Algorithms, 2008

2007
The Complexity of Computing the Size of an Interval.
SIAM J. Comput., 2007

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

Weighted Boolean Formula Games.
Proceedings of the Internet and Network Economics, Third International Workshop, 2007

The Complexity of Unions of Disjoint Sets.
Proceedings of the STACS 2007, 2007

2006
The Complexity of Unions of Disjoint Sets.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy.
Proceedings of the Developments in Language Theory, 10th International Conference, 2006

2005
A reducibility for the dot-depth hierarchy.
Theor. Comput. Sci., 2005

Generation problems.
Theor. Comput. Sci., 2005

A Reducibility that Corresponds to Unbalanced Leaf-Language Classes
Electronic Colloquium on Computational Complexity (ECCC), 2005

The Complexity of Computing the Size of an Interval
CoRR, 2005

2004
Arithmetic Circuits and Polynomial Replacement Systems.
SIAM J. Comput., 2004

Generation Problems
Electronic Colloquium on Computational Complexity (ECCC), 2004

A Reducibility for the Dot-Depth Hierarchy.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Generation Problems.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Leaf Language Classes.
Proceedings of the Machines, Computations, and Universality, 4th International Conference, 2004

2003
The Complexity of Membership Problems for Circuits over Sets of Natural Numbers.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

On the Exponentiation of Languages.
Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

Theoretische Informatik - eine kompakte Einführung (2. Aufl.).
Springer, ISBN: 978-3-540-01313-6, 2003

2001
On boolean lowness and boolean highness.
Theor. Comput. Sci., 2001

The Complexity of Computing the Size of an Interval.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

2000
Characterizing Small Depth and Small Space Classes by Operators of Higher Type.
Chicago J. Theor. Comput. Sci., 2000

The Boolean Hierarchy of NP-Partitions.
Proceedings of the STACS 2000, 2000

Arithmetic Circuits and Polynomial Replacement Systems.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

1998
Bounding Queries in the Analytic Polynomial-Time Hierarchy.
Theor. Comput. Sci., 1998

The Chain Method to Separate Counting Classes.
Theory Comput. Syst., 1998

The Analytic Polynomial Time Hierarchy.
Math. Log. Q., 1998

A Note on Parallel Queries and the Symmetric-Difference Hierarchy.
Inf. Process. Lett., 1998

Characterizing Small Depth and Small Space Classes by Operators of Higher Types
Electronic Colloquium on Computational Complexity (ECCC), 1998

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

Probabilistic Type-2 Operators and "Almost"-Classes.
Computational Complexity, 1998

On Boolean Lowness and Boolean Highness.
Proceedings of the Computing and Combinatorics, 4th Annual International Conference, 1998

1997
On Operators of Higher Types.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

Measure One Results in Computational Complexity Theory.
Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

1996
Recursion Theoretic Characterizations of Complexity Classes of Counting Functions.
Theor. Comput. Sci., 1996

On Balanced Versus Unbalanced Computation Trees.
Mathematical Systems Theory, 1996

On the Power of DNA-Computing.
Inf. Comput., 1996

Probabilistic Type-2 Operators and "Almost"-Classes
Electronic Colloquium on Computational Complexity (ECCC), 1996

On Type-2 Probabilistic Quantifiers.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995
Complexity Classes of Optimization Functions
Inf. Comput., August, 1995

On the Power of Number-Theoretic Operations with Respect to Counting.
Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994
An Observation on Probability Versus Randomness with Applications to Complexity Classes.
Mathematical Systems Theory, 1994

Einführung in die theoretische Informatik - Grundlagen und Modelle.
Springer, ISBN: 978-3-540-58139-0, 1994

1993
Counting Hierarchies: Polynomial Time and Constant Depth Circuits.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

The Complexity of Finding Middle Elements.
Int. J. Found. Comput. Sci., 1993

The Alternation Hierarchy for Sublogarithmic Space: An Exciting Race to STACS'93 (Editorial Note).
Proceedings of the STACS 93, 1993

On the Power of Polynomial Time Bit-Reductions (Extended Abstract).
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
On the Power of Polynomial Bit-Reductions
Universität Trier, Mathematik/Informatik, Forschungsbericht, 1992

The Correlation between the Complexities of the Nonhierarchical and Hierarchical Versions of Graph Problems.
J. Comput. Syst. Sci., 1992

On the Power of One-Way Synchronized Alternating Machines with Small Space.
Int. J. Found. Comput. Sci., 1992

On Complexity Classes and Algorithmically Random Languages (Extended Abstract).
Proceedings of the STACS 92, 1992

1990
The Binary Network Flow Problem is Logspace Complete for P.
Theor. Comput. Sci., 1990

Bounded Query Classes.
SIAM J. Comput., 1990

Counting Hierarchies: Polynomial Time and Constant.
Bulletin of the EATCS, 1990

Vector Language: Simple Description of Hard Instances (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

Interactive Proof Systems: Provers, Rounds, and Error Bounds.
Proceedings of the Computer Science Logic, 4th Workshop, 1990

1989
The Boolean Hierarchy II: Applications.
SIAM J. Comput., 1989

1988
The Boolean Hierarchy I: Structural Properties.
SIAM J. Comput., 1988

The computational complexity of graph problems with succinct multigraph representation.
ZOR - Meth. & Mod. of OR, 1988

Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries.
Proceedings of the STACS 88, 1988

On Restricting the Access to an NP-Oracle.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

Bounded query computations.
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.
Theor. Comput. Sci., 1987

Uniform Simulations of Nondeterministic Real Time Multitape Turing Machines.
Mathematical Systems Theory, 1987

The Difference and Truth-Table Hierarchies for NP.
ITA, 1987

The Correlation Between the Complexities of the Nonhierarchical and Hierarchical Versions of Graph Problems.
Proceedings of the STACS 87, 1987

Do There Exist Languages With an Arbitrarily Small Amount of Context-Sensitivity.
Proceedings of the Computation Theory and Logic, In Memory of Dieter Rödding, 1987

1986
Some Observations on the Connection Between Counting an Recursion.
Theor. Comput. Sci., 1986

On the Intersection of the Class of Linear Context-Free Languages and the Class of Single-Reset Languages.
Inf. Process. Lett., 1986

A characterization of the minimalbasis of the torus.
Combinatorica, 1986

The Complexity of Combinatorial Problems with Succinct Input Representation.
Acta Inf., 1986

More Complicated Questions About Maxima and Minima, and Some Closures of NP.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

1985
Two-Way Automata with More than one Storage Medium.
Theor. Comput. Sci., 1985

On some minimal graphs of the torus.
Journal of Graph Theory, 1985

Zur Einbettbarkeit von Graphen in den Torus.
Eur. J. Comb., 1985

1984
Monotonic Coverings of Finite Sets.
Elektronische Informationsverarbeitung und Kybernetik, 1984

1983
Reversal-Bounded and Visit-Bounded Realtime Computations.
Proceedings of the Fundamentals of Computation Theory, 1983

1982
Eine Bemerkung zu einer Arbeit von Monien über Kopfzahl-Hierarchien für Zweiweg-Automaten.
Elektronische Informationsverarbeitung und Kybernetik, 1982

1979
On omega-Regular Sets
Information and Control, November, 1979

Bounded Recursion and Complexity Classes.
Proceedings of the Mathematical Foundations of Computer Science 1979, 1979

1978
Rekursive Folgenmengen I.
Math. Log. Q., 1978

1977
Arithmetische und Bairesche Operatoren.
Math. Log. Q., 1977

Eine topologische Charakterisierung einiger Klassen regulärer Folgenmengen.
Elektronische Informationsverarbeitung und Kybernetik, 1977

Complexity Hierarchies of Oracles.
Proceedings of the Mathematical Foundations of Computer Science 1977, 1977

Recursive omega-Languages.
FCT, 1977

1976
Arithmetische Operatoren.
Math. Log. Q., 1976

Eine Axiomatisierung der Theorie der regulären Folgenmengen.
Elektronische Informationsverarbeitung und Kybernetik, 1976

1975
Akzeptierbarkeitsgrade regulärer Folgemengen.
Elektronische Informationsverarbeitung und Kybernetik, 1975

A Hierarchy of Regular Sequence Sets.
Proceedings of the Mathematical Foundations of Computer Science 1975, 1975

1974
Zellulare Berechenbarkeit von Funktionen über n-dimensionalen Zeichensystemen.
Elektronische Informationsverarbeitung und Kybernetik, 1974

Automatentheoretische und automatenfreie Charakterisierungen topologischer Klassen regulärer Folgenmengen.
Elektronische Informationsverarbeitung und Kybernetik, 1974

Finite Automata Acceptation of Infinite Sequences.
Proceedings of the Mathematical Foundations of Computer Science, 1974

1973
Universelle Turingmaschinen mit n-dimensionalem Band.
Elektronische Informationsverarbeitung und Kybernetik, 1973

Die Modellierung der Arbeit von Turingmaschinen mit n-dimensionalem Band durch Turingmaschinen mit eindimensionalem Band.
Elektronische Informationsverarbeitung und Kybernetik, 1973


  Loading...