![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
Klaus W. Wagner
Person information
- affiliation: University of Würzburg, Germany
Refine list
![note](https://dblp.dagstuhl.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2010 – 2019
- 2015
- [c36]Marios Mavronicolas
, Burkhard Monien, Klaus W. Wagner:
Weighted Boolean Formula Games. Algorithms, Probability, Networks, and Games 2015: 49-86 - 2014
- [j54]Christian Glaßer, Stephen D. Travers, Klaus W. Wagner:
Perfect correspondences between dot-depth and polynomial-time hierarchies. J. Comput. Syst. Sci. 80(7): 1359-1373 (2014) - 2011
- [j53]Andrei S. Morozov
, Klaus W. Wagner:
Editorial. Theory Comput. Syst. 49(2): 225-226 (2011)
2000 – 2009
- 2009
- [e4]Anna E. Frid, Andrey Morozov, Andrey Rybalchenko, Klaus W. Wagner:
Computer Science - Theory and Applications, Fourth International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Russia, August 18-23, 2009. Proceedings. Lecture Notes in Computer Science 5675, Springer 2009, ISBN 978-3-642-03350-6 [contents] - 2008
- [j52]Victor L. Selivanov, Klaus W. Wagner:
Complexity of Topological Properties of Regular omega-Languages. Fundam. Informaticae 83(1-2): 197-217 (2008) - [j51]Sven Kosub
, Klaus W. Wagner:
The boolean hierarchy of NP-partitions. Inf. Comput. 206(5): 538-568 (2008) - [j50]Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner:
The complexity of unions of disjoint sets. J. Comput. Syst. Sci. 74(7): 1173-1187 (2008) - [c35]Victor L. Selivanov, Klaus W. Wagner:
Complexity of Aperiodicity for Topological Properties of Regular omega-Languages. CiE 2008: 533-543 - [c34]Victor L. Selivanov, Klaus W. Wagner:
Complexity of Topological Properties of Regular omega-Languages. Developments in Language Theory 2008: 529-542 - [e3]Peter Hertling, Victor L. Selivanov, Wolfgang Thomas, William W. Wadge, Klaus W. Wagner:
Topological and Game-Theoretic Aspects of Infinite Computations, 29.06. - 04.07.2008. Dagstuhl Seminar Proceedings 08271, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2008 [contents] - [i10]Peter Hertling, Victor L. Selivanov, Wolfgang Thomas, William W. Wadge, Klaus W. Wagner:
08271 Abstracts Collection - Topological and Game-Theoretic Aspects of Infinite Computations. Topological and Game-Theoretic Aspects of Infinite Computations 2008 - [i9]Peter Hertling, Victor L. Selivanov, Wolfgang Thomas, William W. Wadge, Klaus W. Wagner:
08271 Executive Summary - Topological and Game-Theoretic Aspects of Infinite Computations. Topological and Game-Theoretic Aspects of Infinite Computations 2008 - 2007
- [j49]Pierre McKenzie, Klaus W. Wagner:
The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers. Comput. Complex. 16(3): 211-244 (2007) - [j48]Lane A. Hemaspaandra
, Christopher M. Homan, Sven Kosub
, Klaus W. Wagner:
The Complexity of Computing the Size of an Interval. SIAM J. Comput. 36(5): 1264-1300 (2007) - [c33]Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner:
The Complexity of Unions of Disjoint Sets. STACS 2007: 248-259 - [c32]Marios Mavronicolas
, Burkhard Monien, Klaus W. Wagner:
Weighted Boolean Formula Games. WINE 2007: 469-481 - 2006
- [c31]Christian Glaßer, Stephen D. Travers, Klaus W. Wagner:
Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy. Developments in Language Theory 2006: 408-419 - [i8]Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner:
The Complexity of Unions of Disjoint Sets. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j47]Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner:
Generation problems. Theor. Comput. Sci. 345(2-3): 260-295 (2005) - [j46]Victor L. Selivanov, Klaus W. Wagner:
A reducibility for the dot-depth hierarchy. Theor. Comput. Sci. 345(2-3): 448-472 (2005) - [i7]Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, Klaus W. Wagner:
The Complexity of Computing the Size of an Interval. CoRR abs/cs/0502058 (2005) - [i6]Christian Glaßer, Stephen D. Travers, Klaus W. Wagner:
A Reducibility that Corresponds to Unbalanced Leaf-Language Classes. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j45]Pierre McKenzie, Heribert Vollmer
, Klaus W. Wagner:
Arithmetic Circuits and Polynomial Replacement Systems. SIAM J. Comput. 33(6): 1513-1531 (2004) - [c30]Klaus W. Wagner:
Leaf Language Classes. MCU 2004: 60-81 - [c29]Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner:
Generation Problems. MFCS 2004: 392-403 - [c28]Victor L. Selivanov, Klaus W. Wagner:
A Reducibility for the Dot-Depth Hierarchy. MFCS 2004: 783-793 - [i5]Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner:
Generation Problems. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [b2]Klaus W. Wagner:
Theoretische Informatik - eine kompakte Einführung (2. Aufl.). Springer 2003, ISBN 978-3-540-01313-6, pp. I-X, 1-227 - [c27]Werner Kuich, Klaus W. Wagner:
On the Exponentiation of Languages. FCT 2003: 376-386 - [c26]Pierre McKenzie, Klaus W. Wagner:
The Complexity of Membership Problems for Circuits over Sets of Natural Numbers. STACS 2003: 571-582 - 2001
- [j44]Steffen Reith, Klaus W. Wagner:
On boolean lowness and boolean highness. Theor. Comput. Sci. 261(2): 305-321 (2001) - [c25]Lane A. Hemaspaandra
, Sven Kosub, Klaus W. Wagner:
The Complexity of Computing the Size of an Interval. ICALP 2001: 1040-1051 - 2000
- [j43]Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner:
Characterizing Small Depth and Small Space Classes by Operators of Higher Type. Chic. J. Theor. Comput. Sci. 2000 (2000) - [c24]Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner:
Arithmetic Circuits and Polynomial Replacement Systems. FSTTCS 2000: 164-175 - [c23]Sven Kosub, Klaus W. Wagner:
The Boolean Hierarchy of NP-Partitions. STACS 2000: 157-168
1990 – 1999
- 1998
- [j42]Ronald V. Book, Heribert Vollmer
, Klaus W. Wagner:
Probabilistic Type-2 Operators and "Almost"-Classes. Comput. Complex. 7(3): 265-289 (1998) - [j41]Klaus W. Wagner:
A Note on Parallel Queries and the Symmetric-Difference Hierarchy. Inf. Process. Lett. 66(1): 13-20 (1998) - [j40]Herbert Baier, Klaus W. Wagner:
The Analytic Polynomial Time Hierarchy. Math. Log. Q. 44: 529-544 (1998) - [j39]K. Cronauer, Ulrich Hertrampf, Heribert Vollmer
, Klaus W. Wagner:
The Chain Method to Separate Counting Classes. Theory Comput. Syst. 31(1): 93-108 (1998) - [j38]Herbert Baier, Klaus W. Wagner:
Bounding Queries in the Analytic Polynomial-Time Hierarchy. Theor. Comput. Sci. 207(1): 89-104 (1998) - [c22]Steffen Reith, Klaus W. Wagner:
On Boolean Lowness and Boolean Highness. COCOON 1998: 147-156 - [i4]Heinz Schmitz, Klaus W. Wagner:
The Boolean Hierarchy over Level 1/2 of the Straubing-Therien Hierarchy. CoRR cs.CC/9809118 (1998) - [i3]Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner:
Characterizing Small Depth and Small Space Classes by Operators of Higher Types. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [c21]Heribert Vollmer, Klaus W. Wagner:
Measure One Results in Computational Complexity Theory. Advances in Algorithms, Languages, and Complexity 1997: 285-312 - [c20]Heribert Vollmer
, Klaus W. Wagner:
On Operators of Higher Types. CCC 1997: 174-184 - 1996
- [j37]Diana Rooß, Klaus W. Wagner:
On the Power of DNA-Computing. Inf. Comput. 131(2): 95-109 (1996) - [j36]Ulrich Hertrampf, Heribert Vollmer
, Klaus W. Wagner:
On Balanced Versus Unbalanced Computation Trees. Math. Syst. Theory 29(4): 411-421 (1996) - [j35]Heribert Vollmer
, Klaus W. Wagner:
Recursion Theoretic Characterizations of Complexity Classes of Counting Functions. Theor. Comput. Sci. 163(1&2): 245-258 (1996) - [c19]Ronald V. Book, Heribert Vollmer, Klaus W. Wagner:
On Type-2 Probabilistic Quantifiers. ICALP 1996: 369-380 - [i2]Ronald V. Book, Heribert Vollmer, Klaus W. Wagner:
Probabilistic Type-2 Operators and "Almost"-Classes. Electron. Colloquium Comput. Complex. TR96 (1996) - 1995
- [j34]Heribert Vollmer
, Klaus W. Wagner:
Complexity Classes of Optimization Functions. Inf. Comput. 120(2): 198-219 (1995) - [c18]Ulrich Hertrampf, Heribert Vollmer, Klaus W. Wagner:
On the Power of Number-Theoretic Operations with Respect to Counting. SCT 1995: 299-314 - 1994
- [b1]Klaus W. Wagner:
Einführung in die theoretische Informatik - Grundlagen und Modelle. Springer 1994, ISBN 978-3-540-58139-0, pp. I-X, 1-238 - [j33]Ronald V. Book, Jack H. Lutz, Klaus W. Wagner:
An Observation on Probability Versus Randomness with Applications to Complexity Classes. Math. Syst. Theory 27(3): 201-209 (1994) - [e2]Patrice Enjalbert, Ernst W. Mayr, Klaus W. Wagner:
STACS 94, 11th Annual Symposium on Theoretical Aspects of Computer Science, Caen, France, February 24-26, 1994, Proceedings. Lecture Notes in Computer Science 775, Springer 1994, ISBN 3-540-57785-8 [contents] - 1993
- [j32]Heribert Vollmer, Klaus W. Wagner:
The Complexity of Finding Middle Elements. Int. J. Found. Comput. Sci. 4(4): 293-307 (1993) - [c17]Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner:
On the Power of Polynomial Time Bit-Reductions (Extended Abstract). SCT 1993: 200-207 - [c16]Klaus W. Wagner:
The Alternation Hierarchy for Sublogarithmic Space: An Exciting Race to STACS'93 (Editorial Note). STACS 1993: 2-4 - [p1]Eric Allender, Klaus W. Wagner:
Counting Hierarchies: Polynomial Time and Constant Depth Circuits. Current Trends in Theoretical Computer Science 1993: 469-483 - [e1]Patrice Enjalbert, Alain Finkel, Klaus W. Wagner:
STACS 93, 10th Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25-27, 1993, Proceedings. Lecture Notes in Computer Science 665, Springer 1993, ISBN 3-540-56503-5 [contents] - 1992
- [j31]Juraj Hromkovic, Katsushi Inoue, Branislav Rovan, Anna Slobodová, Itsuo Takanami, Klaus W. Wagner:
On the Power of One-Way Synchronized Alternating Machines with Small Space. Int. J. Found. Comput. Sci. 3(1): 65-79 (1992) - [j30]Thomas Lengauer, Klaus W. Wagner:
The Correlation between the Complexities of the Nonhierarchical and Hierarchical Versions of Graph Problems. J. Comput. Syst. Sci. 44(1): 63-93 (1992) - [c15]Ronald V. Book, Jack H. Lutz, Klaus W. Wagner:
On Complexity Classes and Algorithmically Random Languages (Extended Abstract). STACS 1992: 319-328 - [i1]Ulrich Hertrampf, Clemens Lautemann, Thomas Schwentick, Heribert Vollmer, Klaus W. Wagner:
On the Power of Polynomial Bit-Reductions. Universität Trier, Mathematik/Informatik, Forschungsbericht 92-28 (1992) - 1990
- [j29]Eric Allender, Klaus W. Wagner:
Counting Hierarchies: Polynomial Time and Constant. Bull. EATCS 40: 182-194 (1990) - [j28]Klaus W. Wagner:
Bounded Query Classes. SIAM J. Comput. 19(5): 833-846 (1990) - [j27]Thomas Lengauer, Klaus W. Wagner:
The Binary Network Flow Problem is Logspace Complete for P. Theor. Comput. Sci. 75(3): 357-363 (1990) - [c14]Ulrich Hertrampf, Klaus W. Wagner:
Interactive Proof Systems: Provers, Rounds, and Error Bounds. CSL 1990: 261-273 - [c13]Miroslaw Kowaluk, Klaus W. Wagner:
Vector Language: Simple Description of Hard Instances (Extended Abstract). MFCS 1990: 378-384
1980 – 1989
- 1989
- [j26]Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra
, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung:
The Boolean Hierarchy II: Applications. SIAM J. Comput. 18(1): 95-111 (1989) - 1988
- [j25]Marek Karpinski, Klaus W. Wagner:
The computational complexity of graph problems with succinct multigraph representation. ZOR Methods Model. Oper. Res. 32(3-4): 201-211 (1988) - [j24]Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra
, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung:
The Boolean Hierarchy I: Structural Properties. SIAM J. Comput. 17(6): 1232-1252 (1988) - [c12]Klaus W. Wagner:
Bounded query computations. SCT 1988: 260-277 - [c11]Klaus W. Wagner:
On Restricting the Access to an NP-Oracle. ICALP 1988: 682-696 - [c10]Uwe Schöning, Klaus W. Wagner:
Collapsing Oracle Hierarchies, Census Functions and Logarithmically Many Queries. STACS 1988: 91-97 - 1987
- [j23]Johannes Köbler, Uwe Schöning, Klaus W. Wagner:
The Difference and Truth-Table Hierarchies for NP. RAIRO Theor. Informatics Appl. 21(4): 419-435 (1987) - [j22]Franz-Josef Brandenburg, Andreas Brandstädt, Klaus W. Wagner:
Uniform Simulations of Nondeterministic Real Time Multitape Turing Machines. Math. Syst. Theory 19(4): 277-299 (1987) - [j21]Klaus W. Wagner:
More Complicated Questions About Maxima and Minima, and Some Closures of NP. Theor. Comput. Sci. 51: 53-80 (1987) - [c9]Klaus W. Wagner:
Do There Exist Languages With an Arbitrarily Small Amount of Context-Sensitivity. Computation Theory and Logic 1987: 427-432 - [c8]Thomas Lengauer, Klaus W. Wagner:
The Correlation Between the Complexities of the Nonhierarchical and Hierarchical Versions of Graph Problems. STACS 1987: 100-113 - 1986
- [j20]Klaus W. Wagner:
The Complexity of Combinatorial Problems with Succinct Input Representation. Acta Informatica 23(3): 325-356 (1986) - [j19]Rainer Bodendiek, Klaus W. Wagner:
A characterization of the minimalbasis of the torus. Comb. 6(3): 245-260 (1986) - [j18]Klaus W. Wagner:
On the Intersection of the Class of Linear Context-Free Languages and the Class of Single-Reset Languages. Inf. Process. Lett. 23(3): 143-146 (1986) - [j17]Klaus W. Wagner:
Some Observations on the Connection Between Counting an Recursion. Theor. Comput. Sci. 47(3): 131-147 (1986) - [c7]Klaus W. Wagner:
More Complicated Questions About Maxima and Minima, and Some Closures of NP. ICALP 1986: 434-443 - 1985
- [j16]Rainer Bodendiek, Klaus W. Wagner:
Zur Einbettbarkeit von Graphen in den Torus. Eur. J. Comb. 6(2): 115-127 (1985) - [j15]Rainer Bodendiek, Klaus W. Wagner:
On some minimal graphs of the torus. J. Graph Theory 9(3): 411-417 (1985) - [j14]Jörg Vogel, Klaus W. Wagner:
Two-Way Automata with More than one Storage Medium. Theor. Comput. Sci. 39: 267-280 (1985) - 1984
- [j13]Klaus W. Wagner:
Monotonic Coverings of Finite Sets. J. Inf. Process. Cybern. 20(12): 633-639 (1984) - 1983
- [c6]Andreas Brandstädt, Klaus W. Wagner:
Reversal-Bounded and Visit-Bounded Realtime Computations. FCT 1983: 26-39 - 1982
- [j12]Dietrich Meinhardt, Klaus W. Wagner:
Eine Bemerkung zu einer Arbeit von Monien über Kopfzahl-Hierarchien für Zweiweg-Automaten. J. Inf. Process. Cybern. 18(1/2): 69-74 (1982)
1970 – 1979
- 1979
- [j11]Klaus W. Wagner:
On omega-Regular Sets. Inf. Control. 43(2): 123-177 (1979) - [c5]Klaus W. Wagner:
Bounded Recursion and Complexity Classes. MFCS 1979: 492-498 - 1978
- [j10]Ludwig Staiger, Klaus W. Wagner:
Rekursive Folgenmengen I. Math. Log. Q. 24(31-36): 523-538 (1978) - 1977
- [j9]Klaus W. Wagner:
Eine topologische Charakterisierung einiger Klassen regulärer Folgenmengen. J. Inf. Process. Cybern. 13(9): 473-487 (1977) - [j8]Klaus W. Wagner:
Arithmetische und Bairesche Operatoren. Math. Log. Q. 23(7-12): 181-191 (1977) - [c4]Klaus W. Wagner, Ludwig Staiger:
Recursive omega-Languages. FCT 1977: 532-537 - [c3]Klaus W. Wagner, Gerd Wechsung:
Complexity Hierarchies of Oracles. MFCS 1977: 543-548 - 1976
- [j7]Klaus W. Wagner:
Eine Axiomatisierung der Theorie der regulären Folgenmengen. J. Inf. Process. Cybern. 12(7): 337-354 (1976) - [j6]Klaus W. Wagner:
Arithmetische Operatoren. Math. Log. Q. 22(1): 553-570 (1976) - 1975
- [j5]Klaus W. Wagner:
Akzeptierbarkeitsgrade regulärer Folgemengen. J. Inf. Process. Cybern. 11(10-12): 626-630 (1975) - [c2]Klaus W. Wagner:
A Hierarchy of Regular Sequence Sets. MFCS 1975: 445-449 - 1974
- [j4]Klaus W. Wagner:
Zellulare Berechenbarkeit von Funktionen über n-dimensionalen Zeichensystemen. J. Inf. Process. Cybern. 10(5/6): 259-269 (1974) - [j3]Ludwig Staiger, Klaus W. Wagner:
Automatentheoretische und automatenfreie Charakterisierungen topologischer Klassen regulärer Folgenmengen. J. Inf. Process. Cybern. 10(7): 379-392 (1974) - [c1]Klaus W. Wagner, Ludwig Staiger:
Finite Automata Acceptation of Infinite Sequences. MFCS 1974: 69-72 - 1973
- [j2]Klaus W. Wagner:
Die Modellierung der Arbeit von Turingmaschinen mit n-dimensionalem Band durch Turingmaschinen mit eindimensionalem Band. J. Inf. Process. Cybern. 9(3): 121-135 (1973) - [j1]Klaus W. Wagner:
Universelle Turingmaschinen mit n-dimensionalem Band. J. Inf. Process. Cybern. 9(7/8): 423-431 (1973)
Coauthor Index
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-30 20:10 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint