Pierre McKenzie

According to our database1, Pierre McKenzie
  • authored at least 100 papers between 1983 and 2018.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2018
Handling infinitely branching well-structured transition systems.
Inf. Comput., 2018

2017
Well Behaved Transition Systems.
Logical Methods in Computer Science, 2017

Does Looking Inside a Circuit Help?
Electronic Colloquium on Computational Complexity (ECCC), 2017

Better Complexity Bounds for Cost Register Machines.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Does Looking Inside a Circuit Help?.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

The Power of Programs over Monoids in DA.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Better Complexity Bounds for Cost Register Automata.
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.
TOCT, 2016

On Generalized Addition Chains.
CoRR, 2016

Well Behaved Transition Systems.
CoRR, 2016

Nondeterminism and an abstract formulation of Nečiporuk's lower bound method.
CoRR, 2016

The complexity of intersecting finite automata having few final states.
Computational Complexity, 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
Reachability Problems for Infinite-State Systems (Dagstuhl Seminar 14141).
Dagstuhl Reports, 2014

Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete.
CoRR, 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.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Few Product Gates but Many Zeroes.
Chicago J. Theor. Comput. Sci., 2013

Can Chimps Go It Alone?
Proceedings of the Descriptional Complexity of Formal Systems, 2013

The Algebraic Theory of Parikh Automata.
Proceedings of the Algebraic Informatics - 5th International Conference, 2013

2012
Pebbles and Branching Programs for Tree Evaluation.
TOCT, 2012

Affine Parikh automata.
RAIRO - Theor. Inf. and Applic., 2012

Bounded Parikh Automata.
Int. J. Found. Comput. Sci., 2012

The Complexity of Intersecting Finite Automata Having Few Final States.
Electronic Colloquium on Computational Complexity (ECCC), 2012

The Lower Reaches of Circuit Uniformity.
Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Unambiguous Constrained Automata.
Proceedings of the Developments in Language Theory - 16th International Conference, 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.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Bounded Parikh Automata
Proceedings of the Proceedings 8th International Conference Words 2011, 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

Pebbles and Branching Programs for Tree Evaluation
CoRR, 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. Information Theory, 2008

Incremental Branching Programs.
Theory Comput. Syst., 2008

Extensional Uniformity for Boolean Circuits
CoRR, 2008

Extensional Uniformity for Boolean Circuits.
Proceedings of the Computer Science Logic, 22nd International Workshop, 2008

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

The Complexity of Solitaire.
Proceedings of the Mathematical Foundations of Computer Science 2007, 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

Incremental branching programs.
Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

Incremental Branching Programs.
Proceedings of the Computer Science, 2006

2005
Incremental branching programs
Electronic Colloquium on Computational Complexity (ECCC), 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

The Complexity of Membership Problems for Circuits over Sets of Natural Numbers.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

2002
The complexity of tensor calculus.
Computational Complexity, 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

2000
Reversible Space Equals Deterministic Space.
J. Comput. Syst. Sci., 2000

The Complexity of Tensor Calculus
Electronic Colloquium on Computational Complexity (ECCC), 2000

Alternating and Empty Alternating Auxiliary Stack Automata.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

Equation Satisfiability and Program Satisfiability for Finite Monoids.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

The Many Faces of a Translation.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Arithmetic Circuits and Polynomial Replacement Systems.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

The Complexity of Tensor Calculus.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

On the Complexity of Some Problems on Groups Input as Multiplication Tables.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999
Separation of the Monotone NC Hierarchy.
Combinatorica, 1999

The Descriptive Complexity Approach to LOGCFL.
Proceedings of the STACS 99, 1999

Modular Temporal Logic.
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 NC1 Computation.
J. Comput. Syst. Sci., 1998

The Descriptive Complexity Approach to LOGCFL
Electronic Colloquium on Computational Complexity (ECCC), 1998

The descriptive complexity approach to LOGCFL
CoRR, 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

Separation of the Monotone NC Hierarchy.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Reversible Space Equals Deterministic Space.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996
Logspace and Logtime Leaf Languages.
Inf. Comput., 1996

Nondeterministic NC1 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.
Computational Complexity, 1994

Logspace and Logtime Leaf Languages.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 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.
Computational Complexity, 1991

1990
Extensions to Barrington's M-Program Model.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
Testing Membership: Beyond Permutation Groups (Extended Abstract).
Proceedings of the STACS 89, 1989

Oracle Branching Programs and Logspace versus P.
Proceedings of the Mathematical Foundations of Computer Science 1989, 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
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


  Loading...