3 papers
cs.FL2023
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…
cs.FL2021
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…
cs.CC2019
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…