Pierre McKenzie

According to our database, Pierre McKenzie authored at least 78 papers between 1983 and 2023.

Collaborative distances:

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

2023

Perspective on complexity measures targetting read-once branching programs.

Yaqiao Li, Pierre McKenzie

CoRR, 2023

Pebbles and Branching Programs for Tree Evaluation.

Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam

Proceedings of the Logic, 2023

Towards a Complexity Theory of Parallel Computation.

Paul Beame, Pierre McKenzie

Proceedings of the Logic, 2023

2022

Tameness and the power of programs over monoids in DA.

Nathan Grosshans, Pierre McKenzie, Luc Segoufin

Log. Methods Comput. Sci., 2022

2021

The Reachability Problem for Two-Dimensional Vector Addition Systems with States.

Michael Blondin, Matthias Englert, Alain Finkel, Stefan Göller, Christoph Haase, Ranko Lazic, Pierre McKenzie, Patrick Totzke

J. ACM, 2021

2019

Better Complexity Bounds for Cost Register Automata.

Eric Allender, Andreas Krebs, Pierre McKenzie

Theory Comput. Syst., 2019

2018

Handling infinitely branching well-structured transition systems.

Michael Blondin, Alain Finkel, Pierre McKenzie

Inf. Comput., 2018

2017

Well Behaved Transition Systems.

Michael Blondin, Alain Finkel, Pierre McKenzie

Log. Methods Comput. Sci., 2017

Does Looking Inside a Circuit Help?

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

Electron. Colloquium Comput. Complex., 2017

Better Complexity Bounds for Cost Register Machines.

Eric Allender, Andreas Krebs, Pierre McKenzie

Electron. Colloquium Comput. Complex., 2017

The Power of Programs over Monoids in DA.

Nathan Grosshans, Pierre McKenzie, Luc Segoufin

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.

Paul Beame, Nathan Grosshans, Pierre McKenzie, Luc Segoufin

ACM Trans. Comput. Theory, 2016

The complexity of intersecting finite automata having few final states.

Michael Blondin, Andreas Krebs, Pierre McKenzie

Comput. Complex., 2016

2015

Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete.

Michael Blondin, Alain Finkel, Stefan Göller, Christoph Haase, Pierre McKenzie

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

2014

On Generalized Addition Chains.

Yara Elias, Pierre McKenzie

Integers, 2014

Reachability Problems for Infinite-State Systems (Dagstuhl Seminar 14141).

Javier Esparza, Alain Finkel, Pierre McKenzie, Joël Ouaknine

Dagstuhl Reports, 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

Handling Infinitely Branching WSTS.

Michael Blondin, Alain Finkel, Pierre McKenzie

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Unambiguous constrained Automata.

Michaël Cadilhac, Alain Finkel, Pierre McKenzie

Int. J. Found. Comput. Sci., 2013

The Algebraic Theory of Parikh Automata.

Michaël Cadilhac, Andreas Krebs, Pierre McKenzie

Electron. Colloquium Comput. Complex., 2013

Few Product Gates but Many Zeroes.

Bernd Borchert, Pierre McKenzie, Klaus Reinhardt

Chic. J. Theor. Comput. Sci., 2013

Can Chimps Go It Alone?

Pierre McKenzie

Proceedings of the Descriptional Complexity of Formal Systems, 2013

2012

Pebbles and Branching Programs for Tree Evaluation.

Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam

ACM Trans. Comput. Theory, 2012

Affine Parikh automata.

Michaël Cadilhac, Alain Finkel, Pierre McKenzie

RAIRO Theor. Informatics Appl., 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

The Complexity of Intersecting Finite Automata Having Few Final States.

Michael Blondin, Pierre McKenzie

Proceedings of the Computer Science - Theory and Applications, 2012

2011

Low uniform versions of NC1.

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

Electron. Colloquium Comput. Complex., 2011

Bounded Parikh Automata

Michaël Cadilhac, Alain Finkel, Pierre McKenzie

Proceedings of the Proceedings 8th International Conference Words 2011, 2011

Storming the Parikh Automaton

Michaël Cadilhac, Alain Finkel, Pierre McKenzie

CoRR, 2011

On the Expressiveness of Parikh Automata and Related Models.

Michaël Cadilhac, Alain Finkel, Pierre McKenzie

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.

Pierre McKenzie, Michael Thomas, Heribert Vollmer

SIAM J. Comput., 2010

The Computational Complexity of RaceTrack.

Markus Holzer, Pierre McKenzie

Proceedings of the Fun with Algorithms, 5th International Conference, 2010

2009

The complexity of Solitaire.

Luc Longpré, Pierre McKenzie

Theor. Comput. Sci., 2009

Branching Programs for Tree Evaluation.

Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Few Product Gates But Many Zeros.

Bernd Borchert, Pierre McKenzie, Klaus Reinhardt

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Fractional Pebbling and Thrifty Branching Programs.

Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

2008

Worst Case Nonzero-Error Interactive Communication.

Hugues Mercier, Pierre McKenzie, Stefan Wolf

IEEE Trans. Inf. Theory, 2008

2007

The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers.

Pierre McKenzie, Klaus W. Wagner

Comput. Complex., 2007

2006

The many faces of a translation.

Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer

J. Comput. Syst. Sci., 2006

