Tameness and the power of programs over monoids in DA
| Autor: | Grosshans, Nathan, Mckenzie, Pierre, Segoufin, Luc |
|---|---|
| Přispěvatelé: | University of Kassel, Département d'Informatique et de Recherche Opérationnelle [Montreal] (DIRO), Université de Montréal (UdeM), Value from Data (VALDA ), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Universität Kassel [Kassel], École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL) |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation Computer Science - Logic in Computer Science Discrete Mathematics (cs.DM) General Computer Science DA Formal Languages and Automata Theory (cs.FL) Computer Science - Formal Languages and Automata Theory Computational Complexity (cs.CC) [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Theoretical Computer Science ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages/F.4.3.0: Algebraic language theory [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] Mathematics::Category Theory Tameness F.1.1 F.4.3 F.1.3 Programs over monoids [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] Lower bounds Logic in Computer Science (cs.LO) Computer Science - Computational Complexity Computer Science::Programming Languages ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.3: Complexity Measures and Classes Computer Science - Discrete Mathematics |
| Zdroj: | 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⟩ |
| ISSN: | 1860-5974 |
| DOI: | 10.46298/lmcs-18(3:14)2022⟩ |
| Popis: | 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 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 $\mathbf{DA}$ satisfies tameness and hence that the regular languages recognized by programs over monoids in $\mathbf{DA}$ are precisely those recognizable in the classical sense by morphisms from $\mathbf{QDA}$. Third, we show by contrast that the well studied class of monoids called $\mathbf{J}$ is not tame. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from $\mathbf{DA}$. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|