Improved Randomized Approximation of Hard Universality and Emptiness Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911796265222144 |
|---|---|
| author | Andreou, Pantelis Konstantinidis, Stavros Smith, Taylor J. |
| author_facet | Andreou, Pantelis Konstantinidis, Stavros Smith, Taylor J. |
| contents | We build on recent research on polynomial randomized approximation (PRAX) algorithms for the hard problems of NFA universality and NFA equivalence. Loosely speaking, PRAX algorithms use sampling of infinite domains within any desired accuracy $δ$. In the spirit of experimental mathematics, we extend the concept of PRAX algorithms to be applicable to the emptiness and universality problems in any domain whose instances admit a tractable distribution as defined in this paper. A technical result here is that a linear (w.r.t. $1/δ$) number of samples is sufficient, as opposed to the quadratic number of samples in previous papers. We show how the improved and generalized PRAX algorithms apply to universality and emptiness problems in various domains: ordinary automata, tautology testing of propositions, 2D automata, and to solution sets of certain Diophantine equations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_08707 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Randomized Approximation of Hard Universality and Emptiness Problems Andreou, Pantelis Konstantinidis, Stavros Smith, Taylor J. Data Structures and Algorithms Formal Languages and Automata Theory 68W25 (primary), 68W20, 68Q45 (secondary) We build on recent research on polynomial randomized approximation (PRAX) algorithms for the hard problems of NFA universality and NFA equivalence. Loosely speaking, PRAX algorithms use sampling of infinite domains within any desired accuracy $δ$. In the spirit of experimental mathematics, we extend the concept of PRAX algorithms to be applicable to the emptiness and universality problems in any domain whose instances admit a tractable distribution as defined in this paper. A technical result here is that a linear (w.r.t. $1/δ$) number of samples is sufficient, as opposed to the quadratic number of samples in previous papers. We show how the improved and generalized PRAX algorithms apply to universality and emptiness problems in various domains: ordinary automata, tautology testing of propositions, 2D automata, and to solution sets of certain Diophantine equations. |
| title | Improved Randomized Approximation of Hard Universality and Emptiness Problems |
| topic | Data Structures and Algorithms Formal Languages and Automata Theory 68W25 (primary), 68W20, 68Q45 (secondary) |
| url | https://arxiv.org/abs/2403.08707 |