Pierre McKenzie

Publication Activity (10 Years)

Years Active: 1983-2023
Publications (10 Years): 19

Top Venues

CoRR

MFCS

Electron. Colloquium Comput. Complex.

Theory Comput. Syst.

Publications

Yaqiao Li, Pierre McKenzie
Perspective on complexity measures targetting read-once branching programs. CoRR (2023)
Nathan Grosshans, Pierre McKenzie, Luc Segoufin
Tameness and the power of programs over monoids in DA. Log. Methods Comput. Sci. 18 (3) (2022)
Nathan Grosshans, Pierre McKenzie, Luc Segoufin
Tameness and the power of programs over monoids in DA. CoRR (2021)
Michael Blondin, Matthias Englert, Alain Finkel, Stefan Göller, Christoph Haase, Ranko Lazic, Pierre McKenzie, Patrick Totzke
The Reachability Problem for Two-Dimensional Vector Addition Systems with States. J. ACM 68 (5) (2021)
Eric Allender, Andreas Krebs, Pierre McKenzie
Better Complexity Bounds for Cost Register Automata. Theory Comput. Syst. 63 (3) (2019)
Michael Blondin, Alain Finkel, Pierre McKenzie
Handling infinitely branching well-structured transition systems. Inf. Comput. 258 (2018)
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
The Algebraic Theory of Parikh Automata. Theory Comput. Syst. 62 (5) (2018)
Michael Blondin, Alain Finkel, Pierre McKenzie
Well Behaved Transition Systems. Log. Methods Comput. Sci. 13 (3) (2017)
Eric Allender, Andreas Krebs, Pierre McKenzie
Better Complexity Bounds for Cost Register Automata. MFCS (2017)
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani
Does Looking Inside a Circuit Help?. MFCS (2017)
Eric Allender, Andreas Krebs, Pierre McKenzie
Better Complexity Bounds for Cost Register Machines. Electron. Colloquium Comput. Complex. 24 (2017)
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani
Does Looking Inside a Circuit Help? Electron. Colloquium Comput. Complex. 24 (2017)
Nathan Grosshans, Pierre McKenzie, Luc Segoufin
The Power of Programs over Monoids in DA. MFCS (2017)
Paul Beame, Nathan Grosshans, Pierre McKenzie, Luc Segoufin
Nondeterminism and an abstract formulation of Nečiporuk's lower bound method. CoRR (2016)
Michael Blondin, Andreas Krebs, Pierre McKenzie
The complexity of intersecting finite automata having few final states. Comput. Complex. 25 (4) (2016)
Michael Blondin, Alain Finkel, Pierre McKenzie
Well Behaved Transition Systems. CoRR (2016)
Yara Elias, Pierre McKenzie
On Generalized Addition Chains. CoRR (2016)
Paul Beame, Nathan Grosshans, Pierre McKenzie, Luc Segoufin
Nondeterminism and An Abstract Formulation of Nečiporuk's Lower Bound Method. ACM Trans. Comput. Theory 9 (1) (2016)
Michael Blondin, Alain Finkel, Stefan Göller, Christoph Haase, Pierre McKenzie
Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete. LICS (2015)
Michael Blondin, Alain Finkel, Pierre McKenzie
Handling Infinitely Branching WSTS. ICALP (2) (2014)
Javier Esparza, Alain Finkel, Pierre McKenzie, Joël Ouaknine
Reachability Problems for Infinite-State Systems (Dagstuhl Seminar 14141). Dagstuhl Reports 4 (3) (2014)
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
Extremely uniform branching programs. NCMA (2014)
Yara Elias, Pierre McKenzie
On Generalized Addition Chains. Integers 14 (2014)
Michael Blondin, Alain Finkel, Stefan Göller, Christoph Haase, Pierre McKenzie
Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete. CoRR (2014)
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
The Algebraic Theory of Parikh Automata. CAI (2013)
Pierre McKenzie
Can Chimps Go It Alone? DCFS (2013)
Michaël Cadilhac, Andreas Krebs, Pierre McKenzie
The Algebraic Theory of Parikh Automata. Electron. Colloquium Comput. Complex. 20 (2013)
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
Unambiguous constrained Automata. Int. J. Found. Comput. Sci. 24 (7) (2013)
Bernd Borchert, Pierre McKenzie, Klaus Reinhardt
Few Product Gates but Many Zeroes. Chic. J. Theor. Comput. Sci. 2013 (2013)
Michael Blondin, Andreas Krebs, Pierre McKenzie
The Complexity of Intersecting Finite Automata Having Few Final States. Electron. Colloquium Comput. Complex. 19 (2012)
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
Bounded Parikh Automata. Int. J. Found. Comput. Sci. 23 (8) (2012)
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
Unambiguous Constrained Automata. Developments in Language Theory (2012)
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
Affine Parikh automata. RAIRO Theor. Informatics Appl. 46 (4) (2012)
Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie
The Lower Reaches of Circuit Uniformity. MFCS (2012)
Michael Blondin, Pierre McKenzie
The Complexity of Intersecting Finite Automata Having Few Final States. CSR (2012)
Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
Pebbles and Branching Programs for Tree Evaluation. ACM Trans. Comput. Theory 3 (2) (2012)
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
Bounded Parikh Automata WORDS (2011)
Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie
Low uniform versions of NC1. Electron. Colloquium Comput. Complex. 18 (2011)
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
On the Expressiveness of Parikh Automata and Related Models. NCMA (2011)
Michaël Cadilhac, Alain Finkel, Pierre McKenzie
Storming the Parikh Automaton CoRR (2011)
Pierre McKenzie, Michael Thomas, Heribert Vollmer
Extensional Uniformity for Boolean Circuits. SIAM J. Comput. 39 (7) (2010)
Markus Holzer, Pierre McKenzie
The Computational Complexity of RaceTrack. FUN (2010)
Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
Pebbles and Branching Programs for Tree Evaluation CoRR (2010)
Luc Longpré, Pierre McKenzie
The complexity of Solitaire. Theor. Comput. Sci. 410 (50) (2009)
Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr
Branching Programs for Tree Evaluation. MFCS (2009)
Bernd Borchert, Pierre McKenzie, Klaus Reinhardt
Few Product Gates But Many Zeros. MFCS (2009)
Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr
Fractional Pebbling and Thrifty Branching Programs. FSTTCS (2009)
Pierre McKenzie, Michael Thomas, Heribert Vollmer
Extensional Uniformity for Boolean Circuits CoRR (2008)
Hugues Mercier, Pierre McKenzie, Stefan Wolf
Worst Case Nonzero-Error Interactive Communication. IEEE Trans. Inf. Theory 54 (7) (2008)
Pierre McKenzie, Michael Thomas, Heribert Vollmer
Extensional Uniformity for Boolean Circuits. CSL (2008)
Anna Gál, Michal Koucký, Pierre McKenzie
Incremental Branching Programs. Theory Comput. Syst. 43 (2) (2008)
Pierre McKenzie, Klaus W. Wagner
The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers. Comput. Complex. 16 (3) (2007)
Luc Longpré, Pierre McKenzie
The Complexity of Solitaire. MFCS (2007)
Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán
Corrigendum to "Completeness results for graph isomorphism" [J. Comput. System Sci. 66(2003) 549-566]. J. Comput. Syst. Sci. 72 (4) (2006)
Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer
The many faces of a translation. J. Comput. Syst. Sci. 72 (1) (2006)
Anna Gál, Pierre McKenzie, Michal Koucký
Incremental branching programs. Complexity of Boolean Functions (2006)
Anna Gál, Michal Koucký, Pierre McKenzie
Incremental Branching Programs. CSR (2006)
Hugues Mercier, Pierre McKenzie, Stefan Wolf
Worst-case randomized interactive communication. ISIT (2005)
Anna Gál, Michal Koucký, Pierre McKenzie
Incremental branching programs Electron. Colloquium Comput. Complex. (136) (2005)
Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner
Arithmetic Circuits and Polynomial Replacement Systems. SIAM J. Comput. 33 (6) (2004)
Alain Finkel, Pierre McKenzie, Claudine Picaronny
A well-structured framework for analysing petri net extensions. Inf. Comput. 195 (1-2) (2004)
Pierre McKenzie, Klaus W. Wagner
The Complexity of Membership Problems for Circuits over Sets of Natural Numbers. STACS (2003)
Markus Holzer, Pierre McKenzie
Alternating and empty alternating auxiliary stack automata. Theor. Comput. Sci. 299 (1-3) (2003)
Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán
Completeness results for graph isomorphism. J. Comput. Syst. Sci. 66 (3) (2003)
Carsten Damm, Markus Holzer, Pierre McKenzie
The complexity of tensor calculus. Comput. Complex. 11 (1-2) (2002)
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer
The Descriptive Complexity Approach to LOGCFL. J. Comput. Syst. Sci. 62 (4) (2001)
David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie
On the Complexity of Some Problems on Groups Input as Multiplication Tables. J. Comput. Syst. Sci. 63 (2) (2001)
Carsten Damm, Markus Holzer, Pierre McKenzie
The Complexity of Tensor Calculus Electron. Colloquium Comput. Complex. 7 (36) (2000)
Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer
The Many Faces of a Translation. ICALP (2000)
Markus Holzer, Pierre McKenzie
Alternating and Empty Alternating Auxiliary Stack Automata. MFCS (2000)
Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp
Reversible Space Equals Deterministic Space. J. Comput. Syst. Sci. 60 (2) (2000)
Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner
Arithmetic Circuits and Polynomial Replacement Systems. FSTTCS (2000)
David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie
On the Complexity of Some Problems on Groups Input as Multiplication Tables. Computational Complexity Conference (2000)
Carsten Damm, Markus Holzer, Pierre McKenzie
The Complexity of Tensor Calculus. Computational Complexity Conference (2000)
David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien
Equation Satisfiability and Program Satisfiability for Finite Monoids. MFCS (2000)
Augustin Baziramwabo, Pierre McKenzie, Denis Thérien
Modular Temporal Logic. LICS (1999)
Pierre McKenzie, Klaus Reinhardt, V. Vinay
Circuits and Context-Free Languages. COCOON (1999)
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer
The Descriptive Complexity Approach to LOGCFL. STACS (1999)
Ran Raz, Pierre McKenzie
Separation of the Monotone NC Hierarchy. Comb. 19 (3) (1999)
Klaus-Jörn Lange, Pierre McKenzie
On the Complexity of Free Monoid Morphisms. ISAAC (1998)
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer
The descriptive complexity approach to LOGCFL CoRR (1998)
Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer
Computation. J. Comput. Syst. Sci. 57 (2) (1998)
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer
The Descriptive Complexity Approach to LOGCFL Electron. Colloquium Comput. Complex. 5 (59) (1998)
Birgit Jenner, Pierre McKenzie, Jacobo Torán
A Note on the Hardness of Tree Isomorphism. Computational Complexity Conference (1998)
Martin Beaudry, Pierre McKenzie, Pierre Péladeau, Denis Thérien
Finite Moniods: From Word to Circuit Evaluation. SIAM J. Comput. 26 (1) (1997)
Alain Finkel, Pierre McKenzie
Verifying Identical Communicating Processes is Undecidable. Theor. Comput. Sci. 174 (1-2) (1997)
Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp
Reversible Space Equals Deterministic Space. Computational Complexity Conference (1997)
Ran Raz, Pierre McKenzie
Separation of the Monotone NC Hierarchy. FOCS (1997)
Birgit Jenner, Pierre McKenzie, Denis Thérien
Logspace and Logtime Leaf Languages. Inf. Comput. 129 (1) (1996)
Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer
Computation. Computational Complexity Conference (1996)
Martin Beaudry, Pierre McKenzie
Circuits, Matrices, and Nonassociative Computation. J. Comput. Syst. Sci. 50 (3) (1995)
Pierre McKenzie, Denis Thérien
Special Issue on Circuit Complexity: Foreword. Comput. Complex. 4 (1994)
Birgit Jenner, Pierre McKenzie, Denis Thérien
Logspace and Logtime Leaf Languages. Computational Complexity Conference (1994)
François Bédard, François Lemieux, Pierre McKenzie
Extensions to Barrington's M-Program Model. Theor. Comput. Sci. 107 (1) (1993)
Martin Beaudry, Pierre McKenzie, Denis Thérien
The Membership Problem in Aperiodic Transformation Monoids. J. ACM 39 (3) (1992)
Martin Beaudry, Pierre McKenzie
Cicuits, Matrices, and Nonassociative Computation. Computational Complexity Conference (1992)
David A. Mix Barrington, Pierre McKenzie
Oracle branching programs and Logspace versus P Inf. Comput. 95 (1) (1991)
Pierre McKenzie, Pierre Péladeau, Denis Thérien
NC¹: The Automata-Theoretic Viewpoint. Comput. Complex. 1 (1991)
François Bédard, François Lemieux, Pierre McKenzie
Extensions to Barrington's M-Program Model. Computational Complexity Conference (1990)
David A. Mix Barrington, Pierre McKenzie
Oracle Branching Programs and Logspace versus P. MFCS (1989)

Pierre McKenzie.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Pierre McKenzie