Tameness and the power of programs over monoids in DA
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 natu...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2022-08-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/7110/pdf |
| _version_ | 1797268491101798400 |
|---|---|
| author | Nathan Grosshans Pierre Mckenzie Luc Segoufin |
| author_facet | Nathan Grosshans Pierre Mckenzie Luc Segoufin |
| author_sort | Nathan Grosshans |
| collection | DOAJ |
| description | 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}$. |
| first_indexed | 2024-04-25T01:33:19Z |
| format | Article |
| id | doaj.art-56a8fd27c6c147998442e9087256d71d |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:33:19Z |
| publishDate | 2022-08-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-56a8fd27c6c147998442e9087256d71d2024-03-08T10:39:30ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742022-08-01Volume 18, Issue 310.46298/lmcs-18(3:14)20227110Tameness and the power of programs over monoids in DANathan GrosshansPierre MckenzieLuc SegoufinThe 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}$.https://lmcs.episciences.org/7110/pdfcomputer science - computational complexitycomputer science - discrete mathematicscomputer science - formal languages and automata theorycomputer science - logic in computer sciencef.1.1f.4.3f.1.3 |
| spellingShingle | Nathan Grosshans Pierre Mckenzie Luc Segoufin Tameness and the power of programs over monoids in DA Logical Methods in Computer Science computer science - computational complexity computer science - discrete mathematics computer science - formal languages and automata theory computer science - logic in computer science f.1.1 f.4.3 f.1.3 |
| title | Tameness and the power of programs over monoids in DA |
| title_full | Tameness and the power of programs over monoids in DA |
| title_fullStr | Tameness and the power of programs over monoids in DA |
| title_full_unstemmed | Tameness and the power of programs over monoids in DA |
| title_short | Tameness and the power of programs over monoids in DA |
| title_sort | tameness and the power of programs over monoids in da |
| topic | computer science - computational complexity computer science - discrete mathematics computer science - formal languages and automata theory computer science - logic in computer science f.1.1 f.4.3 f.1.3 |
| url | https://lmcs.episciences.org/7110/pdf |
| work_keys_str_mv | AT nathangrosshans tamenessandthepowerofprogramsovermonoidsinda AT pierremckenzie tamenessandthepowerofprogramsovermonoidsinda AT lucsegoufin tamenessandthepowerofprogramsovermonoidsinda |