Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917086945607680 |
|---|---|
| author | Yamakami, Tomoyuki |
| author_facet | Yamakami, Tomoyuki |
| contents | Lately, there have been intensive studies on strengths and limitations of nonuniform families of promise decision problems solvable by various types of polynomial-size finite automata families, where ``polynomial-size'' refers to the polynomially-bounded state complexity of a finite automata family. In this line of study, we further expand the scope of these studies to families of partial counting and gap functions, defined in terms of nonuniform families of polynomial-size nondeterministic finite automata, and their relevant families of promise decision problems. Counting functions have an ability of counting the number of accepting computation paths produced by nondeterministic finite automata. With no unproven hardness assumption, we show numerous separations and collapses of complexity classes of those partial counting and gap function families and their induced promise decision problem families. We also investigate their relationships to pushdown automata families of polynomial stack-state complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_18965 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata Yamakami, Tomoyuki Computational Complexity Formal Languages and Automata Theory Lately, there have been intensive studies on strengths and limitations of nonuniform families of promise decision problems solvable by various types of polynomial-size finite automata families, where ``polynomial-size'' refers to the polynomially-bounded state complexity of a finite automata family. In this line of study, we further expand the scope of these studies to families of partial counting and gap functions, defined in terms of nonuniform families of polynomial-size nondeterministic finite automata, and their relevant families of promise decision problems. Counting functions have an ability of counting the number of accepting computation paths produced by nondeterministic finite automata. With no unproven hardness assumption, we show numerous separations and collapses of complexity classes of those partial counting and gap function families and their induced promise decision problem families. We also investigate their relationships to pushdown automata families of polynomial stack-state complexity. |
| title | Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata |
| topic | Computational Complexity Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2310.18965 |