Heribert Vollmer
- Konferenz- und Workshop-Veröffentlichungen
- Journal-Veröffentlichungen
- Bücher
- Buchteile
- Vordrucke und Technische Berichte
Jahr: –1995 (10) , 1996–2001 (45) , 2002–2007 (36) , 2008–2013 (63) , 2014–2019 (47) , 2020–2022 (10)
Logik, Philosophie und Wissenschaftstheorie
2021
[BIB]
Woher kommt der Geist?
In: Markus Iff et al., Hrsg.: Superintelligenz? Möglichkeiten und Grenzen Künstlicher Intelligenz in interdisziplinärer Perspektive, Verlag Peter Lang, Berlin 2021: 79-104.
[BIB]
Geist im Kosmos.
Die Tagespost vom 20.05.2021, 74(20): 25 (2021).
[BIB]
Grenzen unserer Erkenntnis.
Die Tagespost vom 08.07.2021, 74(27): 25 (2021).
[BIB]
"Gott macht, dass die Dinge sich selber machen", Pierre Teilhard de Chardin oder das Rekursionsgesetz von Bewusstsein und Komplexität.
Die Tagespost vom 16.12.2021, 74(59): 25 (2021).
2019
[BIB]
Künstlicher Geist?
Christ in der Gegenwart 71(1): 17-18 (2019).
2018
[BIB]
Die Zukunft der Menschheit - Pierre Teilhard de Chardin und die Künstliche Intelligenz.
Herder Korrespondenz 72(11): 28-32 (2018).
2016
[BIB]
Leibniz and the Development of Modal Logic in the 20th Century.
In: Wenchao Li et al., Hrsg.: Für unser Glück oder das Glück anderer. Vorträge des X. Internationalen Leibniz-Kongresses, Band V, Georg Olms Verlag, Hildesheim Zürich New York 2016: 595-608.
[BIB]
Auctor Informaticae - Gottfried Wilhelm Leibniz: Der erste Informatiker.
Unimagazin/Forschungsmagazin der Leibniz Universität Hannover, Ausgabe 01/02: Leibniz 2016: 40-43 (2016).
Populärwissenschaftliche Artikel
2001
[BIB]
Wer wird Millionär? Komplexitätstheorie: Konzepte und Herausforderungen.
c’t Magazin für Computertechnik, Heft 7: 240-251 (2001).
1999
[BIB]
Was leistet die Komplexitätstheorie für die Praxis?
Informatik Spektrum 22(5): 317-327 (1999).
Theoretische Informatik
2022
[BIB]
Enumeration Classes Defined by Circuits.
CoRR abs/2205.00539 (2022).
2021
[BIB]
A Logical Characterization of Constant-Depth Circuits over the Reals.
WoLLIC 2021: 16-30.
[BIB]
Descriptive complexity of #P functions: A new perspective.
J. Comput. Syst. Sci. 116: 40-54 (2021).
2020
[BIB]
Satisfiability of Modal Inclusion Logic: Lax and Strict Semantics.
ACM Trans. Comput. Log. 21(1): 7:1-7:18 (2020).
[BIB]
Enumerating Teams in First-Order Team Logics.
CoRR abs/2006.06953 (2020).
[BIB]
A Logical Characterization of Constant-Depth Circuits over the Reals.
CoRR abs/2005.04916 (2020).
2019
[BIB]
Counting of Teams in First-Order Team Logics.
CoRR abs/1902.00246 (2019).
[BIB]
Logics for Dependence and Independence (Dagstuhl Seminar 19031).
Dagstuhl Reports 9(1): 28-46 (2019).
[BIB]
A model-theoretic characterization of constant-depth arithmetic circuits.
Ann. Pure Appl. Log. 170(9): 1008-1029 (2019).
[BIB]
A complexity theory for hard enumeration problems.
Discret. Appl. Math. 268: 191-209 (2019).
[BIB]
Parameterised Enumeration for Modification Problems.
Algorithms 12(9): 189 (2019).
[BIB]
Counting of Teams in First-Order Team Logics.
MFCS 2019: 19:1-19:15.
[BIB]
Guest Editorial: Special Issue on Theoretical Aspects of Computer Science.
Theory Comput. Syst. 63(5): 923-925 (2019).
2018
[BIB]
Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth.
LICS 2018: 354-363.
[BIB]
Preface of STACS 2016 Special Issue.
Theory Comput. Syst. 62(1): 1-3 (2018).
[BIB]
Complexity of Propositional Logics in Team Semantic.
ACM Trans. Comput. Log. 19(1): 2:1-2:14 (2018).
2017
[BIB]
On the Complexity of Hard Enumeration Problems.
LATA 2017: 183-195.
[BIB]
Modal independence logic.
J. Log. Comput. 27(5): 1333-1352 (2017).
[BIB]
Paradigms for Parameterized Enumeration.
Theory Comput. Syst. 60(4): 737-758 (2017).
[BIB]
Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth.
CoRR abs/1710.01934 (2017).
2016
[BIB]
Descriptive Complexity of #AC0 Functions.
CoRR abs/1604.06617 (2016).
[BIB]
Descriptive Complexity of #AC0 Functions.
CSL 2016: 20:1-20:16.
[BIB]
A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits.
WoLLIC 2016: 234-248.
[BIB]
Dependence Logic, Theory and Applications.
Springer 2016. ISBN 978-3-319-31803-5.
[BIB]
Expressivity and Complexity of Dependence Logic.
Dependence Logic 2016: 5-32.
[BIB]
On the Complexity of Hard Enumeration Problems.
CoRR abs/1610.05493 (2016).
[BIB]
A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits.
CoRR abs/1603.09531 (2016).
[BIB]
SAT and Interactions (Dagstuhl Seminar 16381).
Dagstuhl Reports 6(9): 74-93 (2016).
[BIB]
Introduction.
Dependence Logic 2016: 1-3.
2015
[BIB]
Complexity of Propositional Independence and Inclusion Logic.
CoRR abs/1504.06135 (2015).
[BIB]
Parameterized Complexity of Weighted Satisfiability Problems: Decision, Enumeration, Counting.
Fundam. Informaticae 136(4): 297-316 (2015).
[BIB]
Dependence Logic with a Majority Quantifier.
J. Log. Lang. Inf. 24(3): 289-305 (2015).
[BIB]
Complexity of Propositional Independence and Inclusion Logic.
MFCS (1) 2015: 269-280.
[BIB]
A Van Benthem Theorem for Modal Team Semantics.
CSL 2015: 277-291.
[BIB]
On the parameterized complexity of non-monotonic logics.
Arch. Math. Log. 54(5-6): 685-710 (2015).
[BIB]
Logics for Dependence and Independence (Dagstuhl Seminar 15261).
Dagstuhl Reports 5(6): 70-85 (2015).
[BIB]
Parameterized Enumeration for Modification Problems.
LATA 2015: 524-536.
[BIB]
Satisfiability of Modal Inclusion Logic: Lax and Strict Semantics.
CoRR abs/1504.06409 (2015).
[BIB]
Circuits, Logic and Games (Dagstuhl Seminar 15401).
Dagstuhl Reports 5(9): 105-124 (2015).
[BIB]
Modal Inclusion Logic: Being Lax is Simpler than Being Strict.
MFCS (1) 2015: 281-292.
Aktualisierte Version im arXiv.
[BIB]
Komplexität von Algorithmen.
Mathematik für Anwendungen 4. Lehmanns Media 2015. ISBN 978-3-86541-761-9.
[BIB]
Erratum: The Complexity of Satisfiability for Fragments of CTL and CTL⋆.
Int. J. Found. Comput. Sci. 26(8): 1189- (2015).
Erratum zu Arne Meier, Michael Thomas, Heribert Vollmer, Martin Mundhenk: The Complexity of Satisfiability for Fragments of CTL and CTL*. Int. J. Found. Comput. Sci. 20(5): 901-918 (2009).
2014
[BIB]
A Fragment of Dependence Logic Capturing Polynomial Time.
Log. Methods Comput. Sci. 10(3) (2014).
[BIB]
Modal Independence Logic.
Advances in Modal Logic 2014: 353-372.
[BIB]
LoCo - A Logic for Configuration Problems.
ACM Trans. Comput. Log. 15(3): 20:1-20:25 (2014).
[BIB]
Modal Independence Logic.
CoRR abs/1404.0144 (2014).
[BIB]
A Van Benthem Theorem for Modal Team Semantics.
CoRR abs/1410.6648 (2014).
2013
[BIB]
Verifying proofs in constant depth.
ACM Trans. Comput. Theory 5(1): 2:1-2:23 (2013).
[BIB]
Complexity Results for Modal Dependence Logic.
Stud Logica 101(2): 343-366 (2013).
[BIB]
Paradigms for Parameterized Enumeration.
MFCS 2013: 290-301.
[BIB]
Dependence Logic: Theory and Applications (Dagstuhl Seminar 13071).
Dagstuhl Reports 3(2): 45-54 (2013).
[BIB]
Extended Modal Dependence Logic.
WoLLIC 2013: 126-137.
[BIB]
Model Checking for Modal Dependence Logic: An Approach Through Post's Lattice.
CoRR abs/1303.6424 (2013).
[BIB]
Parameterized Enumeration with Ordering.
CoRR abs/1309.5009 (2013).
[BIB]
Paradigms for Parameterized Enumeration.
CoRR abs/1306.2171 (2013).
[BIB]
Model Checking for Modal Dependence Logic: An Approach through Post's Lattice.
WoLLIC 2013: 238-250.
2012
[BIB]
Counting classes and the fine structure between NC1 and L.
Theor. Comput. Sci. 417: 36-49 (2012).
[BIB]
Verifying Proofs in Constant Depth.
Electron. Colloquium Comput. Complex. 19: 79 (2012).
[BIB]
Complexity of Model Checking for Logics over Kripke models.
Bull. EATCS 108: 49-89 (2012).
[BIB]
LoCo - A Logic for Configuration Problems.
ECAI 2012: 73-78.
[BIB]
On the Parameterized Complexity of Default Logic and Autoepistemic Logic.
LATA 2012: 389-400.
[BIB]
Parameterized Complexity of Weighted Satisfiability Problems.
SAT 2012: 341-354.
[BIB]
The complexity of reasoning for fragments of default logic.
J. Log. Comput. 22(3): 587-604 (2012).
[BIB]
The Complexity of Reasoning for Fragments of Autoepistemic Logic.
ACM Trans. Comput. Log. 13(2): 17:1-17:22 (2012).
[BIB]
SAT Interactions (Dagstuhl Seminar 12471).
Dagstuhl Reports 2(11): 87-101 (2012).
2011
[BIB]
Verifying Proofs in Constant Depth.
MFCS 2011: 84-95.
[BIB]
Dependence logic with a majority quantifier.
CoRR abs/1109.4750 (2011).
[BIB]
Model Checking CTL is Almost Always Inherently Sequential.
Log. Methods Comput. Sci. 7(2) (2011).
[BIB]
Dependence logic with a majority quantifier.
FSTTCS 2011: 252-263.
[BIB]
Proof complexity of propositional default logic.
Arch. Math. Log. 50(7-8): 727-742 (2011).
[BIB]
The tractability of model checking for LTL: The good, the bad, and the ugly fragments.
ACM Trans. Comput. Log. 12(2): 13:1-13:28 (2011).
[BIB]
Complexity Results for Modal Dependence Logic.
CoRR abs/1104.0607 (2011).
[BIB]
On the Parameterized Complexity of Default Logic and Autoepistemic Logic.
CoRR abs/1110.0623 (2011).
[BIB]
Algorithms Unplugged.
Springer 2011. ISBN 978-3-642-15327-3.
2010
[BIB]
Counting Classes and the Fine Structure between NC1 and L.
MFCS 2010: 306-317.
[BIB]
Counting Classes and the Fine Structure between NC1 and L.
Electron. Colloquium Comput. Complex. 17: 101 (2010).
[BIB]
Complexity of non-monotonic logics.
Bull. EATCS 102: 53-82 (2010).
[BIB]
Boolean Circuits as a Data Structure for Boolean Functions: Efficient Algorithms and Hard Problems.
Log. Methods Comput. Sci. 8(3) (2010).
[BIB]
On Second-Order Monadic Monoidal and Groupoidal Quantifiers.
Log. Methods Comput. Sci. 6(3) (2010).
[BIB]
Complexity Results for Modal Dependence Logic.
CSL 2010: 411-425.
[BIB]
Proof Complexity of Propositional Default Logic.
SAT 2010: 30-43.
[BIB]
The Complexity of Problems for Quantified Constraints.
Theory Comput. Syst. 47(2): 454-490 (2010).
[BIB]
Extensional Uniformity for Boolean Circuits.
SIAM J. Comput. 39(7): 3186-3206 (2010).
[BIB]
Proof Complexity of Propositional Default Logic.
Circuits, Logic, and Games 2010.
[BIB]
The Complexity of Reasoning for Fragments of Autoepistemic Logic.
Circuits, Logic, and Games 2010.
[BIB]
Complexity Results for Modal Dependence Logic.
Circuits, Logic, and Games 2010.
[BIB]
10061 Abstracts Collection - Circuits, Logic, and Games.
Circuits, Logic, and Games 2010.
[BIB]
10061 Executive Summary - Circuits, Logic, and Games.
Circuits, Logic, and Games 2010.
[BIB]
The Complexity of Reasoning for Fragments of Autoepistemic Logic.
CoRR abs/1006.0220 (2010).
[BIB]
Complexity of Non-Monotonic Logics.
CoRR abs/1009.1990 (2010).
2009
[BIB]
The complexity of satisfiability problems: Refining Schaefer's theorem.
J. Comput. Syst. Sci. 75(4): 245-254 (2009).
[BIB]
The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments.
Electron. Notes Theor. Comput. Sci. 231: 277-292 (2009).
[BIB]
The Complexity of Generalized Satisfiability for Linear Temporal Logic.
Log. Methods Comput. Sci. 5(1) (2009).
[BIB]
The Complexity of Reasoning for Fragments of Default Logic.
SAT 2009: 51-64.
[BIB]
Model Checking CTL is Almost Always Inherently Sequential.
TIME 2009: 21-28.
[BIB]
The complexity of propositional implication.
Inf. Process. Lett. 109(18): 1071-1077 (2009).
[BIB]
The Complexity of Deciding if a Boolean Function Can Be Computed by Circuits over a Restricted Basis.
Theory Comput. Syst. 44(1): 82-90 (2009).
[BIB]
The Complexity of Satisfiability for Fragments of CTL and CTL*.
Int. J. Found. Comput. Sci. 20(5): 901-918 (2009).
Zugehöriges Erratum vorhanden.
2008
[BIB]
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments.
Electron. Colloquium Comput. Complex. 15(028) (2008).
[BIB]
The Complexity of Satisfiability for Fragments of CTL and CTL*.
Workshop on Reachability Problems, published in Electron. Notes Theor. Comput. Sci., volume 223, 2008: 201-213.
[BIB]
Boolean Constraint Satisfaction Problems: When Does Post's Lattice Help?.
Complexity of Constraints 2008: 3-37.
[BIB]
On Second-Order Monadic Groupoidal Quantifiers.
WoLLIC 2008: 238-248.
[BIB]
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments.
CoRR abs/0805.0498 (2008).
[BIB]
Extensional Uniformity for Boolean Circuits.
CoRR abs/0805.4072 (2008).
[BIB]
The Complexity of Reasoning for Fragments of Default Logic.
CoRR abs/0808.3884 (2008).
[BIB]
The Complexity of Propositional Implication.
CoRR abs/0811.0959 (2008).
[BIB]
Extensional Uniformity for Boolean Circuits.
CSL 2008: 64-78.
[BIB]
Taschenbuch der Algorithmen.
Springer 2008. ISBN 978-3-540-76393-2.
2007
[BIB]
The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis.
Electron. Colloquium Comput. Complex. 14(045) (2007).
[BIB]
The Complexity of Problems for Quantified Constraints.
Electron. Colloquium Comput. Complex. 14(023) (2007).
[BIB]
The Complexity of Generalized Satisfiability for Linear Temporal Logic.
FoSSaCS 2007: 48-62.
[BIB]
Computational Complexity of Constraint Satisfaction.
CiE 2007: 748-757.
2006
[BIB]
The Complexity of Generalized Satisfiability for Linear Temporal Logic.
Electron. Colloquium Comput. Complex. 13(153) (2006).
[BIB]
The many faces of a translation.
J. Comput. Syst. Sci. 72(1): 163-179 (2006).
[BIB]
Exploiting practical limitations of UML diagrams for model validation and execution.
Softw. Syst. Model. 5(1): 26-47 (2006).
[BIB]
06401 Executive Summary - Complexity of Constraints.
Complexity of Constraints 2006.
[BIB]
06401 Abstracts Collection - Complexity of Constraints.
Complexity of Constraints 2006.
[BIB]
06451 Executive Summary -- Circuits, Logic, and Games .
Circuits, Logic, and Games 2006.
[BIB]
06451 Abstracts Collection -- Circuits, Logic, and Games .
Circuits, Logic, and Games 2006.
2005
[BIB]
Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation.
Electron. Colloquium Comput. Complex.(024) (2005).
[BIB]
Functions computable in polynomial space.
Inf. Comput. 198(1): 56-70 (2005).
[BIB]
The complexity of base station positioning in cellular networks.
Discret. Appl. Math. 148(1): 1-12 (2005).
[BIB]
Bases for Boolean co-clones.
Inf. Process. Lett. 96(2): 59-66 (2005).
[BIB]
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.
MFCS 2005: 71-82.
2004
[BIB]
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.
Electron. Colloquium Comput. Complex.(100) (2004).
[BIB]
An Algebraic Approach to the Complexity of Generalized Conjunctive Queries.
SAT 2004.
[BIB]
Arithmetic Circuits and Polynomial Replacement Systems.
SIAM J. Comput. 33(6): 1513-1531 (2004).
[BIB]
The Complexity of Boolean Constraint Isomorphism.
STACS 2004: 164-175.
[BIB]
An Algebraic Approach to the Complexity of Generalized Conjunctive Queries.
SAT (Selected Papers 2004: 30-45.
[BIB]
First-order logic with groupoidal quantifiers.
ESSLLI 2003, Collecium Logicum Vol. VI, Kurt-Gödel-Society 2004: 71-105.
[BIB]
Playing with Boolean Blocks, Part II: Constraint Satisfaction Problems.
(2004).
2003
[BIB]
Functions Computable in Polynomial Space.
Electron. Colloquium Comput. Complex. 10(018) (2003).
[BIB]
Optimal satisfiability for propositional calculi and constraint satisfaction problems.
Inf. Comput. 186(1): 1-19 (2003).
[BIB]
The Complexity of Boolean Constraint Isomorphism.
CoRR cs.CC/0306134 (2003).
[BIB]
Generic separations and leaf languages.
Math. Log. Q. 49(4): 353-362 (2003).
[BIB]
On the Autoreducibility of Random Sequences.
SIAM J. Comput. 32(6): 1542-1569 (2003).
[BIB]
Complexity Theory Made Easy.
Developments in Language Theory 2003: 95-110.
[BIB]
Playing with Boolean Blocks, Part I: Post's Lattice with Applications to Complexity Theory.
(2003).
2002
[BIB]
On the Autoreducibility of Random Sequences.
Electron. Colloquium Comput. Complex.(056) (2002).
[BIB]
Equivalence and Isomorphism for Boolean Constraint Satisfaction.
CoRR cs.CC/0202036 (2002).
[BIB]
Equivalence and Isomorphism for Boolean Constraint Satisfaction.
CSL 2002: 412-426.
[BIB]
Boolean Functions and Post’s Lattice with Applications to Complexity Theory.
(2002).
Lecture Notes for Logic and Interaction 2002.
2001
[BIB]
The Descriptive Complexity Approach to LOGCFL.
J. Comput. Syst. Sci. 62(4): 629-652 (2001).
[BIB]
Finite Automata with Generalized Acceptance Criteria.
Discret. Math. Theor. Comput. Sci. 4(2): 179-192 (2001).
[BIB]
A polynomial-time approximation scheme for base station positioning in UMTS networks.
DIAL-M 2001: 52-59.
[BIB]
Partially-Ordered Two-Way Automata: A New Characterization of DA.
Developments in Language Theory 2001: 239-250.
[BIB]
A Generalization of the Büchi-Elgot-Trakhtenbrot Theorem.
CSL 2001: 355-368.
[BIB]
Ist P=NP? Einführung in die Theorie der NP-Vollständigkeit.
(2001).
Technischer Bericht.
2000
[BIB]
Characterizing Small Depth and Small Space Classes by Operators of Higher Type.
Chic. J. Theor. Comput. Sci. 2000 (2000).
[BIB]
On the Autoreducibility of Random Sequences.
MFCS 2000: 333-342.
[BIB]
Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems.
MFCS 2000: 640-649.
[BIB]
Uniform Characterizations of Complexity Classes of Functions.
Int. J. Found. Comput. Sci. 11(4): 525-551 (2000).
[BIB]
A note on closure properties of logspace MOD classes.
Inf. Process. Lett. 75(3): 91-93 (2000).
[BIB]
The Complexity of Base Station Positioning in Cellular Networks.
ICALP Satellite Workshops 2000: 167-178.
[BIB]
Arithmetic Circuits and Polynomial Replacement Systems.
FSTTCS 2000: 164-175.
[BIB]
The Many Faces of a Translation.
ICALP 2000: 890-901.
1999
[BIB]
Complements of Multivalued Functions.
Chic. J. Theor. Comput. Sci. 1999 (1999).
[BIB]
Uniform characterizations of complexity classes.
SIGACT News 30(1): 17-27 (1999).
[BIB]
Finite Automata with Generalized Acceptance Criteria.
ICALP 1999: 605-614.
[BIB]
The Descriptive Complexity Approach to LOGCFL.
STACS 1999: 444-454.
[BIB]
Introduction to Circuit Complexity - A Uniform Approach.
Springer 1999. ISBN 978-3-662-03927-4.
1998
[BIB]
The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae.
Electron. Colloquium Comput. Complex. 5(22) (1998).
[BIB]
Characterizing Small Depth and Small Space Classes by Operators of Higher Types.
Electron. Colloquium Comput. Complex. 5(57) (1998).
[BIB]
The Descriptive Complexity Approach to LOGCFL.
Electron. Colloquium Comput. Complex. 5(59) (1998).
[BIB]
Relating Polynomial Time to Constant Depth.
Theor. Comput. Sci. 207(1): 159-170 (1998).
[BIB]
Nondeterministic NC1 Computation.
J. Comput. Syst. Sci. 57(2): 200-212 (1998).
[BIB]
Probabilistic Type-2 Operators and "Almost"-Classes.
Comput. Complex. 7(3): 265-289 (1998).
[BIB]
The descriptive complexity approach to LOGCFL.
CoRR cs.CC/9809114 (1998).
[BIB]
A Generalized Quantifier Concept in Computational Complexity Theory.
CoRR cs.CC/9809115 (1998).
[BIB]
The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae.
CoRR cs.CC/9809116 (1998).
[BIB]
Uniformly Defining Complexity Classes of Functions.
STACS 1998: 607-617.
[BIB]
The Chain Method to Separate Counting Classes.
Theory Comput. Syst. 31(1): 93-108 (1998).
[BIB]
Lindström Quantifiers and Leaf Language Definability.
Int. J. Found. Comput. Sci. 9(3): 277-294 (1998).
1997
[BIB]
Gap-Languages and Log-Time Complexity Classes.
Theor. Comput. Sci. 188(1-2): 101-116 (1997).
[BIB]
On Operators of Higher Types.
Computational Complexity Conference 1997: 174-184.
[BIB]
A Generalized Quantifier Concept in Computational Complexity Theory.
ESSLLI 1997: 99-123.
[BIB]
Measure One Results in Computational Complexity Theory.
Advances in Algorithms, Languages, and Complexity 1997: 285-312.
1996
[BIB]
Lindstroem Quantifiers and Leaf Language Definability.
Electron. Colloquium Comput. Complex. 3(5) (1996).
[BIB]
Probabilistic Type-2 Operators and "Almost"-Classes.
Electron. Colloquium Comput. Complex. 3(35) (1996).
[BIB]
Recursion Theoretic Characterizations of Complexity Classes of Counting Functions.
Theor. Comput. Sci. 163(1&2): 245-258 (1996).
[BIB]
On Balanced Versus Unbalanced Computation Trees.
Math. Syst. Theory 29(4): 411-421 (1996).
[BIB]
Nondeterministic NC1 Computation.
Computational Complexity Conference 1996: 12-21.
[BIB]
Complements of Multivalued Functions.
Computational Complexity Conference 1996: 260-269.
[BIB]
Relations Among Parallel and Sequential Computation Models.
ASIAN 1996: 23-32.
[BIB]
On Type-2 Probabilistic Quantifiers.
ICALP 1996: 369-380.
1995
[BIB]
Complexity Classes of Optimization Functions.
Inf. Comput. 120(2): 198-219 (1995).
[BIB]
On the Power of Number-Theoretic Operations with Respect to Counting.
Computational Complexity Conference 1995: 299-314.
[BIB]
The satanic notations: counting classes beyond #P and other definitional adventures.
SIGACT News 26(1): 2-13 (1995).
1994
[BIB]
Komplexitätsklassen von Funktionen.
Julius Maximilians University Würzburg, Germany 1994.
[BIB]
On Different Reducibility Notions for Function Classes.
STACS 1994: 449-460.
1993
[BIB]
On the Power of Polynomial Time Bit-Reductions (Extended Abstract).
Computational Complexity Conference 1993: 200-207.
[BIB]
The Complexity of Finding Middle Elements.
Int. J. Found. Comput. Sci. 4(4): 293-307 (1993).
1992
[BIB]
On the Power of Polynomial Bit-Reductions.
Universität Trier, Mathematik/Informatik, Forschungsbericht 92-28 (1992).
1990
[BIB]
The Gap-Language-Technique Revisited.
CSL 1990: 389-399.
2021
[BIB]
Woher kommt der Geist? In: Markus Iff et al., Hrsg.: Superintelligenz? Möglichkeiten und Grenzen Künstlicher Intelligenz in interdisziplinärer Perspektive, Verlag Peter Lang, Berlin 2021: 79-104.[BIB]
Geist im Kosmos. Die Tagespost vom 20.05.2021, 74(20): 25 (2021).[BIB]
Grenzen unserer Erkenntnis. Die Tagespost vom 08.07.2021, 74(27): 25 (2021).[BIB]
"Gott macht, dass die Dinge sich selber machen", Pierre Teilhard de Chardin oder das Rekursionsgesetz von Bewusstsein und Komplexität. Die Tagespost vom 16.12.2021, 74(59): 25 (2021).
2019
[BIB]
Künstlicher Geist? Christ in der Gegenwart 71(1): 17-18 (2019).
2018
[BIB]
Die Zukunft der Menschheit - Pierre Teilhard de Chardin und die Künstliche Intelligenz. Herder Korrespondenz 72(11): 28-32 (2018).
2016
[BIB]
Leibniz and the Development of Modal Logic in the 20th Century. In: Wenchao Li et al., Hrsg.: Für unser Glück oder das Glück anderer. Vorträge des X. Internationalen Leibniz-Kongresses, Band V, Georg Olms Verlag, Hildesheim Zürich New York 2016: 595-608.[BIB]
Auctor Informaticae - Gottfried Wilhelm Leibniz: Der erste Informatiker. Unimagazin/Forschungsmagazin der Leibniz Universität Hannover, Ausgabe 01/02: Leibniz 2016: 40-43 (2016).
2001
[BIB]
Wer wird Millionär? Komplexitätstheorie: Konzepte und Herausforderungen. c’t Magazin für Computertechnik, Heft 7: 240-251 (2001).
1999
[BIB]
Was leistet die Komplexitätstheorie für die Praxis? Informatik Spektrum 22(5): 317-327 (1999).
Theoretische Informatik
2022
[BIB]
Enumeration Classes Defined by Circuits.
CoRR abs/2205.00539 (2022).
2021
[BIB]
A Logical Characterization of Constant-Depth Circuits over the Reals.
WoLLIC 2021: 16-30.
[BIB]
Descriptive complexity of #P functions: A new perspective.
J. Comput. Syst. Sci. 116: 40-54 (2021).
2020
[BIB]
Satisfiability of Modal Inclusion Logic: Lax and Strict Semantics.
ACM Trans. Comput. Log. 21(1): 7:1-7:18 (2020).
[BIB]
Enumerating Teams in First-Order Team Logics.
CoRR abs/2006.06953 (2020).
[BIB]
A Logical Characterization of Constant-Depth Circuits over the Reals.
CoRR abs/2005.04916 (2020).
2019
[BIB]
Counting of Teams in First-Order Team Logics.
CoRR abs/1902.00246 (2019).
[BIB]
Logics for Dependence and Independence (Dagstuhl Seminar 19031).
Dagstuhl Reports 9(1): 28-46 (2019).
[BIB]
A model-theoretic characterization of constant-depth arithmetic circuits.
Ann. Pure Appl. Log. 170(9): 1008-1029 (2019).
[BIB]
A complexity theory for hard enumeration problems.
Discret. Appl. Math. 268: 191-209 (2019).
[BIB]
Parameterised Enumeration for Modification Problems.
Algorithms 12(9): 189 (2019).
[BIB]
Counting of Teams in First-Order Team Logics.
MFCS 2019: 19:1-19:15.
[BIB]
Guest Editorial: Special Issue on Theoretical Aspects of Computer Science.
Theory Comput. Syst. 63(5): 923-925 (2019).
2018
[BIB]
Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth.
LICS 2018: 354-363.
[BIB]
Preface of STACS 2016 Special Issue.
Theory Comput. Syst. 62(1): 1-3 (2018).
[BIB]
Complexity of Propositional Logics in Team Semantic.
ACM Trans. Comput. Log. 19(1): 2:1-2:14 (2018).
2017
[BIB]
On the Complexity of Hard Enumeration Problems.
LATA 2017: 183-195.
[BIB]
Modal independence logic.
J. Log. Comput. 27(5): 1333-1352 (2017).
[BIB]
Paradigms for Parameterized Enumeration.
Theory Comput. Syst. 60(4): 737-758 (2017).
[BIB]
Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth.
CoRR abs/1710.01934 (2017).
2016
[BIB]
Descriptive Complexity of #AC0 Functions.
CoRR abs/1604.06617 (2016).
[BIB]
Descriptive Complexity of #AC0 Functions.
CSL 2016: 20:1-20:16.
[BIB]
A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits.
WoLLIC 2016: 234-248.
[BIB]
Dependence Logic, Theory and Applications.
Springer 2016. ISBN 978-3-319-31803-5.
[BIB]
Expressivity and Complexity of Dependence Logic.
Dependence Logic 2016: 5-32.
[BIB]
On the Complexity of Hard Enumeration Problems.
CoRR abs/1610.05493 (2016).
[BIB]
A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits.
CoRR abs/1603.09531 (2016).
[BIB]
SAT and Interactions (Dagstuhl Seminar 16381).
Dagstuhl Reports 6(9): 74-93 (2016).
[BIB]
Introduction.
Dependence Logic 2016: 1-3.
2015
[BIB]
Complexity of Propositional Independence and Inclusion Logic.
CoRR abs/1504.06135 (2015).
[BIB]
Parameterized Complexity of Weighted Satisfiability Problems: Decision, Enumeration, Counting.
Fundam. Informaticae 136(4): 297-316 (2015).
[BIB]
Dependence Logic with a Majority Quantifier.
J. Log. Lang. Inf. 24(3): 289-305 (2015).
[BIB]
Complexity of Propositional Independence and Inclusion Logic.
MFCS (1) 2015: 269-280.
[BIB]
A Van Benthem Theorem for Modal Team Semantics.
CSL 2015: 277-291.
[BIB]
On the parameterized complexity of non-monotonic logics.
Arch. Math. Log. 54(5-6): 685-710 (2015).
[BIB]
Logics for Dependence and Independence (Dagstuhl Seminar 15261).
Dagstuhl Reports 5(6): 70-85 (2015).
[BIB]
Parameterized Enumeration for Modification Problems.
LATA 2015: 524-536.
[BIB]
Satisfiability of Modal Inclusion Logic: Lax and Strict Semantics.
CoRR abs/1504.06409 (2015).
[BIB]
Circuits, Logic and Games (Dagstuhl Seminar 15401).
Dagstuhl Reports 5(9): 105-124 (2015).
[BIB]
Modal Inclusion Logic: Being Lax is Simpler than Being Strict.
MFCS (1) 2015: 281-292.
Aktualisierte Version im arXiv.
[BIB]
Komplexität von Algorithmen.
Mathematik für Anwendungen 4. Lehmanns Media 2015. ISBN 978-3-86541-761-9.
[BIB]
Erratum: The Complexity of Satisfiability for Fragments of CTL and CTL⋆.
Int. J. Found. Comput. Sci. 26(8): 1189- (2015).
Erratum zu Arne Meier, Michael Thomas, Heribert Vollmer, Martin Mundhenk: The Complexity of Satisfiability for Fragments of CTL and CTL*. Int. J. Found. Comput. Sci. 20(5): 901-918 (2009).
2014
[BIB]
A Fragment of Dependence Logic Capturing Polynomial Time.
Log. Methods Comput. Sci. 10(3) (2014).
[BIB]
Modal Independence Logic.
Advances in Modal Logic 2014: 353-372.
[BIB]
LoCo - A Logic for Configuration Problems.
ACM Trans. Comput. Log. 15(3): 20:1-20:25 (2014).
[BIB]
Modal Independence Logic.
CoRR abs/1404.0144 (2014).
[BIB]
A Van Benthem Theorem for Modal Team Semantics.
CoRR abs/1410.6648 (2014).
2013
[BIB]
Verifying proofs in constant depth.
ACM Trans. Comput. Theory 5(1): 2:1-2:23 (2013).
[BIB]
Complexity Results for Modal Dependence Logic.
Stud Logica 101(2): 343-366 (2013).
[BIB]
Paradigms for Parameterized Enumeration.
MFCS 2013: 290-301.
[BIB]
Dependence Logic: Theory and Applications (Dagstuhl Seminar 13071).
Dagstuhl Reports 3(2): 45-54 (2013).
[BIB]
Extended Modal Dependence Logic.
WoLLIC 2013: 126-137.
[BIB]
Model Checking for Modal Dependence Logic: An Approach Through Post's Lattice.
CoRR abs/1303.6424 (2013).
[BIB]
Parameterized Enumeration with Ordering.
CoRR abs/1309.5009 (2013).
[BIB]
Paradigms for Parameterized Enumeration.
CoRR abs/1306.2171 (2013).
[BIB]
Model Checking for Modal Dependence Logic: An Approach through Post's Lattice.
WoLLIC 2013: 238-250.
2012
[BIB]
Counting classes and the fine structure between NC1 and L.
Theor. Comput. Sci. 417: 36-49 (2012).
[BIB]
Verifying Proofs in Constant Depth.
Electron. Colloquium Comput. Complex. 19: 79 (2012).
[BIB]
Complexity of Model Checking for Logics over Kripke models.
Bull. EATCS 108: 49-89 (2012).
[BIB]
LoCo - A Logic for Configuration Problems.
ECAI 2012: 73-78.
[BIB]
On the Parameterized Complexity of Default Logic and Autoepistemic Logic.
LATA 2012: 389-400.
[BIB]
Parameterized Complexity of Weighted Satisfiability Problems.
SAT 2012: 341-354.
[BIB]
The complexity of reasoning for fragments of default logic.
J. Log. Comput. 22(3): 587-604 (2012).
[BIB]
The Complexity of Reasoning for Fragments of Autoepistemic Logic.
ACM Trans. Comput. Log. 13(2): 17:1-17:22 (2012).
[BIB]
SAT Interactions (Dagstuhl Seminar 12471).
Dagstuhl Reports 2(11): 87-101 (2012).
2011
[BIB]
Verifying Proofs in Constant Depth.
MFCS 2011: 84-95.
[BIB]
Dependence logic with a majority quantifier.
CoRR abs/1109.4750 (2011).
[BIB]
Model Checking CTL is Almost Always Inherently Sequential.
Log. Methods Comput. Sci. 7(2) (2011).
[BIB]
Dependence logic with a majority quantifier.
FSTTCS 2011: 252-263.
[BIB]
Proof complexity of propositional default logic.
Arch. Math. Log. 50(7-8): 727-742 (2011).
[BIB]
The tractability of model checking for LTL: The good, the bad, and the ugly fragments.
ACM Trans. Comput. Log. 12(2): 13:1-13:28 (2011).
[BIB]
Complexity Results for Modal Dependence Logic.
CoRR abs/1104.0607 (2011).
[BIB]
On the Parameterized Complexity of Default Logic and Autoepistemic Logic.
CoRR abs/1110.0623 (2011).
[BIB]
Algorithms Unplugged.
Springer 2011. ISBN 978-3-642-15327-3.
2010
[BIB]
Counting Classes and the Fine Structure between NC1 and L.
MFCS 2010: 306-317.
[BIB]
Counting Classes and the Fine Structure between NC1 and L.
Electron. Colloquium Comput. Complex. 17: 101 (2010).
[BIB]
Complexity of non-monotonic logics.
Bull. EATCS 102: 53-82 (2010).
[BIB]
Boolean Circuits as a Data Structure for Boolean Functions: Efficient Algorithms and Hard Problems.
Log. Methods Comput. Sci. 8(3) (2010).
[BIB]
On Second-Order Monadic Monoidal and Groupoidal Quantifiers.
Log. Methods Comput. Sci. 6(3) (2010).
[BIB]
Complexity Results for Modal Dependence Logic.
CSL 2010: 411-425.
[BIB]
Proof Complexity of Propositional Default Logic.
SAT 2010: 30-43.
[BIB]
The Complexity of Problems for Quantified Constraints.
Theory Comput. Syst. 47(2): 454-490 (2010).
[BIB]
Extensional Uniformity for Boolean Circuits.
SIAM J. Comput. 39(7): 3186-3206 (2010).
[BIB]
Proof Complexity of Propositional Default Logic.
Circuits, Logic, and Games 2010.
[BIB]
The Complexity of Reasoning for Fragments of Autoepistemic Logic.
Circuits, Logic, and Games 2010.
[BIB]
Complexity Results for Modal Dependence Logic.
Circuits, Logic, and Games 2010.
[BIB]
10061 Abstracts Collection - Circuits, Logic, and Games.
Circuits, Logic, and Games 2010.
[BIB]
10061 Executive Summary - Circuits, Logic, and Games.
Circuits, Logic, and Games 2010.
[BIB]
The Complexity of Reasoning for Fragments of Autoepistemic Logic.
CoRR abs/1006.0220 (2010).
[BIB]
Complexity of Non-Monotonic Logics.
CoRR abs/1009.1990 (2010).
2009
[BIB]
The complexity of satisfiability problems: Refining Schaefer's theorem.
J. Comput. Syst. Sci. 75(4): 245-254 (2009).
[BIB]
The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments.
Electron. Notes Theor. Comput. Sci. 231: 277-292 (2009).
[BIB]
The Complexity of Generalized Satisfiability for Linear Temporal Logic.
Log. Methods Comput. Sci. 5(1) (2009).
[BIB]
The Complexity of Reasoning for Fragments of Default Logic.
SAT 2009: 51-64.
[BIB]
Model Checking CTL is Almost Always Inherently Sequential.
TIME 2009: 21-28.
[BIB]
The complexity of propositional implication.
Inf. Process. Lett. 109(18): 1071-1077 (2009).
[BIB]
The Complexity of Deciding if a Boolean Function Can Be Computed by Circuits over a Restricted Basis.
Theory Comput. Syst. 44(1): 82-90 (2009).
[BIB]
The Complexity of Satisfiability for Fragments of CTL and CTL*.
Int. J. Found. Comput. Sci. 20(5): 901-918 (2009).
Zugehöriges Erratum vorhanden.
2008
[BIB]
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments.
Electron. Colloquium Comput. Complex. 15(028) (2008).
[BIB]
The Complexity of Satisfiability for Fragments of CTL and CTL*.
Workshop on Reachability Problems, published in Electron. Notes Theor. Comput. Sci., volume 223, 2008: 201-213.
[BIB]
Boolean Constraint Satisfaction Problems: When Does Post's Lattice Help?.
Complexity of Constraints 2008: 3-37.
[BIB]
On Second-Order Monadic Groupoidal Quantifiers.
WoLLIC 2008: 238-248.
[BIB]
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments.
CoRR abs/0805.0498 (2008).
[BIB]
Extensional Uniformity for Boolean Circuits.
CoRR abs/0805.4072 (2008).
[BIB]
The Complexity of Reasoning for Fragments of Default Logic.
CoRR abs/0808.3884 (2008).
[BIB]
The Complexity of Propositional Implication.
CoRR abs/0811.0959 (2008).
[BIB]
Extensional Uniformity for Boolean Circuits.
CSL 2008: 64-78.
[BIB]
Taschenbuch der Algorithmen.
Springer 2008. ISBN 978-3-540-76393-2.
2007
[BIB]
The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis.
Electron. Colloquium Comput. Complex. 14(045) (2007).
[BIB]
The Complexity of Problems for Quantified Constraints.
Electron. Colloquium Comput. Complex. 14(023) (2007).
[BIB]
The Complexity of Generalized Satisfiability for Linear Temporal Logic.
FoSSaCS 2007: 48-62.
[BIB]
Computational Complexity of Constraint Satisfaction.
CiE 2007: 748-757.
2006
[BIB]
The Complexity of Generalized Satisfiability for Linear Temporal Logic.
Electron. Colloquium Comput. Complex. 13(153) (2006).
[BIB]
The many faces of a translation.
J. Comput. Syst. Sci. 72(1): 163-179 (2006).
[BIB]
Exploiting practical limitations of UML diagrams for model validation and execution.
Softw. Syst. Model. 5(1): 26-47 (2006).
[BIB]
06401 Executive Summary - Complexity of Constraints.
Complexity of Constraints 2006.
[BIB]
06401 Abstracts Collection - Complexity of Constraints.
Complexity of Constraints 2006.
[BIB]
06451 Executive Summary -- Circuits, Logic, and Games .
Circuits, Logic, and Games 2006.
[BIB]
06451 Abstracts Collection -- Circuits, Logic, and Games .
Circuits, Logic, and Games 2006.
2005
[BIB]
Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation.
Electron. Colloquium Comput. Complex.(024) (2005).
[BIB]
Functions computable in polynomial space.
Inf. Comput. 198(1): 56-70 (2005).
[BIB]
The complexity of base station positioning in cellular networks.
Discret. Appl. Math. 148(1): 1-12 (2005).
[BIB]
Bases for Boolean co-clones.
Inf. Process. Lett. 96(2): 59-66 (2005).
[BIB]
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.
MFCS 2005: 71-82.
2004
[BIB]
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem.
Electron. Colloquium Comput. Complex.(100) (2004).
[BIB]
An Algebraic Approach to the Complexity of Generalized Conjunctive Queries.
SAT 2004.
[BIB]
Arithmetic Circuits and Polynomial Replacement Systems.
SIAM J. Comput. 33(6): 1513-1531 (2004).
[BIB]
The Complexity of Boolean Constraint Isomorphism.
STACS 2004: 164-175.
[BIB]
An Algebraic Approach to the Complexity of Generalized Conjunctive Queries.
SAT (Selected Papers 2004: 30-45.
[BIB]
First-order logic with groupoidal quantifiers.
ESSLLI 2003, Collecium Logicum Vol. VI, Kurt-Gödel-Society 2004: 71-105.
[BIB]
Playing with Boolean Blocks, Part II: Constraint Satisfaction Problems.
(2004).
2003
[BIB]
Functions Computable in Polynomial Space.
Electron. Colloquium Comput. Complex. 10(018) (2003).
[BIB]
Optimal satisfiability for propositional calculi and constraint satisfaction problems.
Inf. Comput. 186(1): 1-19 (2003).
[BIB]
The Complexity of Boolean Constraint Isomorphism.
CoRR cs.CC/0306134 (2003).
[BIB]
Generic separations and leaf languages.
Math. Log. Q. 49(4): 353-362 (2003).
[BIB]
On the Autoreducibility of Random Sequences.
SIAM J. Comput. 32(6): 1542-1569 (2003).
[BIB]
Complexity Theory Made Easy.
Developments in Language Theory 2003: 95-110.
[BIB]
Playing with Boolean Blocks, Part I: Post's Lattice with Applications to Complexity Theory.
(2003).
2002
[BIB]
On the Autoreducibility of Random Sequences.
Electron. Colloquium Comput. Complex.(056) (2002).
[BIB]
Equivalence and Isomorphism for Boolean Constraint Satisfaction.
CoRR cs.CC/0202036 (2002).
[BIB]
Equivalence and Isomorphism for Boolean Constraint Satisfaction.
CSL 2002: 412-426.
[BIB]
Boolean Functions and Post’s Lattice with Applications to Complexity Theory.
(2002).
Lecture Notes for Logic and Interaction 2002.
2001
[BIB]
The Descriptive Complexity Approach to LOGCFL.
J. Comput. Syst. Sci. 62(4): 629-652 (2001).
[BIB]
Finite Automata with Generalized Acceptance Criteria.
Discret. Math. Theor. Comput. Sci. 4(2): 179-192 (2001).
[BIB]
A polynomial-time approximation scheme for base station positioning in UMTS networks.
DIAL-M 2001: 52-59.
[BIB]
Partially-Ordered Two-Way Automata: A New Characterization of DA.
Developments in Language Theory 2001: 239-250.
[BIB]
A Generalization of the Büchi-Elgot-Trakhtenbrot Theorem.
CSL 2001: 355-368.
[BIB]
Ist P=NP? Einführung in die Theorie der NP-Vollständigkeit.
(2001).
Technischer Bericht.
2000
[BIB]
Characterizing Small Depth and Small Space Classes by Operators of Higher Type.
Chic. J. Theor. Comput. Sci. 2000 (2000).
[BIB]
On the Autoreducibility of Random Sequences.
MFCS 2000: 333-342.
[BIB]
Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems.
MFCS 2000: 640-649.
[BIB]
Uniform Characterizations of Complexity Classes of Functions.
Int. J. Found. Comput. Sci. 11(4): 525-551 (2000).
[BIB]
A note on closure properties of logspace MOD classes.
Inf. Process. Lett. 75(3): 91-93 (2000).
[BIB]
The Complexity of Base Station Positioning in Cellular Networks.
ICALP Satellite Workshops 2000: 167-178.
[BIB]
Arithmetic Circuits and Polynomial Replacement Systems.
FSTTCS 2000: 164-175.
[BIB]
The Many Faces of a Translation.
ICALP 2000: 890-901.
1999
[BIB]
Complements of Multivalued Functions.
Chic. J. Theor. Comput. Sci. 1999 (1999).
[BIB]
Uniform characterizations of complexity classes.
SIGACT News 30(1): 17-27 (1999).
[BIB]
Finite Automata with Generalized Acceptance Criteria.
ICALP 1999: 605-614.
[BIB]
The Descriptive Complexity Approach to LOGCFL.
STACS 1999: 444-454.
[BIB]
Introduction to Circuit Complexity - A Uniform Approach.
Springer 1999. ISBN 978-3-662-03927-4.
1998
[BIB]
The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae.
Electron. Colloquium Comput. Complex. 5(22) (1998).
[BIB]
Characterizing Small Depth and Small Space Classes by Operators of Higher Types.
Electron. Colloquium Comput. Complex. 5(57) (1998).
[BIB]
The Descriptive Complexity Approach to LOGCFL.
Electron. Colloquium Comput. Complex. 5(59) (1998).
[BIB]
Relating Polynomial Time to Constant Depth.
Theor. Comput. Sci. 207(1): 159-170 (1998).
[BIB]
Nondeterministic NC1 Computation.
J. Comput. Syst. Sci. 57(2): 200-212 (1998).
[BIB]
Probabilistic Type-2 Operators and "Almost"-Classes.
Comput. Complex. 7(3): 265-289 (1998).
[BIB]
The descriptive complexity approach to LOGCFL.
CoRR cs.CC/9809114 (1998).
[BIB]
A Generalized Quantifier Concept in Computational Complexity Theory.
CoRR cs.CC/9809115 (1998).
[BIB]
The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae.
CoRR cs.CC/9809116 (1998).
[BIB]
Uniformly Defining Complexity Classes of Functions.
STACS 1998: 607-617.
[BIB]
The Chain Method to Separate Counting Classes.
Theory Comput. Syst. 31(1): 93-108 (1998).
[BIB]
Lindström Quantifiers and Leaf Language Definability.
Int. J. Found. Comput. Sci. 9(3): 277-294 (1998).
1997
[BIB]
Gap-Languages and Log-Time Complexity Classes.
Theor. Comput. Sci. 188(1-2): 101-116 (1997).
[BIB]
On Operators of Higher Types.
Computational Complexity Conference 1997: 174-184.
[BIB]
A Generalized Quantifier Concept in Computational Complexity Theory.
ESSLLI 1997: 99-123.
[BIB]
Measure One Results in Computational Complexity Theory.
Advances in Algorithms, Languages, and Complexity 1997: 285-312.
1996
[BIB]
Lindstroem Quantifiers and Leaf Language Definability.
Electron. Colloquium Comput. Complex. 3(5) (1996).
[BIB]
Probabilistic Type-2 Operators and "Almost"-Classes.
Electron. Colloquium Comput. Complex. 3(35) (1996).
[BIB]
Recursion Theoretic Characterizations of Complexity Classes of Counting Functions.
Theor. Comput. Sci. 163(1&2): 245-258 (1996).
[BIB]
On Balanced Versus Unbalanced Computation Trees.
Math. Syst. Theory 29(4): 411-421 (1996).
[BIB]
Nondeterministic NC1 Computation.
Computational Complexity Conference 1996: 12-21.
[BIB]
Complements of Multivalued Functions.
Computational Complexity Conference 1996: 260-269.
[BIB]
Relations Among Parallel and Sequential Computation Models.
ASIAN 1996: 23-32.
[BIB]
On Type-2 Probabilistic Quantifiers.
ICALP 1996: 369-380.
1995
[BIB]
Complexity Classes of Optimization Functions.
Inf. Comput. 120(2): 198-219 (1995).
[BIB]
On the Power of Number-Theoretic Operations with Respect to Counting.
Computational Complexity Conference 1995: 299-314.
[BIB]
The satanic notations: counting classes beyond #P and other definitional adventures.
SIGACT News 26(1): 2-13 (1995).
1994
[BIB]
Komplexitätsklassen von Funktionen.
Julius Maximilians University Würzburg, Germany 1994.
[BIB]
On Different Reducibility Notions for Function Classes.
STACS 1994: 449-460.
1993
[BIB]
On the Power of Polynomial Time Bit-Reductions (Extended Abstract).
Computational Complexity Conference 1993: 200-207.
[BIB]
The Complexity of Finding Middle Elements.
Int. J. Found. Comput. Sci. 4(4): 293-307 (1993).
1992
[BIB]
On the Power of Polynomial Bit-Reductions.
Universität Trier, Mathematik/Informatik, Forschungsbericht 92-28 (1992).
1990
[BIB]
The Gap-Language-Technique Revisited.
CSL 1990: 389-399.
2022
[BIB]
Enumeration Classes Defined by Circuits. CoRR abs/2205.00539 (2022).
2021
[BIB]
A Logical Characterization of Constant-Depth Circuits over the Reals. WoLLIC 2021: 16-30.[BIB]
Descriptive complexity of #P functions: A new perspective. J. Comput. Syst. Sci. 116: 40-54 (2021).
2020
[BIB]
Satisfiability of Modal Inclusion Logic: Lax and Strict Semantics. ACM Trans. Comput. Log. 21(1): 7:1-7:18 (2020).[BIB]
Enumerating Teams in First-Order Team Logics. CoRR abs/2006.06953 (2020).[BIB]
A Logical Characterization of Constant-Depth Circuits over the Reals. CoRR abs/2005.04916 (2020).
2019
[BIB]
Counting of Teams in First-Order Team Logics. CoRR abs/1902.00246 (2019).[BIB]
Logics for Dependence and Independence (Dagstuhl Seminar 19031). Dagstuhl Reports 9(1): 28-46 (2019).[BIB]
A model-theoretic characterization of constant-depth arithmetic circuits. Ann. Pure Appl. Log. 170(9): 1008-1029 (2019).[BIB]
A complexity theory for hard enumeration problems. Discret. Appl. Math. 268: 191-209 (2019).[BIB]
Parameterised Enumeration for Modification Problems. Algorithms 12(9): 189 (2019).[BIB]
Counting of Teams in First-Order Team Logics. MFCS 2019: 19:1-19:15.[BIB]
Guest Editorial: Special Issue on Theoretical Aspects of Computer Science. Theory Comput. Syst. 63(5): 923-925 (2019).
2018
[BIB]
Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth. LICS 2018: 354-363.[BIB]
Preface of STACS 2016 Special Issue. Theory Comput. Syst. 62(1): 1-3 (2018).[BIB]
Complexity of Propositional Logics in Team Semantic. ACM Trans. Comput. Log. 19(1): 2:1-2:14 (2018).
2017
[BIB]
On the Complexity of Hard Enumeration Problems. LATA 2017: 183-195.[BIB]
Modal independence logic. J. Log. Comput. 27(5): 1333-1352 (2017).[BIB]
Paradigms for Parameterized Enumeration. Theory Comput. Syst. 60(4): 737-758 (2017).[BIB]
Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth. CoRR abs/1710.01934 (2017).
2016
[BIB]
Descriptive Complexity of #AC0 Functions. CoRR abs/1604.06617 (2016).[BIB]
Descriptive Complexity of #AC0 Functions. CSL 2016: 20:1-20:16.[BIB]
A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits. WoLLIC 2016: 234-248.[BIB]
Dependence Logic, Theory and Applications. Springer 2016. ISBN 978-3-319-31803-5.[BIB]
Expressivity and Complexity of Dependence Logic. Dependence Logic 2016: 5-32.[BIB]
On the Complexity of Hard Enumeration Problems. CoRR abs/1610.05493 (2016).[BIB]
A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits. CoRR abs/1603.09531 (2016).[BIB]
SAT and Interactions (Dagstuhl Seminar 16381). Dagstuhl Reports 6(9): 74-93 (2016).[BIB]
Introduction. Dependence Logic 2016: 1-3.
2015
[BIB]
Complexity of Propositional Independence and Inclusion Logic. CoRR abs/1504.06135 (2015).[BIB]
Parameterized Complexity of Weighted Satisfiability Problems: Decision, Enumeration, Counting. Fundam. Informaticae 136(4): 297-316 (2015).[BIB]
Dependence Logic with a Majority Quantifier. J. Log. Lang. Inf. 24(3): 289-305 (2015).[BIB]
Complexity of Propositional Independence and Inclusion Logic. MFCS (1) 2015: 269-280.[BIB]
A Van Benthem Theorem for Modal Team Semantics. CSL 2015: 277-291.[BIB]
On the parameterized complexity of non-monotonic logics. Arch. Math. Log. 54(5-6): 685-710 (2015).[BIB]
Logics for Dependence and Independence (Dagstuhl Seminar 15261). Dagstuhl Reports 5(6): 70-85 (2015).[BIB]
Parameterized Enumeration for Modification Problems. LATA 2015: 524-536.[BIB]
Satisfiability of Modal Inclusion Logic: Lax and Strict Semantics. CoRR abs/1504.06409 (2015).[BIB]
Circuits, Logic and Games (Dagstuhl Seminar 15401). Dagstuhl Reports 5(9): 105-124 (2015).[BIB]
Modal Inclusion Logic: Being Lax is Simpler than Being Strict. MFCS (1) 2015: 281-292. Aktualisierte Version im arXiv.[BIB]
Komplexität von Algorithmen. Mathematik für Anwendungen 4. Lehmanns Media 2015. ISBN 978-3-86541-761-9.[BIB]
Erratum: The Complexity of Satisfiability for Fragments of CTL and CTL⋆. Int. J. Found. Comput. Sci. 26(8): 1189- (2015). Erratum zu Arne Meier, Michael Thomas, Heribert Vollmer, Martin Mundhenk: The Complexity of Satisfiability for Fragments of CTL and CTL*. Int. J. Found. Comput. Sci. 20(5): 901-918 (2009).
2014
[BIB]
A Fragment of Dependence Logic Capturing Polynomial Time. Log. Methods Comput. Sci. 10(3) (2014).[BIB]
Modal Independence Logic. Advances in Modal Logic 2014: 353-372.[BIB]
LoCo - A Logic for Configuration Problems. ACM Trans. Comput. Log. 15(3): 20:1-20:25 (2014).[BIB]
Modal Independence Logic. CoRR abs/1404.0144 (2014).[BIB]
A Van Benthem Theorem for Modal Team Semantics. CoRR abs/1410.6648 (2014).
2013
[BIB]
Verifying proofs in constant depth. ACM Trans. Comput. Theory 5(1): 2:1-2:23 (2013).[BIB]
Complexity Results for Modal Dependence Logic. Stud Logica 101(2): 343-366 (2013).[BIB]
Paradigms for Parameterized Enumeration. MFCS 2013: 290-301.[BIB]
Dependence Logic: Theory and Applications (Dagstuhl Seminar 13071). Dagstuhl Reports 3(2): 45-54 (2013).[BIB]
Extended Modal Dependence Logic. WoLLIC 2013: 126-137.[BIB]
Model Checking for Modal Dependence Logic: An Approach Through Post's Lattice. CoRR abs/1303.6424 (2013).[BIB]
Parameterized Enumeration with Ordering. CoRR abs/1309.5009 (2013).[BIB]
Paradigms for Parameterized Enumeration. CoRR abs/1306.2171 (2013).[BIB]
Model Checking for Modal Dependence Logic: An Approach through Post's Lattice. WoLLIC 2013: 238-250.
2012
[BIB]
Counting classes and the fine structure between NC1 and L. Theor. Comput. Sci. 417: 36-49 (2012).[BIB]
Verifying Proofs in Constant Depth. Electron. Colloquium Comput. Complex. 19: 79 (2012).[BIB]
Complexity of Model Checking for Logics over Kripke models. Bull. EATCS 108: 49-89 (2012).[BIB]
LoCo - A Logic for Configuration Problems. ECAI 2012: 73-78.[BIB]
On the Parameterized Complexity of Default Logic and Autoepistemic Logic. LATA 2012: 389-400.[BIB]
Parameterized Complexity of Weighted Satisfiability Problems. SAT 2012: 341-354.[BIB]
The complexity of reasoning for fragments of default logic. J. Log. Comput. 22(3): 587-604 (2012).[BIB]
The Complexity of Reasoning for Fragments of Autoepistemic Logic. ACM Trans. Comput. Log. 13(2): 17:1-17:22 (2012).[BIB]
SAT Interactions (Dagstuhl Seminar 12471). Dagstuhl Reports 2(11): 87-101 (2012).
2011
[BIB]
Verifying Proofs in Constant Depth. MFCS 2011: 84-95.[BIB]
Dependence logic with a majority quantifier. CoRR abs/1109.4750 (2011).[BIB]
Model Checking CTL is Almost Always Inherently Sequential. Log. Methods Comput. Sci. 7(2) (2011).[BIB]
Dependence logic with a majority quantifier. FSTTCS 2011: 252-263.[BIB]
Proof complexity of propositional default logic. Arch. Math. Log. 50(7-8): 727-742 (2011).[BIB]
The tractability of model checking for LTL: The good, the bad, and the ugly fragments. ACM Trans. Comput. Log. 12(2): 13:1-13:28 (2011).[BIB]
Complexity Results for Modal Dependence Logic. CoRR abs/1104.0607 (2011).[BIB]
On the Parameterized Complexity of Default Logic and Autoepistemic Logic. CoRR abs/1110.0623 (2011).[BIB]
Algorithms Unplugged. Springer 2011. ISBN 978-3-642-15327-3.
2010
[BIB]
Counting Classes and the Fine Structure between NC1 and L. MFCS 2010: 306-317.[BIB]
Counting Classes and the Fine Structure between NC1 and L. Electron. Colloquium Comput. Complex. 17: 101 (2010).[BIB]
Complexity of non-monotonic logics. Bull. EATCS 102: 53-82 (2010).[BIB]
Boolean Circuits as a Data Structure for Boolean Functions: Efficient Algorithms and Hard Problems. Log. Methods Comput. Sci. 8(3) (2010).[BIB]
On Second-Order Monadic Monoidal and Groupoidal Quantifiers. Log. Methods Comput. Sci. 6(3) (2010).[BIB]
Complexity Results for Modal Dependence Logic. CSL 2010: 411-425.[BIB]
Proof Complexity of Propositional Default Logic. SAT 2010: 30-43.[BIB]
The Complexity of Problems for Quantified Constraints. Theory Comput. Syst. 47(2): 454-490 (2010).[BIB]
Extensional Uniformity for Boolean Circuits. SIAM J. Comput. 39(7): 3186-3206 (2010).[BIB]
Proof Complexity of Propositional Default Logic. Circuits, Logic, and Games 2010.[BIB]
The Complexity of Reasoning for Fragments of Autoepistemic Logic. Circuits, Logic, and Games 2010.[BIB]
Complexity Results for Modal Dependence Logic. Circuits, Logic, and Games 2010.[BIB]
10061 Abstracts Collection - Circuits, Logic, and Games. Circuits, Logic, and Games 2010.[BIB]
10061 Executive Summary - Circuits, Logic, and Games. Circuits, Logic, and Games 2010.[BIB]
The Complexity of Reasoning for Fragments of Autoepistemic Logic. CoRR abs/1006.0220 (2010).[BIB]
Complexity of Non-Monotonic Logics. CoRR abs/1009.1990 (2010).
2009
[BIB]
The complexity of satisfiability problems: Refining Schaefer's theorem. J. Comput. Syst. Sci. 75(4): 245-254 (2009).[BIB]
The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments. Electron. Notes Theor. Comput. Sci. 231: 277-292 (2009).[BIB]
The Complexity of Generalized Satisfiability for Linear Temporal Logic. Log. Methods Comput. Sci. 5(1) (2009).[BIB]
The Complexity of Reasoning for Fragments of Default Logic. SAT 2009: 51-64.[BIB]
Model Checking CTL is Almost Always Inherently Sequential. TIME 2009: 21-28.[BIB]
The complexity of propositional implication. Inf. Process. Lett. 109(18): 1071-1077 (2009).[BIB]
The Complexity of Deciding if a Boolean Function Can Be Computed by Circuits over a Restricted Basis. Theory Comput. Syst. 44(1): 82-90 (2009).[BIB]
The Complexity of Satisfiability for Fragments of CTL and CTL*. Int. J. Found. Comput. Sci. 20(5): 901-918 (2009). Zugehöriges Erratum vorhanden.
2008
[BIB]
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments. Electron. Colloquium Comput. Complex. 15(028) (2008).[BIB]
The Complexity of Satisfiability for Fragments of CTL and CTL*. Workshop on Reachability Problems, published in Electron. Notes Theor. Comput. Sci., volume 223, 2008: 201-213.[BIB]
Boolean Constraint Satisfaction Problems: When Does Post's Lattice Help?. Complexity of Constraints 2008: 3-37.[BIB]
On Second-Order Monadic Groupoidal Quantifiers. WoLLIC 2008: 238-248.[BIB]
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments. CoRR abs/0805.0498 (2008).[BIB]
Extensional Uniformity for Boolean Circuits. CoRR abs/0805.4072 (2008).[BIB]
The Complexity of Reasoning for Fragments of Default Logic. CoRR abs/0808.3884 (2008).[BIB]
The Complexity of Propositional Implication. CoRR abs/0811.0959 (2008).[BIB]
Extensional Uniformity for Boolean Circuits. CSL 2008: 64-78.[BIB]
Taschenbuch der Algorithmen. Springer 2008. ISBN 978-3-540-76393-2.
2007
[BIB]
The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis. Electron. Colloquium Comput. Complex. 14(045) (2007).[BIB]
The Complexity of Problems for Quantified Constraints. Electron. Colloquium Comput. Complex. 14(023) (2007).[BIB]
The Complexity of Generalized Satisfiability for Linear Temporal Logic. FoSSaCS 2007: 48-62.[BIB]
Computational Complexity of Constraint Satisfaction. CiE 2007: 748-757.
2006
[BIB]
The Complexity of Generalized Satisfiability for Linear Temporal Logic. Electron. Colloquium Comput. Complex. 13(153) (2006).[BIB]
The many faces of a translation. J. Comput. Syst. Sci. 72(1): 163-179 (2006).[BIB]
Exploiting practical limitations of UML diagrams for model validation and execution. Softw. Syst. Model. 5(1): 26-47 (2006).[BIB]
06401 Executive Summary - Complexity of Constraints. Complexity of Constraints 2006.[BIB]
06401 Abstracts Collection - Complexity of Constraints. Complexity of Constraints 2006.[BIB]
06451 Executive Summary -- Circuits, Logic, and Games . Circuits, Logic, and Games 2006.[BIB]
06451 Abstracts Collection -- Circuits, Logic, and Games . Circuits, Logic, and Games 2006.
2005
[BIB]
Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation. Electron. Colloquium Comput. Complex.(024) (2005).[BIB]
Functions computable in polynomial space. Inf. Comput. 198(1): 56-70 (2005).[BIB]
The complexity of base station positioning in cellular networks. Discret. Appl. Math. 148(1): 1-12 (2005).[BIB]
Bases for Boolean co-clones. Inf. Process. Lett. 96(2): 59-66 (2005).[BIB]
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem. MFCS 2005: 71-82.
2004
[BIB]
The Complexity of Satisfiability Problems: Refining Schaefer's Theorem. Electron. Colloquium Comput. Complex.(100) (2004).[BIB]
An Algebraic Approach to the Complexity of Generalized Conjunctive Queries. SAT 2004.[BIB]
Arithmetic Circuits and Polynomial Replacement Systems. SIAM J. Comput. 33(6): 1513-1531 (2004).[BIB]
The Complexity of Boolean Constraint Isomorphism. STACS 2004: 164-175.[BIB]
An Algebraic Approach to the Complexity of Generalized Conjunctive Queries. SAT (Selected Papers 2004: 30-45.[BIB]
First-order logic with groupoidal quantifiers. ESSLLI 2003, Collecium Logicum Vol. VI, Kurt-Gödel-Society 2004: 71-105.[BIB]
Playing with Boolean Blocks, Part II: Constraint Satisfaction Problems. (2004).
2003
[BIB]
Functions Computable in Polynomial Space. Electron. Colloquium Comput. Complex. 10(018) (2003).[BIB]
Optimal satisfiability for propositional calculi and constraint satisfaction problems. Inf. Comput. 186(1): 1-19 (2003).[BIB]
The Complexity of Boolean Constraint Isomorphism. CoRR cs.CC/0306134 (2003).[BIB]
Generic separations and leaf languages. Math. Log. Q. 49(4): 353-362 (2003).[BIB]
On the Autoreducibility of Random Sequences. SIAM J. Comput. 32(6): 1542-1569 (2003).[BIB]
Complexity Theory Made Easy. Developments in Language Theory 2003: 95-110.[BIB]
Playing with Boolean Blocks, Part I: Post's Lattice with Applications to Complexity Theory. (2003).
2002
[BIB]
On the Autoreducibility of Random Sequences. Electron. Colloquium Comput. Complex.(056) (2002).[BIB]
Equivalence and Isomorphism for Boolean Constraint Satisfaction. CoRR cs.CC/0202036 (2002).[BIB]
Equivalence and Isomorphism for Boolean Constraint Satisfaction. CSL 2002: 412-426.[BIB]
Boolean Functions and Post’s Lattice with Applications to Complexity Theory. (2002). Lecture Notes for Logic and Interaction 2002.
2001
[BIB]
The Descriptive Complexity Approach to LOGCFL. J. Comput. Syst. Sci. 62(4): 629-652 (2001).[BIB]
Finite Automata with Generalized Acceptance Criteria. Discret. Math. Theor. Comput. Sci. 4(2): 179-192 (2001).[BIB]
A polynomial-time approximation scheme for base station positioning in UMTS networks. DIAL-M 2001: 52-59.[BIB]
Partially-Ordered Two-Way Automata: A New Characterization of DA. Developments in Language Theory 2001: 239-250.[BIB]
A Generalization of the Büchi-Elgot-Trakhtenbrot Theorem. CSL 2001: 355-368.[BIB]
Ist P=NP? Einführung in die Theorie der NP-Vollständigkeit. (2001). Technischer Bericht.
2000
[BIB]
Characterizing Small Depth and Small Space Classes by Operators of Higher Type. Chic. J. Theor. Comput. Sci. 2000 (2000).[BIB]
On the Autoreducibility of Random Sequences. MFCS 2000: 333-342.[BIB]
Optimal Satisfiability for Propositional Calculi and Constraint Satisfaction Problems. MFCS 2000: 640-649.[BIB]
Uniform Characterizations of Complexity Classes of Functions. Int. J. Found. Comput. Sci. 11(4): 525-551 (2000).[BIB]
A note on closure properties of logspace MOD classes. Inf. Process. Lett. 75(3): 91-93 (2000).[BIB]
The Complexity of Base Station Positioning in Cellular Networks. ICALP Satellite Workshops 2000: 167-178.[BIB]
Arithmetic Circuits and Polynomial Replacement Systems. FSTTCS 2000: 164-175.[BIB]
The Many Faces of a Translation. ICALP 2000: 890-901.
1999
[BIB]
Complements of Multivalued Functions. Chic. J. Theor. Comput. Sci. 1999 (1999).[BIB]
Uniform characterizations of complexity classes. SIGACT News 30(1): 17-27 (1999).[BIB]
Finite Automata with Generalized Acceptance Criteria. ICALP 1999: 605-614.[BIB]
The Descriptive Complexity Approach to LOGCFL. STACS 1999: 444-454.[BIB]
Introduction to Circuit Complexity - A Uniform Approach. Springer 1999. ISBN 978-3-662-03927-4.
1998
[BIB]
The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae. Electron. Colloquium Comput. Complex. 5(22) (1998).[BIB]
Characterizing Small Depth and Small Space Classes by Operators of Higher Types. Electron. Colloquium Comput. Complex. 5(57) (1998).[BIB]
The Descriptive Complexity Approach to LOGCFL. Electron. Colloquium Comput. Complex. 5(59) (1998).[BIB]
Relating Polynomial Time to Constant Depth. Theor. Comput. Sci. 207(1): 159-170 (1998).[BIB]
Nondeterministic NC1 Computation. J. Comput. Syst. Sci. 57(2): 200-212 (1998).[BIB]
Probabilistic Type-2 Operators and "Almost"-Classes. Comput. Complex. 7(3): 265-289 (1998).[BIB]
The descriptive complexity approach to LOGCFL. CoRR cs.CC/9809114 (1998).[BIB]
A Generalized Quantifier Concept in Computational Complexity Theory. CoRR cs.CC/9809115 (1998).[BIB]
The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae. CoRR cs.CC/9809116 (1998).[BIB]
Uniformly Defining Complexity Classes of Functions. STACS 1998: 607-617.[BIB]
The Chain Method to Separate Counting Classes. Theory Comput. Syst. 31(1): 93-108 (1998).[BIB]
Lindström Quantifiers and Leaf Language Definability. Int. J. Found. Comput. Sci. 9(3): 277-294 (1998).
1997
[BIB]
Gap-Languages and Log-Time Complexity Classes. Theor. Comput. Sci. 188(1-2): 101-116 (1997).[BIB]
On Operators of Higher Types. Computational Complexity Conference 1997: 174-184.[BIB]
A Generalized Quantifier Concept in Computational Complexity Theory. ESSLLI 1997: 99-123.[BIB]
Measure One Results in Computational Complexity Theory. Advances in Algorithms, Languages, and Complexity 1997: 285-312.
1996
[BIB]
Lindstroem Quantifiers and Leaf Language Definability. Electron. Colloquium Comput. Complex. 3(5) (1996).[BIB]
Probabilistic Type-2 Operators and "Almost"-Classes. Electron. Colloquium Comput. Complex. 3(35) (1996).[BIB]
Recursion Theoretic Characterizations of Complexity Classes of Counting Functions. Theor. Comput. Sci. 163(1&2): 245-258 (1996).[BIB]
On Balanced Versus Unbalanced Computation Trees. Math. Syst. Theory 29(4): 411-421 (1996).[BIB]
Nondeterministic NC1 Computation. Computational Complexity Conference 1996: 12-21.[BIB]
Complements of Multivalued Functions. Computational Complexity Conference 1996: 260-269.[BIB]
Relations Among Parallel and Sequential Computation Models. ASIAN 1996: 23-32.[BIB]
On Type-2 Probabilistic Quantifiers. ICALP 1996: 369-380.
1995
[BIB]
Complexity Classes of Optimization Functions. Inf. Comput. 120(2): 198-219 (1995).[BIB]
On the Power of Number-Theoretic Operations with Respect to Counting. Computational Complexity Conference 1995: 299-314.[BIB]
The satanic notations: counting classes beyond #P and other definitional adventures. SIGACT News 26(1): 2-13 (1995).
1994
[BIB]
Komplexitätsklassen von Funktionen. Julius Maximilians University Würzburg, Germany 1994.[BIB]
On Different Reducibility Notions for Function Classes. STACS 1994: 449-460.
1993
[BIB]
On the Power of Polynomial Time Bit-Reductions (Extended Abstract). Computational Complexity Conference 1993: 200-207.[BIB]
The Complexity of Finding Middle Elements. Int. J. Found. Comput. Sci. 4(4): 293-307 (1993).
1992
[BIB]
On the Power of Polynomial Bit-Reductions. Universität Trier, Mathematik/Informatik, Forschungsbericht 92-28 (1992).
1990
[BIB]
The Gap-Language-Technique Revisited. CSL 1990: 389-399.
Impressum | Datenschutz | Haftungsausschluss