Search Results

Documents authored by Grosshans, Nathan

Document
DOI: 10.4230/LIPIcs.STACS.2024.38
The AC⁰-Complexity of Visibly Pushdown Languages

Authors: Stefan Göller and Nathan Grosshans

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
We study the question of which visibly pushdown languages (VPLs) are in the complexity class AC⁰ and how to effectively decide this question. Our contribution is to introduce a particular subclass of one-turn VPLs, called intermediate VPLs, for which the raised question is entirely unclear: to the best of our knowledge our research community is unaware of containment or non-containment in AC⁰ for any language in our newly introduced class. Our main result states that there is an algorithm that, given a visibly pushdown automaton, correctly outputs exactly one of the following: that its language L is in AC⁰, some m ≥ 2 such that MODₘ (the words over {0,1} having a number of 1’s divisible by m) is constant-depth reducible to L (implying that L is not in AC⁰), or a finite disjoint union of intermediate VPLs that L is constant-depth equivalent to. In the latter of the three cases one can moreover effectively compute k,l ∈ ℕ_{> 0} with k≠l such that the concrete intermediate VPL L(S → ε ∣ ac^{k-1}Sb₁ ∣ ac^{l-1}Sb₂) is constant-depth reducible to the language L. Due to their particular nature we conjecture that either all intermediate VPLs are in AC⁰ or all are not. As a corollary of our main result we obtain that in case the input language is a visibly counter language our algorithm can effectively determine if it is in AC⁰ - hence our main result generalizes a result by Krebs et al. stating that it is decidable if a given visibly counter language is in AC⁰ (when restricted to well-matched words). For our proofs we revisit so-called Ext-algebras (introduced by Czarnetzki et al.), which are closely related to forest algebras (introduced by Bojańczyk and Walukiewicz), and use Green’s relations.
Cite as

Stefan Göller and Nathan Grosshans. The AC⁰-Complexity of Visibly Pushdown Languages. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{goller_et_al:LIPIcs.STACS.2024.38,
  author =	{G\"{o}ller, Stefan and Grosshans, Nathan},
  title =	{{The AC⁰-Complexity of Visibly Pushdown Languages}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{38:1--38:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.38},
  URN =		{urn:nbn:de:0030-drops-197483},
  doi =		{10.4230/LIPIcs.STACS.2024.38},
  annote =	{Keywords: Visibly pushdown languages, Circuit Complexity, AC0}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.51
A Note on the Join of Varieties of Monoids with LI

Authors: Nathan Grosshans

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
In this note, we give a characterisation in terms of identities of the join of V with the variety of finite locally trivial semigroups LI for several well-known varieties of finite monoids V by using classical algebraic-automata-theoretic techniques. To achieve this, we use the new notion of essentially-V stamps defined by Grosshans, McKenzie and Segoufin and show that it actually coincides with the join of V and LI precisely when some natural condition on the variety of languages corresponding to V is verified. This work is a kind of rediscovery of the work of J. C. Costa around 20 years ago from a rather different angle, since Costa’s work relies on the use of advanced developments in profinite topology, whereas what is presented here essentially uses an algebraic, language-based approach.
Cite as

Nathan Grosshans. A Note on the Join of Varieties of Monoids with LI. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grosshans:LIPIcs.MFCS.2021.51,
  author =	{Grosshans, Nathan},
  title =	{{A Note on the Join of Varieties of Monoids with LI}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{51:1--51:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.51},
  URN =		{urn:nbn:de:0030-drops-144918},
  doi =		{10.4230/LIPIcs.MFCS.2021.51},
  annote =	{Keywords: Varieties of monoids, join, LI}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.2
The Power of Programs over Monoids in DA

Authors: Nathan Grosshans, Pierre McKenzie, and Luc Segoufin

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
The program-over-monoid model of computation originates with Barrington's proof that it captures the complexity class NC^1. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural characterization of the regular languages recognizable by programs over monoids from the class. Second, we prove that the class known as DA satisfies tameness and hence that the regular languages recognized by programs over monoids in DA are precisely those recognizable in the classical sense by morphisms from QDA. Third, we show by contrast that the well studied class of monoids called J is not tame and we exhibit a regular language, recognized by a program over a monoid from J, yet not recognizable classically by morphisms from the class QJ. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from DA.
Cite as

Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. The Power of Programs over Monoids in DA. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{grosshans_et_al:LIPIcs.MFCS.2017.2,
  author =	{Grosshans, Nathan and McKenzie, Pierre and Segoufin, Luc},
  title =	{{The Power of Programs over Monoids in DA}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.2},
  URN =		{urn:nbn:de:0030-drops-80909},
  doi =		{10.4230/LIPIcs.MFCS.2017.2},
  annote =	{Keywords: Programs over monoids, DA, lower-bounds}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact