Heribert Vollmer

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

2021

Descriptive complexity of #P functions: A new perspective.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2021

A Logical Characterization of Constant-Depth Circuits over the Reals.

[BibT_eX]

[DOI]

Timon Barlag

Proceedings of the Logic, Language, Information, and Computation, 2021

2020

Satisfiability of Modal Inclusion Logic: Lax and Strict Semantics.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2020

2019

Guest Editorial: Special Issue on Theoretical Aspects of Computer Science.

[BibT_eX]

[DOI]

Brigitte Vallée

Theory Comput. Syst., 2019

A complexity theory for hard enumeration problems.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2019

Logics for Dependence and Independence (Dagstuhl Seminar 19031).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2019

A model-theoretic characterization of constant-depth arithmetic circuits.

[BibT_eX]

[DOI]

Anselm Haak

Ann. Pure Appl. Log., 2019

Parameterised Enumeration for Modification Problems.

[BibT_eX]

[DOI]

Raïda Ktari

Frédéric Olive

Algorithms, 2019

Counting of Teams in First-Order Team Logics.

[BibT_eX]

[DOI]

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018

Complexity of Propositional Logics in Team Semantic.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2018

Preface of STACS 2016 Special Issue.

[BibT_eX]

[DOI]

Christoph Dürr

Theory Comput. Syst., 2018

Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth.

[BibT_eX]

[DOI]

Anselm Haak

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

2017

Paradigms for Parameterized Enumeration.

[BibT_eX]

[DOI]

Johannes Schmidt

Theory Comput. Syst., 2017

Modal independence logic.

[BibT_eX]

[DOI]

Henning Schnoor

J. Log. Comput., 2017

Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth.

[BibT_eX]

[DOI]

Anselm Haak

CoRR, 2017

On the Complexity of Hard Enumeration Problems.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2017

2016

SAT and Interactions (Dagstuhl Seminar 16381).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2016

Descriptive Complexity of #AC0 Functions.

[BibT_eX]

[DOI]

Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

Introduction.

[BibT_eX]

[DOI]

Proceedings of the Dependence Logic, Theory and Applications, 2016

Expressivity and Complexity of Dependence Logic.

[BibT_eX]

[DOI]

Proceedings of the Dependence Logic, Theory and Applications, 2016

2015

Dependence Logic with a Majority Quantifier.

[BibT_eX]

[DOI]

J. Log. Lang. Inf., 2015

Erratum: The Complexity of Satisfiability for Fragments of CTL and CTL⋆.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2015

Parameterized Complexity of Weighted Satisfiability Problems: Decision, Enumeration, Counting.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2015

Logics for Dependence and Independence (Dagstuhl Seminar 15261).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2015

Circuits, Logic and Games (Dagstuhl Seminar 15401).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2015

On the parameterized complexity of non-monotonic logics.

[BibT_eX]

[DOI]

Arch. Math. Log., 2015

Modal Inclusion Logic: Being Lax is Simpler than Being Strict.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Complexity of Propositional Independence and Inclusion Logic.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Parameterized Enumeration for Modification Problems.

[BibT_eX]

[DOI]

Raïda Ktari

Frédéric Olive

Proceedings of the Language and Automata Theory and Applications, 2015

A Van Benthem Theorem for Modal Team Semantics.

[BibT_eX]

[DOI]

Henning Schnoor

Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015

Komplexität von Algorithmen.

[BibT_eX]

[DOI]

Mathematik für Anwendungen 4, Lehmanns Media, ISBN: 978-3-86541-761-9, 2015

2014

LoCo - A Logic for Configuration Problems.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2014

A Fragment of Dependence Logic Capturing Polynomial Time

[BibT_eX]

[DOI]

Johannes Ebbing

Log. Methods Comput. Sci., 2014

2013

Complexity Results for Modal Dependence Logic.

[BibT_eX]

[DOI]

Peter Lohmann

Stud Logica, 2013

Dependence Logic: Theory and Applications (Dagstuhl Seminar 13071).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2013

Parameterized Enumeration with Ordering.

[BibT_eX]

[DOI]

Raïda Ktari

Frédéric Olive

CoRR, 2013

Model Checking for Modal Dependence Logic: An Approach through Post's Lattice.

[BibT_eX]

[DOI]

Proceedings of the Logic, Language, Information, and Computation, 2013

Extended Modal Dependence Logic.

[BibT_eX]

[DOI]

Johannes Ebbing

Lauri Hella

Jonni Virtema

Proceedings of the Logic, Language, Information, and Computation, 2013

2012

The Complexity of Reasoning for Fragments of Autoepistemic Logic.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2012

Counting classes and the fine structure between NC1 and L.

[BibT_eX]

[DOI]

Samir Datta

Meena Mahajan

B. V. Raghavendra Rao

Gido Scharfenberger-Fabian

Theor. Comput. Sci., 2012

The complexity of reasoning for fragments of default logic.

[BibT_eX]

[DOI]

J. Log. Comput., 2012

Verifying Proofs in Constant Depth.

[BibT_eX]

[DOI]

Karteek Sreenivasaiah

Electron. Colloquium Comput. Complex., 2012

Complexity of Model Checking for Logics over Kripke models.

[BibT_eX]

[DOI]

Martin Mundhenk

Bull. EATCS, 2012

SAT Interactions (Dagstuhl Seminar 12471).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2012

Parameterized Complexity of Weighted Satisfiability Problems.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2012, 2012

On the Parameterized Complexity of Default Logic and Autoepistemic Logic.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2012

LoCo - A Logic for Configuration Problems.

[BibT_eX]

[DOI]

Markus Aschinger

Conrad Drescher

Gido Scharfenberger-Fabian

Proceedings of the ECAI 2012, 2012

2011

Model Checking CTL is Almost Always Inherently Sequential

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2011

Proof complexity of propositional default logic.

[BibT_eX]

[DOI]

Arch. Math. Log., 2011

Verifying Proofs in Constant Depth.

[BibT_eX]

[DOI]

Olaf Beyersdorff

Samir Datta

Meena Mahajan

Karteek Sreenivasaiah

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

2010

Extensional Uniformity for Boolean Circuits.

[BibT_eX]

[DOI]

Pierre McKenzie

SIAM J. Comput., 2010

Complexity of non-monotonic logics.

[BibT_eX]

[DOI]

Bull. EATCS, 2010

On Second-Order Monadic Monoidal and Groupoidal Quantifiers

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2010

Boolean Circuits as a Data Structure for Boolean Functions: Efficient Algorithms and Hard Problems

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2010

10061 Executive Summary - Circuits, Logic, and Games.

[BibT_eX]

[DOI]

Proceedings of the Circuits, Logic, and Games, 07.02. - 12.02.2010, 2010

10061 Abstracts Collection - Circuits, Logic, and Games.

[BibT_eX]

[DOI]

Proceedings of the Circuits, Logic, and Games, 07.02. - 12.02.2010, 2010

2009

The complexity of satisfiability problems: Refining Schaefer's theorem.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2009

The complexity of propositional implication.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

The Complexity of Satisfiability for Fragments of CTL and CTL*.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2009

2008

The Complexity of Satisfiability for Fragments of CTL and CTL*.

[BibT_eX]

[DOI]

Proceedings of the Second Workshop on Reachability Problems in Computational Models, 2008

On Second-Order Monadic Groupoidal Quantifiers.

[BibT_eX]

[DOI]

Proceedings of the Logic, 2008

Boolean Constraint Satisfaction Problems: When Does Post's Lattice Help?.

[BibT_eX]

[DOI]

Proceedings of the Complexity of Constraints, 2008

2007

The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments.

[BibT_eX]

[DOI]

Proceedings of the 5th Workshop on Methods for Modalities, 2007

The Complexity of Problems for Quantified Constraints.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Computational Complexity of Constraint Satisfaction.

[BibT_eX]

[DOI]

Proceedings of the Computation and Logic in the Real World, 2007

2006

Exploiting practical limitations of UML diagrams for model validation and execution.

[BibT_eX]

[DOI]

Friedrich Steimann

Softw. Syst. Model., 2006

The many faces of a translation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

The Complexity of Generalized Satisfiability for Linear Temporal Logic.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

06451 Abstracts Collection -- Circuits, Logic, and Games .

[BibT_eX]

[DOI]

Thomas Schwentick

Denis Thérien

Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

06451 Executive Summary -- Circuits, Logic, and Games .

[BibT_eX]

[DOI]

Thomas Schwentick

Denis Thérien

Proceedings of the Circuits, Logic, and Games, 08.11. - 10.11.2006, 2006

06401 Abstracts Collection - Complexity of Constraints.

[BibT_eX]

[DOI]

Phokion G. Kolaitis

Proceedings of the Complexity of Constraints, 01.10. - 06.10.2006, 2006

06401 Executive Summary - Complexity of Constraints.

[BibT_eX]

[DOI]

Phokion G. Kolaitis

Proceedings of the Complexity of Constraints, 01.10. - 06.10.2006, 2006

2005

Bases for Boolean co-clones.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2005

Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

The complexity of base station positioning in cellular networks.

[BibT_eX]

[DOI]

Christian Glaßer

Discret. Appl. Math., 2005

2004

Arithmetic Circuits and Polynomial Replacement Systems.

[BibT_eX]

[DOI]

Pierre McKenzie

SIAM J. Comput., 2004

The Complexity of Boolean Constraint Isomorphism.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

An Algebraic Approach to the Complexity of Generalized Conjunctive Queries.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing, 2004

2003

Generic separations and leaf languages.

[BibT_eX]

[DOI]

Matthias Galota

Sven Kosub

Math. Log. Q., 2003

Optimal satisfiability for propositional calculi and constraint satisfaction problems.

[BibT_eX]

