default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDPierre McKenzie
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 2001
[b2]Béatrice Bérard, Michel Bidoit, Alain Finkel, François Laroussinie, Antoine Petit, Laure Petrucci, Philippe Schnoebelen, Pierre McKenzie:
Systems and Software Verification, Model-Checking Techniques and Tools. Springer 2001, ISBN 978-3-642-07478-3, pp. I-XII, 1-190- 1984
- [b1]Pierre McKenzie:
Parallel complexity and permutation groups. University of Toronto, Canada, 1984
Journal Articles
- 2024
- [j46]Yaqiao Li, Pierre McKenzie:
Perspective on complexity measures targeting read-once branching programs. Inf. Comput. 301: 105230 (2024) - 2023
- [j45]Hugo Côté
, Pierre McKenzie:
Catalytic Branching Programs from Groups and General Protocols. ACM Trans. Comput. Theory 15(3-4): 5:1-5:17 (2023) - 2022
- [j44]Nathan Grosshans, Pierre McKenzie, Luc Segoufin:
Tameness and the power of programs over monoids in DA. Log. Methods Comput. Sci. 18(3) (2022) - 2021
- [j43]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): 34:1-34:43 (2021) - 2019
- [j42]Eric Allender, Andreas Krebs, Pierre McKenzie:
Better Complexity Bounds for Cost Register Automata. Theory Comput. Syst. 63(3): 367-385 (2019) - 2018
- [j41]Michael Blondin, Alain Finkel, Pierre McKenzie:
Handling infinitely branching well-structured transition systems. Inf. Comput. 258: 28-49 (2018) - [j40]Michaël Cadilhac, Andreas Krebs, Pierre McKenzie:
The Algebraic Theory of Parikh Automata. Theory Comput. Syst. 62(5): 1241-1268 (2018) - 2017
- [j39]Michael Blondin, Alain Finkel, Pierre McKenzie:
Well Behaved Transition Systems. Log. Methods Comput. Sci. 13(3) (2017) - 2016
- [j38]Michael Blondin, Andreas Krebs, Pierre McKenzie:
The complexity of intersecting finite automata having few final states. Comput. Complex. 25(4): 775-814 (2016) - [j37]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): 5:1-5:34 (2016) - 2014
- [j36]Yara Elias, Pierre McKenzie:
On Generalized Addition Chains. Integers 14: A16 (2014) - 2013
- [j35]Bernd Borchert, Pierre McKenzie, Klaus Reinhardt:
Few Product Gates but Many Zeroes. Chic. J. Theor. Comput. Sci. 2013 (2013) - [j34]Michaël Cadilhac, Alain Finkel, Pierre McKenzie:
Unambiguous constrained Automata. Int. J. Found. Comput. Sci. 24(7): 1099-1116 (2013) - 2012
- [j33]Michaël Cadilhac, Alain Finkel, Pierre McKenzie:
Bounded Parikh Automata. Int. J. Found. Comput. Sci. 23(8): 1691-1710 (2012) - [j32]Michaël Cadilhac, Alain Finkel, Pierre McKenzie:
Affine Parikh automata. RAIRO Theor. Informatics Appl. 46(4): 511-545 (2012) - [j31]Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam:
Pebbles and Branching Programs for Tree Evaluation. ACM Trans. Comput. Theory 3(2): 4:1-4:43 (2012) - 2010
- [j30]Pierre McKenzie, Michael Thomas, Heribert Vollmer:
Extensional Uniformity for Boolean Circuits. SIAM J. Comput. 39(7): 3186-3206 (2010) - 2009
- [j29]Luc Longpré, Pierre McKenzie:
The complexity of Solitaire. Theor. Comput. Sci. 410(50): 5252-5260 (2009) - 2008
- [j28]Anna Gál, Michal Koucký, Pierre McKenzie:
Incremental Branching Programs. Theory Comput. Syst. 43(2): 159-184 (2008) - [j27]Hugues Mercier, Pierre McKenzie, Stefan Wolf:
Worst Case Nonzero-Error Interactive Communication. IEEE Trans. Inf. Theory 54(7): 2857-2867 (2008) - 2007
- [j26]Pierre McKenzie, Klaus W. Wagner:
The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers. Comput. Complex. 16(3): 211-244 (2007) - 2006
- [j25]Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer:
The many faces of a translation. J. Comput. Syst. Sci. 72(1): 163-179 (2006) - [j24]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): 783 (2006) - 2004
- [j23]Alain Finkel, Pierre McKenzie, Claudine Picaronny:
A well-structured framework for analysing petri net extensions. Inf. Comput. 195(1-2): 1-29 (2004) - [j22]Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner:
Arithmetic Circuits and Polynomial Replacement Systems. SIAM J. Comput. 33(6): 1513-1531 (2004) - 2003
- [j21]Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán:
Completeness results for graph isomorphism. J. Comput. Syst. Sci. 66(3): 549-566 (2003) - [j20]Markus Holzer, Pierre McKenzie:
Alternating and empty alternating auxiliary stack automata. Theor. Comput. Sci. 299(1-3): 307-326 (2003) - 2002
- [j19]Carsten Damm, Markus Holzer, Pierre McKenzie:
The complexity of tensor calculus. Comput. Complex. 11(1-2): 54-89 (2002) - 2001
- [j18]Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer:
The Descriptive Complexity Approach to LOGCFL. J. Comput. Syst. Sci. 62(4): 629-652 (2001) - [j17]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): 186-200 (2001) - 2000
- [j16]Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp:
Reversible Space Equals Deterministic Space. J. Comput. Syst. Sci. 60(2): 354-367 (2000) - 1999
- [j15]Ran Raz, Pierre McKenzie:
Separation of the Monotone NC Hierarchy. Comb. 19(3): 403-435 (1999) - 1998
- [j14]Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer:
Nondeterministic NC1 Computation. J. Comput. Syst. Sci. 57(2): 200-212 (1998) - 1997
- [j13]Martin Beaudry, Pierre McKenzie, Pierre Péladeau, Denis Thérien:
Finite Moniods: From Word to Circuit Evaluation. SIAM J. Comput. 26(1): 138-152 (1997) - [j12]Alain Finkel, Pierre McKenzie:
Verifying Identical Communicating Processes is Undecidable. Theor. Comput. Sci. 174(1-2): 217-230 (1997) - 1996
- [j11]Birgit Jenner, Pierre McKenzie, Denis Thérien:
Logspace and Logtime Leaf Languages. Inf. Comput. 129(1): 21-33 (1996) - 1995
- [j10]Martin Beaudry, Pierre McKenzie:
Circuits, Matrices, and Nonassociative Computation. J. Comput. Syst. Sci. 50(3): 441-455 (1995) - 1994
- [j9]Pierre McKenzie, Denis Thérien:
Special Issue on Circuit Complexity: Foreword. Comput. Complex. 4: 297-300 (1994) - 1993
- [j8]François Bédard, François Lemieux, Pierre McKenzie:
Extensions to Barrington's M-Program Model. Theor. Comput. Sci. 107(1): 31-61 (1993) - 1992
- [j7]Martin Beaudry, Pierre McKenzie, Denis Thérien:
The Membership Problem in Aperiodic Transformation Monoids. J. ACM 39(3): 599-616 (1992) - 1991
- [j6]Pierre McKenzie, Pierre Péladeau, Denis Thérien:
NC¹: The Automata-Theoretic Viewpoint. Comput. Complex. 1: 330-359 (1991) - [j5]David A. Mix Barrington, Pierre McKenzie:
Oracle branching programs and Logspace versus P. Inf. Comput. 95(1): 96-115 (1991) - 1988
- [j4]Eugene M. Luks, Pierre McKenzie:
Parallel Algorithms for Solvable Permutation Groups. J. Comput. Syst. Sci. 37(1): 39-62 (1988) - 1987
- [j3]Stephen A. Cook, Pierre McKenzie:
Problems Complete for Deterministic Logarithmic Space. J. Algorithms 8(3): 385-394 (1987) - [j2]Pierre McKenzie, Stephen A. Cook:
The Parallel Complexity of Abelian Permutation Group Problems. SIAM J. Comput. 16(5): 880-909 (1987) - 1984
- [j1]Pierre McKenzie:
Permutations of Bounded Degree Generate Groups of Polynomial Diameter. Inf. Process. Lett. 19(5): 253-254 (1984)
Conference and Workshop Papers
- 2017
- [c44]Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani:
Does Looking Inside a Circuit Help?. MFCS 2017: 1:1-1:13 - [c43]Nathan Grosshans, Pierre McKenzie, Luc Segoufin:
The Power of Programs over Monoids in DA. MFCS 2017: 2:1-2:20 - [c42]Eric Allender, Andreas Krebs, Pierre McKenzie:
Better Complexity Bounds for Cost Register Automata. MFCS 2017: 24:1-24:14 - 2015
- [c41]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: 32-43 - 2014
- [c40]Michael Blondin, Alain Finkel, Pierre McKenzie:
Handling Infinitely Branching WSTS. ICALP (2) 2014: 13-25 - [c39]Michaël Cadilhac, Andreas Krebs, Pierre McKenzie:
Extremely uniform branching programs. NCMA 2014: 73-83 - 2013
- [c38]Michaël Cadilhac, Andreas Krebs, Pierre McKenzie:
The Algebraic Theory of Parikh Automata. CAI 2013: 60-73 - [c37]Pierre McKenzie:
Can Chimps Go It Alone? DCFS 2013: 17 - 2012
- [c36]Michael Blondin, Pierre McKenzie:
The Complexity of Intersecting Finite Automata Having Few Final States. CSR 2012: 31-42 - [c35]Michaël Cadilhac, Alain Finkel, Pierre McKenzie:
Unambiguous Constrained Automata. Developments in Language Theory 2012: 239-250 - [c34]Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie:
The Lower Reaches of Circuit Uniformity. MFCS 2012: 590-602 - 2011
- [c33]Michaël Cadilhac, Alain Finkel, Pierre McKenzie:
On the Expressiveness of Parikh Automata and Related Models. NCMA 2011: 103-119 - [c32]Michaël Cadilhac, Alain Finkel, Pierre McKenzie:
Bounded Parikh Automata. WORDS 2011: 93-102 - 2010
- [c31]Markus Holzer, Pierre McKenzie:
The Computational Complexity of RaceTrack. FUN 2010: 260-271 - 2009
- [c30]Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr:
Fractional Pebbling and Thrifty Branching Programs. FSTTCS 2009: 109-120 - [c29]Bernd Borchert, Pierre McKenzie, Klaus Reinhardt:
Few Product Gates But Many Zeros. MFCS 2009: 162-174 - [c28]Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr:
Branching Programs for Tree Evaluation. MFCS 2009: 175-186 - 2008
- [c27]Pierre McKenzie, Michael Thomas, Heribert Vollmer:
Extensional Uniformity for Boolean Circuits. CSL 2008: 64-78 - 2007
- [c26]Luc Longpré, Pierre McKenzie:
The Complexity of Solitaire. MFCS 2007: 182-193 - 2006
- [c25]Anna Gál, Michal Koucký, Pierre McKenzie:
Incremental Branching Programs. CSR 2006: 178-190 - 2005
- [c24]Hugues Mercier, Pierre McKenzie, Stefan Wolf:
Worst-case randomized interactive communication. ISIT 2005: 430-434 - 2003
- [c23]Pierre McKenzie, Klaus W. Wagner:
The Complexity of Membership Problems for Circuits over Sets of Natural Numbers. STACS 2003: 571-582 - 2000
- [c22]David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie:
On the Complexity of Some Problems on Groups Input as Multiplication Tables. CCC 2000: 62-69 - [c21]Carsten Damm, Markus Holzer, Pierre McKenzie:
The Complexity of Tensor Calculus. CCC 2000: 70-86 - [c20]Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner:
Arithmetic Circuits and Polynomial Replacement Systems. FSTTCS 2000: 164-175 - [c19]Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer:
The Many Faces of a Translation. ICALP 2000: 890-901 - [c18]David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien:
Equation Satisfiability and Program Satisfiability for Finite Monoids. MFCS 2000: 172-181 - [c17]Markus Holzer, Pierre McKenzie:
Alternating and Empty Alternating Auxiliary Stack Automata. MFCS 2000: 415-425 - 1999
- [c16]Pierre McKenzie, Klaus Reinhardt, V. Vinay:
Circuits and Context-Free Languages. COCOON 1999: 194-203 - [c15]Augustin Baziramwabo, Pierre McKenzie, Denis Thérien:
Modular Temporal Logic. LICS 1999: 344-351 - [c14]Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer:
The Descriptive Complexity Approach to LOGCFL. STACS 1999: 444-454 - 1998
- [c13]Birgit Jenner, Pierre McKenzie, Jacobo Torán:
A Note on the Hardness of Tree Isomorphism. CCC 1998: 101-105 - [c12]Klaus-Jörn Lange, Pierre McKenzie:
On the Complexity of Free Monoid Morphisms. ISAAC 1998: 247-256 - 1997
- [c11]Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp:
Reversible Space Equals Deterministic Space. CCC 1997: 45-50 - [c10]Ran Raz, Pierre McKenzie:
Separation of the Monotone NC Hierarchy. FOCS 1997: 234-243 - 1996
- [c9]Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer:
Nondeterministic NC1 Computation. CCC 1996: 12-21 - 1994
- [c8]Birgit Jenner, Pierre McKenzie, Denis Thérien:
Logspace and Logtime Leaf Languages. SCT 1994: 242-254 - 1992
- [c7]Martin Beaudry, Pierre McKenzie:
Cicuits, Matrices, and Nonassociative Computation. SCT 1992: 94-106 - 1990
- [c6]François Bédard, François Lemieux, Pierre McKenzie:
Extensions to Barrington's M-Program Model. SCT 1990: 200-209 - 1989
- [c5]Pierre McKenzie, Denis Thérien:
Automata Theory Meets Circuit Complexity. ICALP 1989: 589-602 - [c4]David A. Mix Barrington, Pierre McKenzie:
Oracle Branching Programs and Logspace versus P. MFCS 1989: 370-379 - [c3]Martin Beaudry, Pierre McKenzie, Denis Thérien:
Testing Membership: Beyond Permutation Groups (Extended Abstract). STACS 1989: 388-399 - 1985
- [c2]Eugene M. Luks, Pierre McKenzie:
Fast Parallel Computation with Permutation Groups. FOCS 1985: 505-514 - 1983
- [c1]Pierre McKenzie, Stephen A. Cook:
The Parallel Complexity of the Abelian Permutation Group Membership Problem. FOCS 1983: 154-161
Parts in Books or Collections
- 2023
- [p2]Paul Beame, Pierre McKenzie:
Towards a Complexity Theory of Parallel Computation. Logic, Automata, and Computational Complexity 2023: 107-126 - [p1]Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam:
Pebbles and Branching Programs for Tree Evaluation. Logic, Automata, and Computational Complexity 2023: 261-318
Editorship
- 2017
- [e1]Hamed Hatami, Pierre McKenzie, Valerie King:
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017. ACM 2017, ISBN 978-1-4503-4528-6 [contents]
Informal and Other Publications
- 2023
- [i20]Yaqiao Li, Pierre McKenzie:
Perspective on complexity measures targetting read-once branching programs. CoRR abs/2305.11276 (2023) - 2021
- [i19]Nathan Grosshans, Pierre McKenzie, Luc Segoufin:
Tameness and the power of programs over monoids in DA. CoRR abs/2101.07495 (2021) - 2017
- [i18]Eric Allender, Andreas Krebs, Pierre McKenzie:
Better Complexity Bounds for Cost Register Machines. Electron. Colloquium Comput. Complex. TR17 (2017) - [i17]Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani:
Does Looking Inside a Circuit Help? Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i16]Yara Elias, Pierre McKenzie:
On Generalized Addition Chains. CoRR abs/1607.07011 (2016) - [i15]Paul Beame, Nathan Grosshans, Pierre McKenzie, Luc Segoufin:
Nondeterminism and an abstract formulation of Nečiporuk's lower bound method. CoRR abs/1608.01932 (2016) - [i14]Michael Blondin, Alain Finkel, Pierre McKenzie:
Well Behaved Transition Systems. CoRR abs/1608.02636 (2016) - 2014
- [i13]Michael Blondin, Alain Finkel, Stefan Göller, Christoph Haase, Pierre McKenzie:
Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete. CoRR abs/1412.4259 (2014) - [i12]Javier Esparza, Alain Finkel, Pierre McKenzie, Joël Ouaknine:
Reachability Problems for Infinite-State Systems (Dagstuhl Seminar 14141). Dagstuhl Reports 4(3): 153-180 (2014) - 2013
- [i11]Michaël Cadilhac, Andreas Krebs, Pierre McKenzie:
The Algebraic Theory of Parikh Automata. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [i10]Michael Blondin, Andreas Krebs, Pierre McKenzie:
The Complexity of Intersecting Finite Automata Having Few Final States. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [i9]Michaël Cadilhac, Alain Finkel, Pierre McKenzie:
Storming the Parikh Automaton. CoRR abs/1101.1547 (2011) - [i8]Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie:
Low uniform versions of NC1. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [i7]Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam:
Pebbles and Branching Programs for Tree Evaluation. CoRR abs/1005.2642 (2010) - 2008
- [i6]Pierre McKenzie, Michael Thomas, Heribert Vollmer:
Extensional Uniformity for Boolean Circuits. CoRR abs/0805.4072 (2008) - 2006
- [i5]Anna Gál, Pierre McKenzie, Michal Koucký:
Incremental branching programs. Complexity of Boolean Functions 2006 - 2005
- [i4]Anna Gál, Michal Koucký, Pierre McKenzie:
Incremental branching programs. Electron. Colloquium Comput. Complex. TR05 (2005) - 2000
- [i3]Carsten Damm, Markus Holzer, Pierre McKenzie:
The Complexity of Tensor Calculus. Electron. Colloquium Comput. Complex. TR00 (2000) - 1998
- [i2]Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer:
The descriptive complexity approach to LOGCFL. CoRR cs.CC/9809114 (1998) - [i1]Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer:
The Descriptive Complexity Approach to LOGCFL. Electron. Colloquium Comput. Complex. TR98 (1998)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-11-07 21:32 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
