2024
Perspective on complexity measures targeting read-once branching programs.
Inf. Comput., 2024
2023
Catalytic Branching Programs from Groups and General Protocols.
ACM Trans. Comput. Theory, 2023
Perspective on complexity measures targetting read-once branching programs.
CoRR, 2023
Pebbles and Branching Programs for Tree Evaluation.
Proceedings of the Logic, 2023
Towards a Complexity Theory of Parallel Computation.
Proceedings of the Logic, 2023
2022
Tameness and the power of programs over monoids in DA.
Log. Methods Comput. Sci., 2022
2021
The Reachability Problem for Two-Dimensional Vector Addition Systems with States.
J. ACM, 2021
2019
Better Complexity Bounds for Cost Register Automata.
Theory Comput. Syst., 2019
2018
Handling infinitely branching well-structured transition systems.
Inf. Comput., 2018
2017
Well Behaved Transition Systems.
Log. Methods Comput. Sci., 2017
Does Looking Inside a Circuit Help?
Electron. Colloquium Comput. Complex., 2017
Better Complexity Bounds for Cost Register Machines.
Electron. Colloquium Comput. Complex., 2017
The Power of Programs over Monoids in DA.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017
2016
Nondeterminism and An Abstract Formulation of Nečiporuk's Lower Bound Method.
ACM Trans. Comput. Theory, 2016
The complexity of intersecting finite automata having few final states.
Comput. Complex., 2016
2015
Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete.
Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015
2014
On Generalized Addition Chains.
Integers, 2014
Reachability Problems for Infinite-State Systems (Dagstuhl Seminar 14141).
Dagstuhl Reports, 2014
Extremely uniform branching programs.
Proceedings of the Sixth Workshop on Non-Classical Models for Automata and Applications, 2014
Handling Infinitely Branching WSTS.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014
2013
Unambiguous constrained Automata.
Int. J. Found. Comput. Sci., 2013
The Algebraic Theory of Parikh Automata.
Electron. Colloquium Comput. Complex., 2013
Few Product Gates but Many Zeroes.
Chic. J. Theor. Comput. Sci., 2013
Proceedings of the Descriptional Complexity of Formal Systems, 2013
2012
Pebbles and Branching Programs for Tree Evaluation.
ACM Trans. Comput. Theory, 2012
RAIRO Theor. Informatics Appl., 2012
Int. J. Found. Comput. Sci., 2012
The Lower Reaches of Circuit Uniformity.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012
The Complexity of Intersecting Finite Automata Having Few Final States.
Proceedings of the Computer Science - Theory and Applications, 2012
2011
Low uniform versions of NC1.
Electron. Colloquium Comput. Complex., 2011
Storming the Parikh Automaton
CoRR, 2011
On the Expressiveness of Parikh Automata and Related Models.
Proceedings of the Third Workshop on Non-Classical Models for Automata and Applications - NCMA 2011, Milan, Italy, July 18, 2011
2010
Extensional Uniformity for Boolean Circuits.
SIAM J. Comput., 2010
The Computational Complexity of RaceTrack.
Proceedings of the Fun with Algorithms, 5th International Conference, 2010
2009
The complexity of Solitaire.
Theor. Comput. Sci., 2009
Branching Programs for Tree Evaluation.
Proceedings of the Mathematical Foundations of Computer Science 2009, 2009
Few Product Gates But Many Zeros.
Proceedings of the Mathematical Foundations of Computer Science 2009, 2009
Fractional Pebbling and Thrifty Branching Programs.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009
2008
Worst Case Nonzero-Error Interactive Communication.
IEEE Trans. Inf. Theory, 2008
2007
The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers.
Comput. Complex., 2007
2006
The many faces of a translation.
J. Comput. Syst. Sci., 2006
Corrigendum to "Completeness results for graph isomorphism" [J. Comput. System Sci. 66(2003) 549-566].
J. Comput. Syst. Sci., 2006
2005
Incremental branching programs
Electron. Colloquium Comput. Complex., 2005
Worst-case randomized interactive communication.
Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005
2004
Arithmetic Circuits and Polynomial Replacement Systems.
SIAM J. Comput., 2004
A well-structured framework for analysing petri net extensions.
Inf. Comput., 2004
2003
Alternating and empty alternating auxiliary stack automata.
Theor. Comput. Sci., 2003
Completeness results for graph isomorphism.
J. Comput. Syst. Sci., 2003
2002
The complexity of tensor calculus.
Comput. Complex., 2002
2001
The Descriptive Complexity Approach to LOGCFL.
J. Comput. Syst. Sci., 2001
On the Complexity of Some Problems on Groups Input as Multiplication Tables.
J. Comput. Syst. Sci., 2001
Systems and Software Verification, Model-Checking Techniques and Tools.
Springer, ISBN: 9783540415237, 2001
2000
Reversible Space Equals Deterministic Space.
J. Comput. Syst. Sci., 2000
Equation Satisfiability and Program Satisfiability for Finite Monoids.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000
1999
Separation of the Monotone NC Hierarchy.
Comb., 1999
Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999
Circuits and Context-Free Languages.
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999
1998
Nondeterministic <i>NC</i><sup>1</sup> Computation.
J. Comput. Syst. Sci., 1998
On the Complexity of Free Monoid Morphisms.
Proceedings of the Algorithms and Computation, 9th International Symposium, 1998
A Note on the Hardness of Tree Isomorphism.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998
1997
Verifying Identical Communicating Processes is Undecidable.
Theor. Comput. Sci., 1997
Finite Moniods: From Word to Circuit Evaluation.
SIAM J. Comput., 1997
1996
Logspace and Logtime Leaf Languages.
Inf. Comput., 1996
Nondeterministic NC<sup>1</sup> Computation.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996
1995
Circuits, Matrices, and Nonassociative Computation.
J. Comput. Syst. Sci., 1995
1994
Special Issue on Circuit Complexity: Foreword.
Comput. Complex., 1994
1993
Extensions to Barrington's M-Program Model.
Theor. Comput. Sci., 1993
1992
The Membership Problem in Aperiodic Transformation Monoids.
J. ACM, 1992
Cicuits, Matrices, and Nonassociative Computation.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992
1991
Oracle branching programs and Logspace versus P
Inf. Comput., November, 1991
NC¹: The Automata-Theoretic Viewpoint.
Comput. Complex., 1991
1989
Testing Membership: Beyond Permutation Groups (Extended Abstract).
Proceedings of the STACS 89, 1989
Automata Theory Meets Circuit Complexity.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989
1988
Parallel Algorithms for Solvable Permutation Groups.
J. Comput. Syst. Sci., 1988
1987
The Parallel Complexity of Abelian Permutation Group Problems.
SIAM J. Comput., 1987
Problems Complete for Deterministic Logarithmic Space.
J. Algorithms, 1987
1985
Fast Parallel Computation with Permutation Groups
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
1984
Parallel complexity and permutation groups.
PhD thesis, 1984
Permutations of Bounded Degree Generate Groups of Polynomial Diameter.
Inf. Process. Lett., 1984
1983
The Parallel Complexity of the Abelian Permutation Group Membership Problem
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983