45 citations · 90 across the 11 of their papers we have counts for
11 papers
Perspective on complexity measures targetting read-once branching programs
Yaqiao Li, Pierre McKenzie
A model of computation for which reasonable yet still incomplete lower bounds are known is the read-once branching program. Here variants of complexity measures successful in the s…
Tameness and the power of programs over monoids in DA
Nathan Grosshans, Pierre Mckenzie, Luc Segoufin
The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class . Here we make progress in understanding…
Nondeterminism and an abstract formulation of Nečiporuk's lower bound method
Paul Beame, Nathan Grosshans, Pierre McKenzie +1
A formulation of "Nečiporuk's lower bound method" slightly more inclusive than the usual complexity-measure-specific formulation is presented. Using this general formulation, limit…
Well Behaved Transition Systems
Michael Blondin, Alain Finkel, Pierre McKenzie
The well-quasi-ordering (i.e., a well-founded quasi-ordering such that all antichains are finite) that defines well-structured transition systems (WSTS) is shown not to be the weak…
On Generalized Addition Chains
Yara Elias, Pierre McKenzie
Given integers d >= 1, and g >= 2, a g-addition chain for d is a sequence of integers a_0=1, a_1, a_2,..., a_{r-1}, a_r=d where a_i=a_{j_1}+a_{j_2}+...+a_{j_k}, with 2 =< k =< g, a…
Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete
Michael Blondin, Alain Finkel, Stefan Göller +2
Determining the complexity of the reachability problem for vector addition systems with states (VASS) is a long-standing open problem in computer science. Long known to be decidabl…