Andreas Krebs

According to our database, Andreas Krebs authored at least 71 papers between 2003 and 2024.

Collaborative distances:

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

2024

A Formal Framework for Understanding Length Generalization in Transformers.

Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Sarrof, Andreas Krebs, Hattie Zhou, Preetum Nakkiran, Michael Hahn

CoRR, 2024

Synchronous Team Semantics for Temporal Logics.

Andreas Krebs, Arne Meier, Jonni Virtema, Martin Zimmermann

CoRR, 2024

2022

Regular languages defined by first-order formulas without quantifier alternation.

Andreas Krebs, Howard Straubing

CoRR, 2022

2020

Skew circuits of small width.

Nikhil Balaji, Andreas Krebs, Nutan Limaye

Theor. Comput. Sci., 2020

Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership.

Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing

Log. Methods Comput. Sci., 2020

Diminishable parameterized problems and strict polynomial kernelization.

Henning Fernau, Till Fluschnik, Danny Hermelin, Andreas Krebs, Hendrik Molter, Rolf Niedermeier

Comput., 2020

2019

Better Complexity Bounds for Cost Register Automata.

Eric Allender, Andreas Krebs, Pierre McKenzie

Theory Comput. Syst., 2019

A topological approach to non-uniform complexity.

Silke Czarnetzki, Andreas Krebs

Inf. Comput., 2019

The model checking fingerprints of CTL operators.

Andreas Krebs, Arne Meier, Martin Mundhenk

Acta Informatica, 2019

2018

Difference hierarchies and duality with an application to formal languages.

Célia Borlido, Mai Gehrke, Andreas Krebs, Howard Straubing

CoRR, 2018

Visibly Pushdown Languages and Free Profinite Algebras.

Silke Czarnetzki, Andreas Krebs, Klaus-Jörn Lange

CoRR, 2018

Team Semantics for the Specification and Verification of Hyperproperties.

Andreas Krebs, Arne Meier, Jonni Virtema, Martin Zimmermann

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Wreath Products of Distributive Forest Algebras.

Michael Hahn, Andreas Krebs, Howard Straubing

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

Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy.

Demen Güler, Andreas Krebs, Klaus-Jörn Lange, Petra Wolf

Proceedings of the Language and Automata Theory and Applications, 2018

An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation.

Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing

Proceedings of the 27th EACSL Annual Conference on Computer Science Logic, 2018

2017

An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic.

Andreas Krebs, Howard Straubing

ACM Trans. Comput. Log., 2017

Stone duality for languages and complexity.

Mai Gehrke, Andreas Krebs

ACM SIGLOG News, 2017

A Unified Method for Placing Problems in Polylogarithmic Depth.

Andreas Krebs, Nutan Limaye, Michael Ludwig

Electron. Colloquium Comput. Complex., 2017

Better Complexity Bounds for Cost Register Machines.

Eric Allender, Andreas Krebs, Pierre McKenzie

Electron. Colloquium Comput. Complex., 2017

Problems on Finite Automata and the Exponential Time Hypothesis.

Henning Fernau, Andreas Krebs

Algorithms, 2017

On the Complexity of Bounded Context Switching.

Peter Chini, Jonathan Kolberg, Andreas Krebs, Roland Meyer, Prakash Saivasan

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Stone Duality and the Substitution Principle.

Célia Borlido, Silke Czarnetzki, Mai Gehrke, Andreas Krebs

Proceedings of the 26th EACSL Annual Conference on Computer Science Logic, 2017

2016

Ultrafilters on words for a fragment of logic.

Mai Gehrke, Andreas Krebs, Jean-Éric Pin

Theor. Comput. Sci., 2016

Positive and negative proofs for circuits and branching programs.

Olga Dorzweiler, Thomas Flamm, Andreas Krebs, Michael Ludwig

Theor. Comput. Sci., 2016

Relating two width measures for resolution proofs.

Andreas Krebs, Meena Mahajan, Anil Shukla

Electron. Colloquium Comput. Complex., 2016

Two-variable Logic with a Between Predicate.

Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing

CoRR, 2016

The complexity of intersecting finite automata having few final states.

Michael Blondin, Andreas Krebs, Pierre McKenzie

Comput. Complex., 2016

Two-variable Logic with a Between Relation.

Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

Using Duality in Circuit Complexity.

Silke Czarnetzki, Andreas Krebs

Proceedings of the Language and Automata Theory and Applications, 2016

A Language-Theoretical Approach to Descriptive Complexity.

Michaël Cadilhac, Andreas Krebs, Klaus-Jörn Lange

Proceedings of the Developments in Language Theory - 20th International Conference, 2016

Cost Register Automata for Nested Words.

Andreas Krebs, Nutan Limaye, Michael Ludwig

Proceedings of the Computing and Combinatorics - 22nd International Conference, 2016

2015

Bounds for the Quantifier Depth in Finite-Variable Logics: Alternation Hierarchy.

Christoph Berkholz, Andreas Krebs, Oleg Verbitsky

ACM Trans. Comput. Log., 2015

Parallel Computational Tree Logic.

Andreas Krebs, Arne Meier, Jonni Virtema

CoRR, 2015

Value Automata with Filters.

Michaël Cadilhac, Andreas Krebs, Nutan Limaye

CoRR, 2015

A Team Based Variant of CTL.

Andreas Krebs, Arne Meier, Jonni Virtema

Proceedings of the 22nd International Symposium on Temporal Representation and Reasoning, 2015

Visibly Counter Languages and the Structure of NC¹.

Michael Hahn, Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

A Circuit Complexity Approach to Transductions.

Michaël Cadilhac, Andreas Krebs, Michael Ludwig, Charles Paperman

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth.

Andreas Krebs, Oleg Verbitsky

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

On Distinguishing NC¹ and NL.

Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig

Proceedings of the Developments in Language Theory - 19th International Conference, 2015

EF+EX Forest Algebras.

Andreas Krebs, Howard Straubing

Proceedings of the Algebraic Informatics - 6th International Conference, 2015

2014

Visibly Counter Languages and Constant Depth Circuits.

Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig

Electron. Colloquium Comput. Complex., 2014

Naive configurations.

Christoph Hering, Andreas Krebs, Thomas Edgar

Des. Codes Cryptogr., 2014

Quasi-optimal degree distribution for a quadratic programming problem arising from the p-version finite element method for a one-dimensional obstacle problem.

Matthias Maischak, Andreas Krebs, Ernst P. Stephan

Discret. Appl. Math., 2014

Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth.

Andreas Krebs, Oleg Verbitsky

CoRR, 2014

Extremely uniform branching programs.

Michaël Cadilhac, Andreas Krebs, Pierre McKenzie

Proceedings of the Sixth Workshop on Non-Classical Models for Automata and Applications, 2014

From Ultrafilters on Words to the Expressive Power of a Fragment of Logic.

Mai Gehrke, Andreas Krebs, Jean-Éric Pin

Proceedings of the Descriptional Complexity of Formal Systems, 2014

2013

Linear circuits, two-variable logic and weakly blocked monoids.

Christoph Behle, Andreas Krebs, Mark Mercer

Theor. Comput. Sci., 2013

Small Depth Proof Systems.

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

Electron. Colloquium Comput. Complex., 2013

The Algebraic Theory of Parikh Automata.

Michaël Cadilhac, Andreas Krebs, Pierre McKenzie

Electron. Colloquium Comput. Complex., 2013

2012

DLOGTIME-Proof Systems.

Andreas Krebs, Nutan Limaye

Electron. Colloquium Comput. Complex., 2012

Verifying Proofs in Constant Depth.

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer

Electron. Colloquium Comput. Complex., 2012

Counting Paths in VPA Is Complete for #NC 1.

Andreas Krebs, Nutan Limaye, Meena Mahajan

Algorithmica, 2012

The Lower Reaches of Circuit Uniformity.

Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Non-definability of Languages by Generalized First-order Formulas over (N, +).

Andreas Krebs, A. V. Sreejith

Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

Dense Completeness.

Andreas Krebs, Klaus-Jörn Lange

Proceedings of the Developments in Language Theory - 16th International Conference, 2012

2011

Typed Monoids - An Eilenberg-like Theorem for non regular Languages.

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Electron. Colloquium Comput. Complex., 2011

Low uniform versions of NC1.

Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie

Electron. Colloquium Comput. Complex., 2011

Regular Languages in MAJ[>] with three variables.

Christoph Behle, Andreas Krebs

Electron. Colloquium Comput. Complex., 2011

Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions.

Andreas Krebs, Nutan Limaye, Srikanth Srinivasan

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Optimization of Quadrature Filters Based on the Numerical Integration of Improper Integrals.

Andreas Krebs, Johan Wiklund, Michael Felsberg

Proceedings of the Pattern Recognition - 33rd DAGM Symposium, Frankfurt/Main, Germany, August 31, 2011

2010

A quadratic programming problem arising from the p-version for obstacle problems.

Matthias Maischak, Andreas Krebs, Ernst P. Stephan

Electron. Notes Discret. Math., 2010

Counting paths in VPA is complete for #NC¹.

Andreas Krebs, Nutan Limaye, Meena Mahajan

Electron. Colloquium Comput. Complex., 2010

2009

An Approach to characterize the Regular Languages in TC0 with Linear Wires.

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Electron. Colloquium Comput. Complex., 2009

Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG].

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Proceedings of the Language and Automata Theory and Applications, 2009

Regular Languages Definable by Majority Quantifiers with Two Variables.

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Proceedings of the Developments in Language Theory, 13th International Conference, 2009

2008

Typed semigroups, majority logic, and threshold circuits.

Andreas Krebs

PhD thesis, 2008

2007

A <i>p</i>-version finite element method for nonlinear elliptic variational inequalities in 2D.

Andreas Krebs, Ernst P. Stephan

Numerische Mathematik, 2007

Characterizing TC⁰ in Terms of Infinite Groups.

Andreas Krebs, Klaus-Jörn Lange, Stephanie Reifferscheid

Theory Comput. Syst., 2007

A partial plane of order 6 constructed from the icosahedron.

Christoph Hering, Andreas Krebs

Des. Codes Cryptogr., 2007

2006

Languages with Bounded Multiparty Communication Complexity.

Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

Electron. Colloquium Comput. Complex., 2006

2003

Optimized Temporal Logic Compilation.

Andreas Krebs, Jürgen Ruf

J. Univers. Comput. Sci., 2003