Corrigendum to "Completeness results for graph isomorphism" [J. Comput. System Sci. 66(2003) 549-566].

Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán

J. Comput. Syst. Sci., 2006

2005

Incremental branching programs

Anna Gál, Michal Koucký, Pierre McKenzie

Electron. Colloquium Comput. Complex., 2005

Worst-case randomized interactive communication.

Hugues Mercier, Pierre McKenzie, Stefan Wolf

Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005

2004

Arithmetic Circuits and Polynomial Replacement Systems.

Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner

SIAM J. Comput., 2004

A well-structured framework for analysing petri net extensions.

Alain Finkel, Pierre McKenzie, Claudine Picaronny

Inf. Comput., 2004

2003

Alternating and empty alternating auxiliary stack automata.

Markus Holzer, Pierre McKenzie

Theor. Comput. Sci., 2003

Completeness results for graph isomorphism.

Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán

J. Comput. Syst. Sci., 2003

2002

The complexity of tensor calculus.

Carsten Damm, Markus Holzer, Pierre McKenzie

Comput. Complex., 2002

2001

The Descriptive Complexity Approach to LOGCFL.

Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer

J. Comput. Syst. Sci., 2001

On the Complexity of Some Problems on Groups Input as Multiplication Tables.

David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie

J. Comput. Syst. Sci., 2001

Systems and Software Verification, Model-Checking Techniques and Tools.

Béatrice Bérard, Michel Bidoit, Alain Finkel, François Laroussinie, Antoine Petit, Laure Petrucci, Philippe Schnoebelen, Pierre McKenzie

Springer, ISBN: 9783540415237, 2001

2000

Reversible Space Equals Deterministic Space.

Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp

J. Comput. Syst. Sci., 2000

Equation Satisfiability and Program Satisfiability for Finite Monoids.

David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

1999

Separation of the Monotone NC Hierarchy.

Ran Raz, Pierre McKenzie

Comb., 1999

Modular Temporal Logic.

Augustin Baziramwabo, Pierre McKenzie, Denis Thérien

Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999

Circuits and Context-Free Languages.

Pierre McKenzie, Klaus Reinhardt, V. Vinay

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998

Nondeterministic <i>NC</i>¹ Computation.

Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer

J. Comput. Syst. Sci., 1998

On the Complexity of Free Monoid Morphisms.

Klaus-Jörn Lange, Pierre McKenzie

Proceedings of the Algorithms and Computation, 9th International Symposium, 1998

A Note on the Hardness of Tree Isomorphism.

Birgit Jenner, Pierre McKenzie, Jacobo Torán

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

Verifying Identical Communicating Processes is Undecidable.

Alain Finkel, Pierre McKenzie

Theor. Comput. Sci., 1997

Finite Moniods: From Word to Circuit Evaluation.

Martin Beaudry, Pierre McKenzie, Pierre Péladeau, Denis Thérien

SIAM J. Comput., 1997

1996

Logspace and Logtime Leaf Languages.

Birgit Jenner, Pierre McKenzie, Denis Thérien

Inf. Comput., 1996

Nondeterministic NC¹ Computation.

Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer

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

1995

Circuits, Matrices, and Nonassociative Computation.

Martin Beaudry, Pierre McKenzie

J. Comput. Syst. Sci., 1995

1994

Special Issue on Circuit Complexity: Foreword.

Pierre McKenzie, Denis Thérien

Comput. Complex., 1994

1993

Extensions to Barrington's M-Program Model.

François Bédard, François Lemieux, Pierre McKenzie

Theor. Comput. Sci., 1993

1992

The Membership Problem in Aperiodic Transformation Monoids.

Martin Beaudry, Pierre McKenzie, Denis Thérien

J. ACM, 1992

Cicuits, Matrices, and Nonassociative Computation.

Martin Beaudry, Pierre McKenzie

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

Oracle branching programs and Logspace versus P

David A. Mix Barrington, Pierre McKenzie

Inf. Comput., November, 1991

NC¹: The Automata-Theoretic Viewpoint.

Pierre McKenzie, Pierre Péladeau, Denis Thérien

Comput. Complex., 1991

1989

Testing Membership: Beyond Permutation Groups (Extended Abstract).

Martin Beaudry, Pierre McKenzie, Denis Thérien

Proceedings of the STACS 89, 1989

Automata Theory Meets Circuit Complexity.

Pierre McKenzie, Denis Thérien

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

1988

Parallel Algorithms for Solvable Permutation Groups.

Eugene M. Luks, Pierre McKenzie

J. Comput. Syst. Sci., 1988

1987

The Parallel Complexity of Abelian Permutation Group Problems.

Pierre McKenzie, Stephen A. Cook

SIAM J. Comput., 1987

Problems Complete for Deterministic Logarithmic Space.

Stephen A. Cook, Pierre McKenzie

J. Algorithms, 1987

1985

Fast Parallel Computation with Permutation Groups

Eugene M. Luks, Pierre McKenzie

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

Parallel complexity and permutation groups.

Pierre McKenzie

PhD thesis, 1984

Permutations of Bounded Degree Generate Groups of Polynomial Diameter.

Pierre McKenzie

Inf. Process. Lett., 1984

1983

The Parallel Complexity of the Abelian Permutation Group Membership Problem

Pierre McKenzie, Stephen A. Cook

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983