Publications de McKenzie
Publications of mckenzie

Juillet 2016 - août 2013

[1] M. Blondin, A. Finkel, S. Göller, C. Haase and P. McKenzie, Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete, Proc. 30th ACM/IEEE Symp. on Logic in Computer Science (LICS 2015), IEEE Comp. Soc., pp. 32 - 45. [DOI] [CoRR]

[2] M. Cadilhac, A. Krebs and P. McKenzie, Extremely uniform branching programs, Proc. Sixth Workshop on Non-Classical Models for Automata and Applications (NCMA 2014), Österreichische Computer Gesellschaft, series books@ocg.at, v. 304, pp. 73 - 83. [DOI] [pdf]

[3] M. Blondin, A. Finkel and P. McKenzie, Handling infinitely branching WSTS, Proc. 41th Int. Colloq. on Automata, Languages and Programming (ICALP 2014), Springer LNCS 8573, 2014, pp. 13 - 24. [DOI]

[4] M. Blondin, A. Krebs and P. McKenzie, The Complexity of Intersecting Finite Automata Having Few Final States, to appear in Computational Complexity, First online Sept. 6th 2014, pp. 1 - 40.

[5] Y. Elias and P. McKenzie, On Generalized Addition Chains, Electronic Journal of Combinatorial Number Theory, vol. 14 (2014), no. A16, pp. 1 - 13. [DOI] [pdf]

[6] M. Cadilhac, A. Finkel and P. McKenzie, Unambiguous constrained automata, Int. J. Found. Comput. Sci. v. 24, no. 7, 2013 (DLT 2012 special issue), pp. 1099 - 1116. [DOI]