[DOI]

Inf. Comput., 2003

Functions Computable in Polynomial Space

[BibT_eX]

[DOI]

Matthias Galota

Electron. Colloquium Comput. Complex., 2003

Complexity Theory Made Easy.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 7th International Conference, 2003

2002

On the Autoreducibility of Random Sequences

[BibT_eX]

[DOI]

Todd Ebert

Wolfgang Merkle

Electron. Colloquium Comput. Complex., 2002

Equivalence and Isomorphism for Boolean Constraint Satisfaction.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 16th International Workshop, 2002

2001

The Descriptive Complexity Approach to LOGCFL.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

Finite Automata with Generalized Acceptance Criteria.

[BibT_eX]

[DOI]

Timo Peichl

Discret. Math. Theor. Comput. Sci., 2001

Partially-Ordered Two-Way Automata: A New Characterization of DA.

[BibT_eX]

[DOI]

Thomas Schwentick

Denis Thérien

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

A polynomial-time approximation scheme for base station positioning in UMTS networks.

[BibT_eX]

[DOI]

Proceedings of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M 2001), 2001

A Generalization of the Büchi-Elgot-Trakhtenbrot Theorem.

[BibT_eX]

[DOI]

Matthias Galota

Proceedings of the Computer Science Logic, 15th International Workshop, 2001

2000

A note on closure properties of logspace MOD classes.

[BibT_eX]

[DOI]

Ulrich Hertrampf

Inf. Process. Lett., 2000

Uniform Characterizations of Complexity Classes of Functions.

[BibT_eX]

[DOI]

Sven Kosub

Heinz Schmitz

Int. J. Found. Comput. Sci., 2000

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

[BibT_eX]

[DOI]

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

On the Autoreducibility of Random Sequences.

[BibT_eX]

[DOI]

Todd Ebert

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

1999

Uniform characterizations of complexity classes.

[BibT_eX]

[DOI]

SIGACT News, 1999

Was leistet die Komplexitätstheorie für die Praxis?

[BibT_eX]

[DOI]

Inform. Spektrum, 1999

Complements of Multivalued Functions.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 1999

Introduction to Circuit Complexity - A Uniform Approach.

[BibT_eX]

[DOI]

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-662-03927-4, 1999

1998

Relating Polynomial Time to Constant Depth.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

The Chain Method to Separate Counting Classes.

[BibT_eX]

[DOI]

Theory Comput. Syst., 1998

Nondeterministic NC1 Computation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1998

Lindström Quantifiers and Leaf Language Definability.

[BibT_eX]

[DOI]

Hans-Jörg Burtschick

Int. J. Found. Comput. Sci., 1998

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

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

[BibT_eX]

[DOI]

Ronald V. Book

Comput. Complex., 1998

Uniformly Defining Complexity Classes of Functions.

[BibT_eX]

[DOI]

Sven Kosub

Heinz Schmitz

Proceedings of the STACS 98, 1998

1997

Gap-Languages and Log-Time Complexity Classes.

[BibT_eX]

[DOI]

Kenneth W. Regan

Theor. Comput. Sci., 1997

A Generalized Quantifier Concept in Computational Complexity Theory.

[BibT_eX]

[DOI]

Proceedings of the Generalized Quantifiers and Computation, 1997

On Operators of Higher Types.

[BibT_eX]

[DOI]

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

Measure One Results in Computational Complexity Theory.

[BibT_eX]

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

1996

Recursion Theoretic Characterizations of Complexity Classes of Counting Functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

On Balanced Versus Unbalanced Computation Trees.

[BibT_eX]

[DOI]

Ulrich Hertrampf

Math. Syst. Theory, 1996

Lindstroem Quantifiers and Leaf Language Definability

[BibT_eX]

[DOI]

Hans-Jörg Burtschick

Electron. Colloquium Comput. Complex., 1996

On Type-2 Probabilistic Quantifiers.

[BibT_eX]

[DOI]

Ronald V. Book

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

Nondeterministic NC1 Computation.

[BibT_eX]

[DOI]

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

Relations Among Parallel and Sequential Computation Models.

[BibT_eX]

[DOI]

Proceedings of the Concurrency and Parallelism, 1996

1995

Complexity Classes of Optimization Functions

[BibT_eX]

[DOI]

Inf. Comput., August, 1995

The satanic notations: counting classes beyond #P and other definitional adventures.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

SIGACT News, 1995

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

[BibT_eX]

[DOI]

Ulrich Hertrampf

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

1994

Komplexitätsklassen von Funktionen.

[BibT_eX]

[DOI]

PhD thesis, 1994

On Different Reducibility Notions for Function Classes.

[BibT_eX]

[DOI]

Proceedings of the STACS 94, 1994

1993

The Complexity of Finding Middle Elements.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

1992

On the Power of Polynomial Bit-Reductions

[BibT_eX]

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

1990

The Gap-Language-Technique Revisited.

[BibT_eX]

[DOI]