Nonuniform Deterministic Finite Automata over finite algebraic structures
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929683413598208 |
|---|---|
| author | Idziak, Paweł M. Kawałek, Piotr Krzaczkowski, Jacek |
| author_facet | Idziak, Paweł M. Kawałek, Piotr Krzaczkowski, Jacek |
| contents | Nonuniform Deterministic Finite Automata (NUDFA) over monoids were invented by Barrington to study boundaries of nonuniform constant-memory computation. Later, results on these automata helped to indentify interesting classes of groups for which equation satisfiability problem is solvable in (probabilistic) polynomial-time. Based on these results, we present a full characterization of groups, for which the identity checking problem has a probabilistic polynomial-time algorithm. We also go beyond groups, and propose how to generalise the notion of NUDFA to arbitrary finite algebraic structures. We study satisfiability of these automata in this more general setting. As a consequence, we present full description of finite algebras from congruence modular varieties for which testing circuit equivalence can be solved by a probabilistic polynomial-time procedure. In our proofs we use two computational complexity assumptions: randomized Expotential Time Hypothesis and Constant Degree Hypothesis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12260 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nonuniform Deterministic Finite Automata over finite algebraic structures Idziak, Paweł M. Kawałek, Piotr Krzaczkowski, Jacek Computational Complexity F.1.3; F.2.0 Nonuniform Deterministic Finite Automata (NUDFA) over monoids were invented by Barrington to study boundaries of nonuniform constant-memory computation. Later, results on these automata helped to indentify interesting classes of groups for which equation satisfiability problem is solvable in (probabilistic) polynomial-time. Based on these results, we present a full characterization of groups, for which the identity checking problem has a probabilistic polynomial-time algorithm. We also go beyond groups, and propose how to generalise the notion of NUDFA to arbitrary finite algebraic structures. We study satisfiability of these automata in this more general setting. As a consequence, we present full description of finite algebras from congruence modular varieties for which testing circuit equivalence can be solved by a probabilistic polynomial-time procedure. In our proofs we use two computational complexity assumptions: randomized Expotential Time Hypothesis and Constant Degree Hypothesis. |
| title | Nonuniform Deterministic Finite Automata over finite algebraic structures |
| topic | Computational Complexity F.1.3; F.2.0 |
| url | https://arxiv.org/abs/2501.12260 |