Zobrazeno 1 - 9
of 9
pro vyhledávání: '"Grosshans, Nathan"'
Autor:
Göller, Stefan, Grosshans, Nathan
We study the question of which visibly pushdown languages (VPLs) are in the complexity class $\mathsf{AC}^0$ and how to effectively decide this question. Our contribution is to introduce a particular subclass of one-turn VPLs, called intermediate VPL
Externí odkaz:
http://arxiv.org/abs/2302.13116
Autor:
Grosshans, Nathan
Publikováno v:
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Aug 2021, Tallinn, Estonia. pp.51:1--51:16
In this note, we give a characterisation in terms of identities of the join of $\mathbf{V}$ with the variety of finite locally trivial semigroups $\mathbf{LI}$ for several well-known varieties of finite monoids $\mathbf{V}$ by using classical algebra
Externí odkaz:
http://arxiv.org/abs/2103.15659
Publikováno v:
Logical Methods in Computer Science, Volume 18, Issue 3 (August 2, 2022) lmcs:7110
The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class $\mathsf{NC^1}$. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condit
Externí odkaz:
http://arxiv.org/abs/2101.07495
Autor:
Grosshans, Nathan
Cette thèse porte sur des minorants pour des mesures de complexité liées à des sous-classes de la classe P de langages pouvant être décidés en temps polynomial par des machines de Turing. Nous considérons des modèles de calcul non uniformes
Externí odkaz:
http://www.theses.fr/2018SACLN028/document
Autor:
Grosshans, Nathan
The model of programs over (finite) monoids, introduced by Barrington and Th\'erien, gives an interesting way to characterise the circuit complexity class $\mathsf{NC^1}$ and its subclasses and showcases deep connections with algebraic automata theor
Externí odkaz:
http://arxiv.org/abs/1912.07992
A formulation of "Ne\v{c}iporuk's lower bound method" slightly more inclusive than the usual complexity-measure-specific formulation is presented. Using this general formulation, limitations to lower bounds achievable by the method are obtained for s
Externí odkaz:
http://arxiv.org/abs/1608.01932
Publikováno v:
Logical Methods in Computer Science
Logical Methods in Computer Science, 2022, 18 (3), pp.14:1-14:34. ⟨10.46298/lmcs-18(3:14)2022⟩
Logical Methods in Computer Science, 2022, 18 (3), pp.14:1-14:34. ⟨10.46298/lmcs-18(3:14)2022⟩
International audience; The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class $\mathsf{NC^1}$. Here we make progress in understanding the subtleties of the model. First, we identi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a6bfc0044029e6e3740b3df6122dbaff
https://lmcs.episciences.org/7110
https://lmcs.episciences.org/7110
Autor:
Grosshans, Nathan
Publikováno v:
Language and Automata Theory and Applications
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 subclasses and showcases deep connections with algebraic automata theory. In this articl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=pmc_________::e8a4119c82a8aa842a08255c04b7f030
http://europepmc.org/articles/PMC7206935
http://europepmc.org/articles/PMC7206935
