3 citations · 5 across the 4 of their papers we have counts for
5 papers
The -Complexity Of Visibly Pushdown Languages
Stefan Göller, Nathan Grosshans
We study the question of which visibly pushdown languages (VPLs) are in the complexity class and how to effectively decide this question. Our contribution is to int…
A Note on the Join of Varieties of Monoids with LI
Nathan Grosshans
In this note, we give a characterisation in terms of identities of the join of with the variety of finite locally trivial semigroups for several well-kno…
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…
The Power of Programs over Monoids in J and Threshold Dot-depth One Languages
Nathan Grosshans
The model of programs over (finite) monoids, introduced by Barrington and Thérien, gives an interesting way to characterise the circuit complexity class and its sub…
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…