Avant août 2013:
2013
[75] Few Product Gates but Many Zeroes (Pierre McKenzie Bernd Borchert, Klaus Reinhardt), In Chicago Journal of Theoretical Computer Science, volume 2013, 2013. [bibtex] [pdf]
[74] Can Chimps Go It Alone? (Invited talk) (Pierre McKenzie), In DCFS, 2013. (preprint) [bibtex] [pdf]
[73] The Algebraic Theory of Parikh Automata (Michaël Cadilhac, Andreas Krebs, Pierre McKenzie), In Electronic Colloquium on Computational Complexity (ECCC), volume 20, 2013. [bibtex] [pdf]
[72] The Algebraic Theory of Parikh Automata (Michaël Cadilhac, Andreas Krebs, Pierre McKenzie), In CAI, 2013. (preprint) [bibtex] [pdf]
2012
[71] Pebbles and Branching Programs for Tree Evaluation (Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam), In TOCT, volume 3, 2012. [bibtex] [pdf]
[70] Unambiguous Constrained Automata (Michaël Cadilhac, Alain Finkel, Pierre McKenzie), In Developments in Language Theory, 2012. [bibtex] [pdf]
[69] Bounded Parikh Automata (Michaël Cadilhac, Alain Finkel, Pierre McKenzie), In Int. J. Found. Comput. Sci., volume 23, 2012. [bibtex] [pdf]
[68] Affine Parikh automata (Michaël Cadilhac, Alain Finkel, Pierre McKenzie), In RAIRO - Theor. Inf. and Applic., volume 46, 2012. [bibtex] [pdf]
[67] The Complexity of Intersecting Finite Automata Having Few Final States (Michael Blondin, Pierre McKenzie), In CSR, 2012. [bibtex] [pdf]
[66] The Complexity of Intersecting Finite Automata Having Few Final States (Michael Blondin, Andreas Krebs, Pierre McKenzie), In Electronic Colloquium on Computational Complexity (ECCC), volume 19, 2012. [bibtex] [pdf]
[65] The Lower Reaches of Circuit Uniformity (Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie), In MFCS, 2012. [bibtex] [pdf]
2011
[64] Bounded Parikh Automata (Michaël Cadilhac, Alain Finkel, Pierre McKenzie), In WORDS, 2011. (precursor to IJFCS 2012) [bibtex] [pdf]
[63] On the Expressiveness of Parikh Automata and Related Models (Michaël Cadilhac, Alain Finkel, Pierre McKenzie), In NCMA (Rudolf Freund, Markus Holzer, Carlo Mereghetti, Friedrich Otto, Beatrice Palano, eds.), Austrian Computer Society, volume 282, 2011. [bibtex] [pdf]
[62] Low uniform versions of NC1 (Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie), In Electronic Colloquium on Computational Complexity (ECCC), volume 18, 2011. [bibtex] [pdf]
2010
[61] Extensional Uniformity for Boolean Circuits (Pierre McKenzie, Michael Thomas, Heribert Vollmer), In SIAM J. Comput., volume 39, 2010. [bibtex] [pdf]
[60] The Computational Complexity of RaceTrack (Markus Holzer, Pierre McKenzie), In FUN, 2010. (preprint) [bibtex] [pdf]
2009
[59] The complexity of Solitaire (Luc Longpré, Pierre McKenzie), In Theor. Comput. Sci., volume 410, 2009. [bibtex] [pdf]
[58] Branching Programs for Tree Evaluation (Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr), In MFCS, 2009. (precursor with FSTTCS 2009 to TOCT 2012) [bibtex] [pdf]
[57] Fractional Pebbling and Thrifty Branching Programs (Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr), In FSTTCS, 2009. (precursor with MFCS 2009 to TOCT 2012) [bibtex] [pdf]
[56] Few Product Gates But Many Zeros (Bernd Borchert, Pierre McKenzie, Klaus Reinhardt), In MFCS, 2009. (precursor to CJTCS 2013) [bibtex] [pdf]
2008
[55] Worst Case Nonzero-Error Interactive Communication (Hugues Mercier, Pierre McKenzie, Stefan Wolf), In IEEE Transactions on Information Theory, volume 54, 2008. [bibtex] [pdf]
[54] Extensional Uniformity for Boolean Circuits (Pierre McKenzie, Michael Thomas, Heribert Vollmer), In CSL, 2008. (precursor to SIAM 2010) [bibtex] [pdf]
[53] Incremental Branching Programs (Anna Gál, Michal Koucký, Pierre McKenzie), In Theory Comput. Syst., volume 43, 2008. [bibtex] [pdf]
2007
[52] The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers (Pierre McKenzie, Klaus W. Wagner), In Computational Complexity, volume 16, 2007. [bibtex] [pdf]
[51] The Complexity of Solitaire (Luc Longpré, Pierre McKenzie), In MFCS, 2007. (precursor to TCS 2007) [bibtex] [pdf]
2006
[50] The many faces of a translation (Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer), In J. Comput. Syst. Sci., volume 72, 2006. [bibtex] [pdf]
[49] 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), In J. Comput. Syst. Sci., volume 72, 2006. [bibtex] [pdf]
[48] Incremental branching programs (Anna Gál, Pierre McKenzie, Michal Koucký), In Complexity of Boolean Functions, 2006. (can serve as preprint for ToCS 2008) [bibtex] [pdf]
[47] Incremental Branching Programs (Anna Gál, Michal Koucký, Pierre McKenzie), In CSR, 2006. (precursor to ToCS 2008) [bibtex] [pdf]
2004
[46] Arithmetic Circuits and Polynomial Replacement Systems (Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner), In SIAM J. Comput., volume 33, 2004. [bibtex] [pdf]
[45] A well-structured framework for analysing petri net extensions (Alain Finkel, Pierre McKenzie, Claudine Picaronny), In Inf. Comput., volume 195, 2004. [bibtex] [pdf]
2003
[44] The Complexity of Membership Problems for Circuits over Sets of Natural Numbers (Pierre McKenzie, Klaus W. Wagner), In STACS, 2003. (precursor to CC 2007) [bibtex] [pdf]
[43] Completeness results for graph isomorphism (Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán), In J. Comput. Syst. Sci., volume 66, 2003. [bibtex] [pdf]
[42] Alternating and empty alternating auxiliary stack automata (Markus Holzer, Pierre McKenzie), In Theor. Comput. Sci., volume 1-3, 2003. [bibtex] [pdf]
2002
[41] The complexity of tensor calculus (Carsten Damm, Markus Holzer, Pierre McKenzie), In Computational Complexity, volume 11, 2002. [bibtex] [pdf]
2001
[40] The Descriptive Complexity Approach to LOGCFL (Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer), In J. Comput. Syst. Sci., volume 62, 2001. [bibtex] [pdf]
[39] On the Complexity of Some Problems on Groups Input as Multiplication Tables (David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie), In J. Comput. Syst. Sci., volume 63, 2001. [bibtex] [pdf]
2000
[38] Arithmetic Circuits and Polynomial Replacement Systems (Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner), In FSTTCS, 2000. (precursor to SIAM 2004) [bibtex] [pdf]
[37] The Many Faces of a Translation (Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer), In ICALP, 2000. (precursor to JCSS 2006) [bibtex] [pdf]
[36] Reversible Space Equals Deterministic Space (Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp), In J. Comput. Syst. Sci., volume 60, 2000. [bibtex] [pdf]
[35] Alternating and Empty Alternating Auxiliary Stack Automata (Markus Holzer, Pierre McKenzie), In MFCS, 2000. (precursor to TCS 2003) [bibtex] [pdf]
[34] The Complexity of Tensor Calculus (Carsten Damm, Markus Holzer, Pierre McKenzie), In IEEE Conference on Computational Complexity, 2000. (precursor to CC 2002) [bibtex] [pdf]
[33] Equation Satisfiability and Program Satisfiability for Finite Monoids (David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien), In MFCS, 2000. [bibtex] [pdf]
[32] On the Complexity of Some Problems on Groups Input as Multiplication Tables (David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie), In IEEE Conference on Computational Complexity, 2000. (precursor to JCSS 2000) [bibtex] [pdf]
1999
[31] Separation of the Monotone NC Hierarchy (Ran Raz, Pierre McKenzie), In Combinatorica, volume 19, 1999. [bibtex] [pdf]
[30] Circuits and Context-Free Languages (Pierre McKenzie, Klaus Reinhardt, V. Vinay), In COCOON, 1999. (preprint) [bibtex] [pdf]
[29] The Descriptive Complexity Approach to LOGCFL (Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer), In STACS, 1999. (precursor to JCSS 2001) [bibtex] [pdf]
[28] Modular Temporal Logic (Augustin Baziramwabo, Pierre McKenzie, Denis Thérien), In LICS, 1999. [bibtex] [pdf]
1998
[27] On the Complexity of Free Monoid Morphisms (Klaus-Jörn Lange, Pierre McKenzie), In ISAAC, 1998. (preprint) [bibtex] [pdf]
[26] A Note on the Hardness of Tree Isomorphism (Birgit Jenner, Pierre McKenzie, Jacobo Torán), In IEEE Conference on Computational Complexity, 1998. (subsumed by JCSS 2001) [bibtex] [pdf]
[25] Nondeterministic it NC$^\mbox1$ Computation (Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer), In J. Comput. Syst. Sci., volume 57, 1998. [bibtex] [pdf]
1997
[24] Separation of the Monotone NC Hierarchy (Ran Raz, Pierre McKenzie), In FOCS, 1997. (precursor to COMBINATORICA 1999) [bibtex] [pdf]
[23] Reversible Space Equals Deterministic Space (Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp), In IEEE Conference on Computational Complexity, 1997. (precursor to JCSS 2000) [bibtex] [pdf]
[22] Verifying Identical Communicating Processes is Undecidable (Alain Finkel, Pierre McKenzie), In Theor. Comput. Sci., volume 174, 1997. [bibtex] [pdf]
[21] Finite Moniods: From Word to Circuit Evaluation (Martin Beaudry, Pierre McKenzie, Pierre Péladeau, Denis Thérien), In SIAM J. Comput., volume 26, 1997. [bibtex] [pdf]
1996
[20] Logspace and Logtime Leaf Languages (Birgit Jenner, Pierre McKenzie, Denis Thérien), In Inf. Comput., volume 129, 1996. [bibtex] [pdf]
[19] Nondeterministic NC$^\mbox1$ Computation (Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer), In IEEE Conference on Computational Complexity, 1996. (precursor to JCSS 1998) [bibtex] [pdf]
1995
[18] Circuits, Matrices, and Nonassociative Computation (Martin Beaudry, Pierre McKenzie), In J. Comput. Syst. Sci., volume 50, 1995. [bibtex] [pdf]
1994
[17] Special Issue on Circuit Complexity: Foreword (Pierre McKenzie, Denis Thérien), In Computational Complexity, volume 4, 1994. [bibtex] [pdf]
[16] Logspace and Logtime Leaf Languages (Birgit Jenner, Pierre McKenzie, Denis Thérien), In Structure in Complexity Theory Conference, 1994. (precursor to IC 1996) [bibtex] [pdf]
1993
[15] Extensions to Barrington's M-Program Model (François Bédard, François Lemieux, Pierre McKenzie), In Theor. Comput. Sci., volume 107, 1993. [bibtex] [pdf]
1992
[14] The Membership Problem in Aperiodic Transformation Monoids (Martin Beaudry, Pierre McKenzie, Denis Thérien), In J. ACM, volume 39, 1992. [bibtex] [pdf]
[13] Cicuits, Matrices, and Nonassociative Computation (Martin Beaudry, Pierre McKenzie), In Structure in Complexity Theory Conference, 1992. (precursor to JCSS 1995) [bibtex] [pdf]
1991
[12] NC$^1$: The Automata-Theoretic Viewpoint (Pierre McKenzie, Pierre Péladeau, Denis Thérien), In Computational Complexity, volume 1, 1991. [bibtex] [pdf]
[11] Oracle branching programs and Logspace versus P (David A. Mix Barrington, Pierre McKenzie), In Inf. Comput., volume 95, 1991. [bibtex] [pdf]
1990
[10] Extensions to Barrington's M-Program Model (François Bédard, François Lemieux, Pierre McKenzie), In Structure in Complexity Theory Conference, 1990. (precursor to TCS 1993) [bibtex] [pdf]
1989
[9] Automata Theory Meets Circuit Complexity (Pierre McKenzie, Denis Thérien), In ICALP, 1989. (precursor to CC 1991) [bibtex] [pdf]
[8] Testing Membership: Beyond Permutation Groups (Extended Abstract) (Martin Beaudry, Pierre McKenzie, Denis Thérien), In STACS, 1989. (precursor to JACM 1992) [bibtex] [pdf]
[7] Oracle Branching Programs and Logspace versus P (David A. Mix Barrington, Pierre McKenzie), In MFCS, 1989. (precursor to IC 1991) [bibtex] [pdf]
1988
[6] Parallel Algorithms for Solvable Permutation Groups (Eugene M. Luks, Pierre McKenzie), In J. Comput. Syst. Sci., volume 37, 1988. [bibtex] [pdf]
1987
[5] The Parallel Complexity of Abelian Permutation Group Problems (Pierre McKenzie, Stephen A. Cook), In SIAM J. Comput., volume 16, 1987. [bibtex] [pdf]
[4] Problems Complete for Deterministic Logarithmic Space (Stephen A. Cook, Pierre McKenzie), In J. Algorithms, volume 8, 1987. [bibtex] [pdf]
1985
[3] Fast Parallel Computation with Permutation Groups (Eugene M. Luks, Pierre McKenzie), In FOCS, 1985. (precursor to JCSS 1988) [bibtex] [pdf]
1984
[2] Permutations of Bounded Degree Generate Groups of Polynomial Diameter (Pierre McKenzie), In Inf. Process. Lett., volume 19, 1984. [bibtex] [pdf]
1983
[1] The Parallel Complexity of the Abelian Permutation Group Membership Problem (Pierre McKenzie, Stephen A. Cook), In FOCS, 1983. (precursor to SIAM 1987) [bibtex] [pdf]
Powered by bibtexbrowser
2013
[75] Few Product Gates but Many Zeroes (Pierre McKenzie Bernd Borchert, Klaus Reinhardt), In Chicago Journal of Theoretical Computer Science, volume 2013, 2013. [bibtex] [pdf]
[74] Can Chimps Go It Alone? (Invited talk) (Pierre McKenzie), In DCFS, 2013. (preprint) [bibtex] [pdf]
[73] The Algebraic Theory of Parikh Automata (Michaël Cadilhac, Andreas Krebs, Pierre McKenzie), In Electronic Colloquium on Computational Complexity (ECCC), volume 20, 2013. [bibtex] [pdf]
[72] The Algebraic Theory of Parikh Automata (Michaël Cadilhac, Andreas Krebs, Pierre McKenzie), In CAI, 2013. (preprint) [bibtex] [pdf]
2012
[71] Pebbles and Branching Programs for Tree Evaluation (Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam), In TOCT, volume 3, 2012. [bibtex] [pdf]
[70] Unambiguous Constrained Automata (Michaël Cadilhac, Alain Finkel, Pierre McKenzie), In Developments in Language Theory, 2012. [bibtex] [pdf]
[69] Bounded Parikh Automata (Michaël Cadilhac, Alain Finkel, Pierre McKenzie), In Int. J. Found. Comput. Sci., volume 23, 2012. [bibtex] [pdf]
[68] Affine Parikh automata (Michaël Cadilhac, Alain Finkel, Pierre McKenzie), In RAIRO - Theor. Inf. and Applic., volume 46, 2012. [bibtex] [pdf]
[67] The Complexity of Intersecting Finite Automata Having Few Final States (Michael Blondin, Pierre McKenzie), In CSR, 2012. [bibtex] [pdf]
[66] The Complexity of Intersecting Finite Automata Having Few Final States (Michael Blondin, Andreas Krebs, Pierre McKenzie), In Electronic Colloquium on Computational Complexity (ECCC), volume 19, 2012. [bibtex] [pdf]
[65] The Lower Reaches of Circuit Uniformity (Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie), In MFCS, 2012. [bibtex] [pdf]
2011
[64] Bounded Parikh Automata (Michaël Cadilhac, Alain Finkel, Pierre McKenzie), In WORDS, 2011. (precursor to IJFCS 2012) [bibtex] [pdf]
[63] On the Expressiveness of Parikh Automata and Related Models (Michaël Cadilhac, Alain Finkel, Pierre McKenzie), In NCMA (Rudolf Freund, Markus Holzer, Carlo Mereghetti, Friedrich Otto, Beatrice Palano, eds.), Austrian Computer Society, volume 282, 2011. (precursor to RAIRO 2012) [bibtex] [pdf]
[62] Low uniform versions of NC1 (Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie), In Electronic Colloquium on Computational Complexity (ECCC), volume 18, 2011. [bibtex] [pdf]
2010
[61] Extensional Uniformity for Boolean Circuits (Pierre McKenzie, Michael Thomas, Heribert Vollmer), In SIAM J. Comput., volume 39, 2010. [bibtex] [pdf]
[60] The Computational Complexity of RaceTrack (Markus Holzer, Pierre McKenzie), In FUN, 2010. (preprint) [bibtex] [pdf]
2009
[59] The complexity of Solitaire (Luc Longpré, Pierre McKenzie), In Theor. Comput. Sci., volume 410, 2009. [bibtex] [pdf]
[58] Branching Programs for Tree Evaluation (Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr), In MFCS, 2009. (precursor with FSTTCS 2009 to TOCT 2012) [bibtex] [pdf]
[57] Fractional Pebbling and Thrifty Branching Programs (Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr), In FSTTCS, 2009. (precursor with MFCS 2009 to TOCT 2012) [bibtex] [pdf]
[56] Few Product Gates But Many Zeros (Bernd Borchert, Pierre McKenzie, Klaus Reinhardt), In MFCS, 2009. (precursor to CJTCS 2013) [bibtex] [pdf]
2008
[55] Worst Case Nonzero-Error Interactive Communication (Hugues Mercier, Pierre McKenzie, Stefan Wolf), In IEEE Transactions on Information Theory, volume 54, 2008. [bibtex] [pdf]
[54] Extensional Uniformity for Boolean Circuits (Pierre McKenzie, Michael Thomas, Heribert Vollmer), In CSL, 2008. (precursor to SIAM 2010) [bibtex] [pdf]
[53] Incremental Branching Programs (Anna Gál, Michal Koucký, Pierre McKenzie), In Theory Comput. Syst., volume 43, 2008. [bibtex] [pdf]
2007
[52] The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers (Pierre McKenzie, Klaus W. Wagner), In Computational Complexity, volume 16, 2007. [bibtex] [pdf]
[51] The Complexity of Solitaire (Luc Longpré, Pierre McKenzie), In MFCS, 2007. (precursor to TCS 2007) [bibtex] [pdf]
2006
[50] The many faces of a translation (Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer), In J. Comput. Syst. Sci., volume 72, 2006. [bibtex] [pdf]
[49] 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), In J. Comput. Syst. Sci., volume 72, 2006. [bibtex] [pdf]
[48] Incremental branching programs (Anna Gál, Pierre McKenzie, Michal Koucký), In Complexity of Boolean Functions, 2006. (can serve as preprint for ToCS 2008) [bibtex] [pdf]
[47] Incremental Branching Programs (Anna Gál, Michal Koucký, Pierre McKenzie), In CSR, 2006. (precursor to ToCS 2008) [bibtex] [pdf]
2004
[46] Arithmetic Circuits and Polynomial Replacement Systems (Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner), In SIAM J. Comput., volume 33, 2004. [bibtex] [pdf]
[45] A well-structured framework for analysing petri net extensions (Alain Finkel, Pierre McKenzie, Claudine Picaronny), In Inf. Comput., volume 195, 2004. [bibtex] [pdf]
2003
[44] The Complexity of Membership Problems for Circuits over Sets of Natural Numbers (Pierre McKenzie, Klaus W. Wagner), In STACS, 2003. (precursor to CC 2007) [bibtex] [pdf]
[43] Completeness results for graph isomorphism (Birgit Jenner, Johannes Köbler, Pierre McKenzie, Jacobo Torán), In J. Comput. Syst. Sci., volume 66, 2003. [bibtex] [pdf]
[42] Alternating and empty alternating auxiliary stack automata (Markus Holzer, Pierre McKenzie), In Theor. Comput. Sci., volume 1-3, 2003. [bibtex] [pdf]
2002
[41] The complexity of tensor calculus (Carsten Damm, Markus Holzer, Pierre McKenzie), In Computational Complexity, volume 11, 2002. [bibtex] [pdf]
2001
[40] The Descriptive Complexity Approach to LOGCFL (Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer), In J. Comput. Syst. Sci., volume 62, 2001. [bibtex] [pdf]
[39] On the Complexity of Some Problems on Groups Input as Multiplication Tables (David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie), In J. Comput. Syst. Sci., volume 63, 2001. [bibtex] [pdf]
2000
[38] Arithmetic Circuits and Polynomial Replacement Systems (Pierre McKenzie, Heribert Vollmer, Klaus W. Wagner), In FSTTCS, 2000. (precursor to SIAM 2004) [bibtex] [pdf]
[37] The Many Faces of a Translation (Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer), In ICALP, 2000. (precursor to JCSS 2006) [bibtex] [pdf]
[36] Reversible Space Equals Deterministic Space (Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp), In J. Comput. Syst. Sci., volume 60, 2000. [bibtex] [pdf]
[35] Alternating and Empty Alternating Auxiliary Stack Automata (Markus Holzer, Pierre McKenzie), In MFCS, 2000. (precursor to TCS 2003) [bibtex] [pdf]
[34] The Complexity of Tensor Calculus (Carsten Damm, Markus Holzer, Pierre McKenzie), In IEEE Conference on Computational Complexity, 2000. (precursor to CC 2002) [bibtex] [pdf]
[33] Equation Satisfiability and Program Satisfiability for Finite Monoids (David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien), In MFCS, 2000. [bibtex] [pdf]
[32] On the Complexity of Some Problems on Groups Input as Multiplication Tables (David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie), In IEEE Conference on Computational Complexity, 2000. (precursor to JCSS 2000) [bibtex] [pdf]
1999
[31] Separation of the Monotone NC Hierarchy (Ran Raz, Pierre McKenzie), In Combinatorica, volume 19, 1999. [bibtex] [pdf]
[30] Circuits and Context-Free Languages (Pierre McKenzie, Klaus Reinhardt, V. Vinay), In COCOON, 1999. (preprint) [bibtex] [pdf]
[29] The Descriptive Complexity Approach to LOGCFL (Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer), In STACS, 1999. (precursor to JCSS 2001) [bibtex] [pdf]
[28] Modular Temporal Logic (Augustin Baziramwabo, Pierre McKenzie, Denis Thérien), In LICS, 1999. [bibtex] [pdf]
1998
[27] On the Complexity of Free Monoid Morphisms (Klaus-Jörn Lange, Pierre McKenzie), In ISAAC, 1998. (preprint) [bibtex] [pdf]
[26] A Note on the Hardness of Tree Isomorphism (Birgit Jenner, Pierre McKenzie, Jacobo Torán), In IEEE Conference on Computational Complexity, 1998. (subsumed by JCSS 2001) [bibtex] [pdf]
[25] Nondeterministic it NC$^\mbox1$ Computation (Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer), In J. Comput. Syst. Sci., volume 57, 1998. [bibtex] [pdf]
1997
[24] Separation of the Monotone NC Hierarchy (Ran Raz, Pierre McKenzie), In FOCS, 1997. (precursor to COMBINATORICA 1999) [bibtex] [pdf]
[23] Reversible Space Equals Deterministic Space (Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp), In IEEE Conference on Computational Complexity, 1997. (precursor to JCSS 2000) [bibtex] [pdf]
[22] Verifying Identical Communicating Processes is Undecidable (Alain Finkel, Pierre McKenzie), In Theor. Comput. Sci., volume 174, 1997. [bibtex] [pdf]
[21] Finite Moniods: From Word to Circuit Evaluation (Martin Beaudry, Pierre McKenzie, Pierre Péladeau, Denis Thérien), In SIAM J. Comput., volume 26, 1997. [bibtex] [pdf]
1996
[20] Logspace and Logtime Leaf Languages (Birgit Jenner, Pierre McKenzie, Denis Thérien), In Inf. Comput., volume 129, 1996. [bibtex] [pdf]
[19] Nondeterministic NC$^\mbox1$ Computation (Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer), In IEEE Conference on Computational Complexity, 1996. (precursor to JCSS 1998) [bibtex] [pdf]
1995
[18] Circuits, Matrices, and Nonassociative Computation (Martin Beaudry, Pierre McKenzie), In J. Comput. Syst. Sci., volume 50, 1995. [bibtex] [pdf]
1994
[17] Special Issue on Circuit Complexity: Foreword (Pierre McKenzie, Denis Thérien), In Computational Complexity, volume 4, 1994. [bibtex] [pdf]
[16] Logspace and Logtime Leaf Languages (Birgit Jenner, Pierre McKenzie, Denis Thérien), In Structure in Complexity Theory Conference, 1994. (precursor to IC 1996) [bibtex] [pdf]
1993
[15] Extensions to Barrington's M-Program Model (François Bédard, François Lemieux, Pierre McKenzie), In Theor. Comput. Sci., volume 107, 1993. [bibtex] [pdf]
1992
[14] The Membership Problem in Aperiodic Transformation Monoids (Martin Beaudry, Pierre McKenzie, Denis Thérien), In J. ACM, volume 39, 1992. [bibtex] [pdf]
[13] Cicuits, Matrices, and Nonassociative Computation (Martin Beaudry, Pierre McKenzie), In Structure in Complexity Theory Conference, 1992. (precursor to JCSS 1995) [bibtex] [pdf]
1991
[12] NC$^1$: The Automata-Theoretic Viewpoint (Pierre McKenzie, Pierre Péladeau, Denis Thérien), In Computational Complexity, volume 1, 1991. [bibtex] [pdf]
[11] Oracle branching programs and Logspace versus P (David A. Mix Barrington, Pierre McKenzie), In Inf. Comput., volume 95, 1991. [bibtex] [pdf]
1990
[10] Extensions to Barrington's M-Program Model (François Bédard, François Lemieux, Pierre McKenzie), In Structure in Complexity Theory Conference, 1990. (precursor to TCS 1993) [bibtex] [pdf]
1989
[9] Automata Theory Meets Circuit Complexity (Pierre McKenzie, Denis Thérien), In ICALP, 1989. (precursor to CC 1991) [bibtex] [pdf]
[8] Testing Membership: Beyond Permutation Groups (Extended Abstract) (Martin Beaudry, Pierre McKenzie, Denis Thérien), In STACS, 1989. (precursor to JACM 1992) [bibtex] [pdf]
[7] Oracle Branching Programs and Logspace versus P (David A. Mix Barrington, Pierre McKenzie), In MFCS, 1989. (precursor to IC 1991) [bibtex] [pdf]
1988
[6] Parallel Algorithms for Solvable Permutation Groups (Eugene M. Luks, Pierre McKenzie), In J. Comput. Syst. Sci., volume 37, 1988. [bibtex] [pdf]
1987
[5] The Parallel Complexity of Abelian Permutation Group Problems (Pierre McKenzie, Stephen A. Cook), In SIAM J. Comput., volume 16, 1987. [bibtex] [pdf]
[4] Problems Complete for Deterministic Logarithmic Space (Stephen A. Cook, Pierre McKenzie), In J. Algorithms, volume 8, 1987. [bibtex] [pdf]
1985
[3] Fast Parallel Computation with Permutation Groups (Eugene M. Luks, Pierre McKenzie), In FOCS, 1985. (precursor to JCSS 1988) [bibtex] [pdf]
1984
[2] Permutations of Bounded Degree Generate Groups of Polynomial Diameter (Pierre McKenzie), In Inf. Process. Lett., volume 19, 1984. [bibtex] [pdf]
1983
[1] The Parallel Complexity of the Abelian Permutation Group Membership Problem (Pierre McKenzie, Stephen A. Cook), In FOCS, 1983. (precursor to SIAM 1987) [bibtex] [pdf]
Powered by bibtexbrowser